Precision medicine brings the promise of more precise diagnosis and individualized therapeutic strategies from analyzing a cancer's genomic signature. Technologies such as high-throughput sequencing enable cheaper data collection at higher speed, but rely on modern data analysis platforms to extract knowledge from these high dimensional datasets. Since this is a rapidly advancing field, new diagnoses and therapies often require tailoring of the analysis. These pipelines are therefore developed iteratively, continuously modifying analysis parameters before arriving at the final results. To enable reproducible results it is important to record all these modifications and decisions made during the analysis process. We built a system, walrus, to support reproducible analyses for iteratively developed analysis pipelines. The approach is based on our experiences developing and using deep analysis pipelines to provide insights and recommendations for treatment in an actual breast cancer case. We designed walrus for the single servers or small compute clusters typically available for novel treatments in the clinical setting. walrus leverages software containers to provide reproducible execution environments, and integrates with modern version control systems to capture provenance of data and pipeline parameters. We have used walrus to analyze a patient's primary tumor and adjacent normal tissue, including subsequent metastatic lesions. Although we have used walrus for specialized analyses of whole-exome sequencing datasets, it is a general data analysis tool that can be applied in a variety of scientific disciplines.

Although systemic immunity is critical to the process of tumor rejection, cancer research has largely focused on immune cells in the tumor microenvironment. To understand molecular changes in the patient systemic response (SR) to the presence of BC, we profiled RNA in blood and matched tumor from 173 patients. We designed a system (MIxT, Matched Interactions Across Tissues) to systematically explore and link molecular processes expressed in each tissue. MIxT confirmed that processes active in the patient SR are especially relevant to BC immunogenicity. The nature of interactions across tissues (i.e. which biological processes are associated and their patterns of expression) varies highly with tumor subtype. For example, aspects of the immune SR are underexpressed proportionally to the level of expression of defined molecular processes specific to basal tumors. The catalog of subtype-specific interactions across tissues from BC patients provides promising new ways to tackle or monitor the disease by exploiting the patient SR.

A genetic interaction (GI) is defined when the mutation of one gene modifies the phenotypic expression associated with the mutation of a second gene. Genome-wide efforts to map GIs in yeast revealed structural and functional properties of a GI network. This provided insights into the mechanisms underlying the robustness of yeast to genetic and environmental insults, and also into the link existing between genotype and phenotype. While a significant conservation of GIs and GI network structure has been reported between distant yeast species, such a conservation is not clear between unicellular and multicellular organisms. Structural and functional characterization of a GI network in these latter organisms is consequently of high interest. In this study, we present an in-depth characterization of ~1.5K GIs in the nematode Caenorhabditis elegans. We identify and characterize six distinct classes of GIs by examining a wide-range of structural and functional properties of genes and network, including co-expression, phenotypical manifestations, relationship with protein-protein interaction dense subnetworks (PDS) and pathways, molecular and biological functions, gene essentiality and pleiotropy. Our study shows that GI classes link genes within pathways and display distinctive properties, specifically towards PDS. It suggests a model in which pathways are composed of PDS-centric and PDS-independent GIs coordinating molecular machines through two specific classes of GIs involving pleiotropic and non-pleiotropic connectors. Our study provides the first in-depth characterization of a GI network within pathways of a multicellular organism. It also suggests a model to understand better how GIs control system robustness and evolution.

The incongruency between a gene tree and a corresponding species tree can be attributed to evolutionary events such as gene duplication and gene loss. This paper describes a combinatorial model where so-called DTL-scenarios are used to explain the differences between a gene tree and a corresponding species tree taking into account gene duplications, gene losses, and lateral gene transfers (also known as horizontal gene transfers). The reasonable biological constraint that a lateral gene transfer may only occur between contemporary species leads to the notion of acyclic DTL-scenarios. Parsimony methods are introduced by defining appropriate optimization problems. We show that finding most parsimonious acyclic DTL-scenarios is NP-hard. However, by dropping the condition of acyclicity, the problem becomes tractable, and we provide a dynamic programming algorithm as well as a fixed-parameter tractable algorithm for finding most parsimonious DTL-scenarios.

A key problem in molecular biology is to infer regulatory relationships between genes from expression data. This paper studies a simplified model of such inference problems in which one or more Boolean variables, modeling, for example, the expression levels of genes, each depend deterministically on a small but unknown subset of a large number of Boolean input variables. Our model assumes that the expression data comprises a time series, in which successive samples may be correlated. We provide bounds on the expected amount of data needed to infer the correct relationships between output and input variables. These bounds improve and generalize previous results for Boolean network inference and continuous-time switching network inference. Although the computational problem is intractable in general, we describe a fixed-parameter tractable algorithm that is guaranteed to provide at least a partial solution to the problem. Most interestingly, both the sample complexity and computational complexity of the problem depend on the strength of correlations between successive samples in the time series but in opposing ways. Uncorrelated samples minimize the total number of samples needed while maximizing computational complexity; a strong correlation between successive samples has the opposite effect. This observation has implications for the design of experiments for measuring gene expression.

UNLABELLED: Many tools exist for visually exploring biological networks including well-known examples such as Cytoscape, VisANT, Pathway Studio and Patika. These systems play a key role in the development of integrative biology, systems biology and integrative bioinformatics. The trend in the development of these tools is to go beyond 'static' representations of cellular state, towards a more dynamic model of cellular processes through the incorporation of gene expression data, subcellular localization information and time-dependent behavior. We provide a comprehensive review of the relative advantages and disadvantages of existing systems with two goals in mind: to aid researchers in efficiently identifying the appropriate existing tools for data visualization; to describe the necessary and realistic goals for the next generation of visualization tools. In view of the first goal, we provide in the Supplementary Material a systematic comparison of more than 35 existing tools in terms of over 25 different features. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: We introduce a development platform especially tailored to Bioinformatics research and software development. BIAS (Bioinformatics Integrated Application Software) provides the tools necessary for carrying out integrative Bioinformatics research requiring multiple datasets and analysis tools. It follows an object-relational strategy for providing persistent objects, allows third-party tools to be easily incorporated within the system and supports standards and data-exchange protocols common to Bioinformatics. AVAILABILITY: BIAS is an OpenSource project and is freely available to all interested users at http://www.mcb.mcgill.ca/~bias/. This website also contains a paper containing a more detailed description of BIAS and a sample implementation of a Bayesian network approach for the simultaneous prediction of gene regulation events and of mRNA expression from combinations of gene regulation events. CONTACT: [email protected].

The study of protein subcellular localization is important to elucidate protein function. Even in well-studied organisms such as yeast, experimental methods have not been able to provide a full coverage of localization. The development of bioinformatic predictors of localization can bridge this gap. We have created a Bayesian network predictor called PSLT2 that considers diverse protein characteristics, including the combinatorial presence of InterPro motifs and protein interaction data. We compared the localization predictions of PSLT2 to high-throughput experimental localization datasets. Disagreements between these methods generally involve proteins that transit through or reside in the secretory pathway. We used our multi-compartmental predictions to refine the localization annotations of yeast proteins primarily by distinguishing between soluble lumenal proteins and soluble proteins peripherally associated with organelles. To our knowledge, this is the first tool to provide this functionality. We used these sub-compartmental predictions to characterize cellular processes on an organellar scale. The integration of diverse protein characteristics and protein interaction data in an appropriate setting can lead to high-quality detailed localization annotations for whole proteomes. This type of resource is instrumental in developing models of whole organelles that provide insight into the extent of interaction and communication between organelles and help define organellar functionality.

This paper introduces a combinatorial model that incorporates duplication events as well as lateral gene transfer events (a.k.a. horizontal gene transfer events). To the best of our knowledge, this is the first such model containing both of these events. A so-called dt-scenario is used to explain differences between a gene tree T and species trees S. The model is biologically as well as mathematically sound. Among other biological considerations, the model respects the partial order of evolution implied by S by demanding that the dt-scenarios are We present fixed parameter tractable algorithms that count the minimum number of duplications and lateral transfers, and more generally can compute the set of pairs (t,d) where d is the minimum number of duplications required by any explanation that requires t lateral transfers. This allows us to also compute a weighted parsimony score. We also show how gene loss events can be incorporated into our model. We also give an $NP$-completeness proof which suggests that the intractability is due to the demand that the dt-scenarios be acyclic. When this condition is removed, we can show that the problem is computable in polynomial time via dynamic programming. By generating synthetic gene and species trees via a birth-death process, we explored the capacity of our algorithms to faithfully reconstruct the actual number of events taken place. The results are positive.

MOTIVATION: Information concerning endoplasmic reticulum (ER) proteins is widely dispersed and cannot be easily and rapidly processed by the biological community. We present a comprehensive database of human ER proteins, called Human ER Aperçu (Hera). The Hera database was constructed by exhaustively searching through public databases and the scientific literature for ER proteins. RESULTS: Hera was used for the analysis of characteristics common to all human ER proteins. Our results show that a high proportion of ER proteins (59%) have at least one transmembrane domain and display physical characteristics consistent with this observation. In addition, one-third of ER proteins contain known ER retrieval or retention signals and 70% of ER proteins contain a signal peptide or anchor. Finally, 85% of ER proteins contain at least one InterPro motif. The most abundant InterPro motifs in ER proteins represent many of the most well-characterized functions of the ER.

Many scientific disciplines are shifting from in vitro to in silico research as more physical processes and natural phenomena are examined in a computer (in silico) instead of being observed (in vitro). In many of these virtual laboratories, the computations involved are very complex and long lived. Currently, users are required to manually handle almost all aspects of such computations, including their dependability. Not surprisingly, this is a major bottleneck and a significant source of inefficiencies. To address this issue, we have developed BioOpera, an extensible process support management system for virtual laboratories. The authors briefly discuss the architecture and functionality of BioOpera and show how it can be used to efficiently manage long lived computations.

This paper develops a model for lateral gene transfer events (a.k.a. horizontal gene transfer events) between a set of gene trees T1, T2, …, Tk and a species tree S. To the best of our knowledge, this model possesses a higher degree of biological and mathematical soundness than any other model proposed in the literature. Among other biological considerations, the model respects the partial order of evolution implied by S. Within our model, we identify an activity parameter that measures the number of genes that are allowed to be simultaneously active in the genome of a taxa and show that finding the most parsimonious scenario that reconciles the disagreeing gene trees with the species tree is doable in polynomial time when the activity level and number of transfers are small, but intractable in general. To the best of our knowledge, all other models proposed in the literature assume implicitly that the activity is one. Finally, using a dataset of bacterial gene sequences from [4], our implementations found 5 optimal scenarios; one of which is the scenario proposed by the authors in [4].

We consider the problem of constructing a species tree given a number of gene trees. In the frameworks introduced by Goodman et al. [3], Page [10], and Guigó, Muchnik, and Smith [5] this is formulated as an optimization problem; namely, that of finding the species tree requiring the minimum number of duplications and/ or losses in order to explain the gene trees.

Abstract Summary: We make available a large cross-comparison for 16 of the completely sequenced genomes and additional eukaryotic genes. The alignments were performed at the protein level using liberal similarity bounds in order to capture as many significant alignments as possible. This dataset will be updated as new genomes become available. Availability: The dataset is accessible at http://cbrg.inf.ethz.ch/AllAllGeneAlign.html Contact: [email protected] * To whom correspondence should be addressed.

MOTIVATION: We announce the availability of the second release of Darwin v. 2.0, an interpreted computer language especially tailored to researchers in the biosciences. The system is a general tool applicable to a wide range of problems. RESULTS: This second release improves Darwin version 1.6 in several ways: it now contains (1) a larger set of libraries touching most of the classical problems from computational biology (pairwise alignment, all versus all alignments, tree construction, multiple sequence alignment), (2) an expanded set of general purpose algorithms (search algorithms for discrete problems, matrix decomposition routines, complex/long integer arithmetic operations), (3) an improved language with a cleaner syntax, (4) better on-line help, and (5) a number of fixes to user-reported bugs. AVAILABILITY: Darwin is made available for most operating systems free of char ge from the Computational Biochemistry Research Group (CBRG), reachable at http://chrg.inf.ethz.ch. CONTACT: [email protected]

Many computational problems in biology involve parameters for which a small range of values cover important applications. We argue that for many problems in this setting, parameterized computational complexity rather than NP-completeness is the appropriate tool for studying apparent intractability. At issue in the theory of parameterized complexity is whether a problem can be solved in time O(n alpha) for each fixed parameter value, where alpha is a constant independent of the parameter. In addition to surveying this complexity framework, we describe a new result for the Longest Common Subsequence problem. In particular, we show that the problem is hard for W[t] for all t when parameterized by the number of strings and the size of the alphabet. Lower bounds on the complexity of this basic combinatorial problem imply lower bounds on more general sequence alignment and consensus discovery problems. We also describe a number of open problems pertaining to the parameterized complexity of problems in computational biology where small parameter values are important.

The parameterized computational complexity of a collection of well-known problems including: BAND-WIDTH, PRECEDENCE CONSTRAINED MULTIPROCES-SOR SCHEDULING, LONGEST COMMON SUBSEQUENCE, DNA PHYSICAL MAPPING (or INTERNALIZING COL-ORED GRAPHS), PERFECT PHYLOGENY (or TRIANGU-LATING COLORED GRAPHS), COLORED CUTWIDTH, and FEASIBLE REGISTER ASSIGNMENT is explored.It is shown that these problems are hard for various levels of the W hierarchy.In the case of PRECEDENCE CONSTRAINED MULTIPROCESSOR SCHEDULING the results can be interpreted as providing substantial new complexity lower bounds on the outcome of [OPEN 8] of the Garey and Johnson list.