The structures of protein–protein complexes in the apoptosis signaling pathway are important as the structural pathway helps in understanding the mechanism of the regulation and information transfer, and in identifying targets for drug design. Here, we aim to predict the structures toward a more informative pathway than currently available. Based on the 3D structures of complexes in the target pathway and a protein–protein interaction modeling tool which allows accurate and proteome-scale applications, we modeled the structures of 29 interactions, 21 of which were previously unknown. Next, 27 interactions which were not listed in the KEGG apoptosis pathway were predicted and subsequently validated by the experimental data in the literature. Additional interactions are also predicted. The multi-partner hub proteins are analyzed and interactions that can and cannot co-exist are identified. Overall, our results enrich the understanding of the pathway with
interactions and provide structural details for the human apoptosis pathway.

Bacterial cells communicate with one another by exchanging chemical signals, which can be used to coordinate actions across a cell population. Such coordination, regulated by so-called quorum-sensing systems, works on the following principle: every cell secretes a specific signal; the more cells there are, the more signal is generated; when the population density crosses a critical threshold, cells respond by driving transcription at a specific promoter. In our experiments, we find that quorum-sensing feedback systems can generate a diverse array of response types; this diversity arises through the complex interaction of microscopic parameters with feedback topology. I will show how, treating the promoter as a black-box characterized only by its input/output response or ‘promoter logic’, we are able to qualitatively and quantitatively predict the entire range of experimentally observed responses: smooth activation; hysteretic behavior; and even synchronized oscillations. Promoter logic is thus a necessary and sufficient representation of microscopic biochemistry.

Motivation: Staining the mRNA of a gene via in situ hybridization (ISH) during the development of a Drosophila melanogaster embryo delivers the detailed spatio-temporal patterns of the gene expression. Many related biological problems such as the detection of co-expressed genes, co-regulated genes, and transcription factor binding motifs rely heavily on the analysis of these image patterns. To provide the text-based pattern searching for facilitating related biological studies, the images in the Berkeley Drosophila Genome Project (BDGP) study are annotated with developmental stage term and anatomical ontology terms manually by domain experts. Due to the rapid increasing number of such images and the inevitable bias annotations by human curators, it is necessary to develop an automatic method to recognize the developmental stage and annotate anatomical terms. Results: In this paper, we propose a novel computational model for joint stage classification and anatomical terms annotation of Drosophila gene expression patterns. We introduce a new Tri-Relational Graph (TG) model that comprises the data graph, anatomical terms graph, developmental stage term graph, and connects them by three additional graphs induced from stage or annotation label assignments. Upon the TG model, we present a Preferential Random Walk (PRW) method to jointly recognize developmental stage and annotate anatomical terms by utilizing the interrelations between two tasks. The experimental results on two refined BDGP data sets demonstrate our joint learning method can achieve superior prediction results on both tasks than the state-of-the-art methods.

To better understand the molecular mechanisms and genetic basis of human disease, we systematically examine relationships between 3,949 genes, 62,663 mutations and 3,453 associated disorders by generating a three-dimensional, structurally resolved human interactome. This network consists of 4,222 high-quality binary protein-protein interactions with their atomic-resolution interfaces. We find that in-frame mutations (missense mutations and in-frame insertions and deletions) are enriched on the interaction interfaces of proteins associated with the corresponding disorders, and that the disease specificity for different mutations of the same gene can be explained by their location within an interface. We also predict 292 candidate genes for 694 unknown disease-to-gene associations with proposed molecular mechanism hypotheses. This work indicates that knowledge of how in-frame disease mutations alter specific interactions is critical to understanding pathogenesis. Structurally resolved interaction networks should be valuable tools for interpreting the wealth of data being generated by large-scale structural genomics and disease association studies.

By analyzing gene expression data in gliobastoma in combination with matched microRNA profiles, we have uncovered a post-transcriptional regulation layer of surprising magnitude, comprising hundreds of thousands of microRNA-mediated interactions. These include thousands of genes whose transcripts act as microRNA ‘sponges’ and hundreds of genes that act through alternative, non-sponge interactions. Biochemical analyses in cell lines confirmed that this network regulates established drivers of glioblastoma tumor initiation and subtype, including P53, PTEN, PDGFRA, RB1, VEGFA, STAT3, and RUNX1, suggesting that these interactions mediate crosstalk between canonical oncogenic pathways. RNA silencing of 13 microRNA-mediated PTEN regulators, whose locus deletions are predictive of PTEN expression variability, was sufficient to downregulate PTEN in a 3' UTR-dependent manner and to increase tumor-cell growth rates. Thus, this microRNA-mediated network provides a mechanistic, experimentally validated rationale for the loss of PTEN expression in a large number of glioma samples with an intact PTEN locus.

Motivation: A new technique, mammalian GFP reconstitution across synaptic partners (mGRASP), enables mapping mammalian synaptic connectivity with light microscopy. To! characterize the locations and distribution of synapses in complex neuronal networks visualized by mGRASP, it is essential to detect mGRASP fluorescence signals with high accuracy.

Results: We developed a fully-automatic method for detecting mGRASP-labeled synapse puncta. By modeling each punctum as a Gaussian distribution, our method enables accurate detection even when puncta of varying size and shape partially overlap. The method consists of three stages: blob detection by global thresholding; blob separation by watershed; and punctum modeling by a Variational Bayesian Gaussian Mixture Model. Extensive testing shows that the three-stage method improved detection accuracy markedly, and especially reduces under-segmentation. The method provides a goodness-of-fit score for each detected punctum, allowing efficient error detection. We applied this advantage to also develop an efficient interactive method for correcting errors.

Availability: The software is available on http! ://jinny.kist.re.kr

This paper concerns a central issue in the analysis of biological networks, which is how functional information can be discovered or exploited through their use. Our key finding is that almost all the available information on gene function is concentrated in a tiny part of networks. A striking demonstration is that a mouse gene network of 4.5 million edges can be reduced one with just 23 edges, while retaining key features commonly thought to involve widely distributed properties. At a basic level, the “guilt-by-association” approach that is practised by biologists all the time to study genes one-by-one does not scale up to networks, despite numerous claims to the contrary. Attempts to adjust or validate networks based on gene function are highly misleading, and attempts to predict gene function using computational means are based on deeply flawed assumptions. We offer concrete suggestions to help others avoid these pitfalls.

The generation of time series transcriptomic datasets collected under multiple experimental conditions has proven to be a powerful approach for disentangling complex biological processes, allowing for the reverse engineering of gene regulatory networks (GRNs). Most methods for reverse engineering GRNs from multiple datasets assume that each of the time series were generated from networks with identical topology. Here we outline a hierarchical, nonparametric Bayesian approach for reverse engineering GRNs using multiple time series that can be applied in a number of novel situations including: (i) where different, but overlapping sets of transcription factors are expected to bind in the different experimental conditions i.e., where switching events could potentially arise under the different treatments; and (ii) for inference in evolutionary related species in which orthologous GRNs exist. The hierarchical inference outperforms related (but non- hierarchical) approaches when the networks used to generate the data were identical, and performs comparably even when the networks used to generate data were independent. The method was subsequently used alongside yeast one-hybrid and microarray time series data to infer potential transcriptional switches in Arabidopsis thaliana response to abiotic stress. The results confirm previous biological studies and allow for additional insights into gene regulation under various abiotic stresses.

In human proteome, the subcellular location pattern is crucial for understanding the functions of a protein. This pattern is essentially characterized by the co-localization of the protein and the components in the cell. In this paper, we address the protein pattern classification problem based on the confocal immune-fluorescence cellular images from the Human Protein Atlas (HPA) project. In our HPA data set, each cell has the staining images of one protein and three reference components, and in the meanwhile there are many other components that are invisible. Given one such cell, the task is to classify the pattern type of stained protein. We first randomly select local image regions within the cells, and then extract various carefully designed features from these regions. Compared to traditional cell based methods, this region based approach enables us to explicitly study the relationship between proteins and different cell components, as well as the interactions between these components. To achieve these two goals, we propose two discriminative models that extend logistic regression with structured latent variables. The first model allows the same protein pattern class to be expressed differently according to the underlying components in different regions. The second model further captures the spatial dependencies between the components within the same cell so that we can better infer these components. To learn these models, we propose a fast approximate algorithm for inference, and then use gradient based methods to maximize the data likelihood. In the experiments, we show that the proposed models can both help improve the classification accuracies on synthetic data and real cellular images. The best overall accuracy we report in this paper for classifying $942$ proteins into $13$ classes of patterns is about $84.6\%$, which to our knowledge is the best so far. In addition, we can give these results biological interpretations.

Genetic interactions provide a powerful perspective into biological processes that is fundamentally different from other high-throughput genome-wide studies. We developed a data mining approach based on association rule learning to exhaustively discover all statistically significant block structures within the yeast genetic interaction network, producing a complete modular decomposition of the network. This provides a first opportunity for a global, unbiased assessment of the structure of the genetic interaction network and the relationship between structure and individual gene function. The genetic interaction network is highly structured with over half of interactions appearing in modular structures, and genetic interactions contained within modules exhibit strikingly different functional properties relative to isolated interactions. In addition, gene module membership provides a specific and unbiased assessment of the prevalence of multi-functionality among genes. Our modular decomposition also provided a basis for testing the between-pathway model of negative genetic interactions and within-pathway model of positive genetic interactions.

Motivation: Nucleosomes are the basic elements of DNA chromatin structure. They control the packaging of DNA and play a critical role in gene regulation by allowing physical access to transcription factors. The advent of second-generation sequencing has enabled landmark genome-wide studies of nucleosome position for several model organisms. Current methods to determine nucleosome positioning first compute an occupancy coverage profile by mapping nucleosome-enriched sequenced reads to a reference genome; then, nucleosomes are placed according to the peaks of the coverage profile. These methods are quite accurate on placing isolated nucleosomes, but they do not properly handle "overlapping" nucleosomes. Also, they can only provide the positions of nucleosomes and their occupancy level, while it is very beneficial to supply molecular biologists additional information about nucleosomes like the probability of placement, the size of DNA fragments enriched for nucleosomes, and/or whether nucleosome are well-positioned or "fuzzy" in the sequenced cell sample. Results: We address these issues by providing a novel method based on a parametric probabilistic model. An expectation maximization (EM) algorithm is used to infer the parameters of the mixture of distributions. We compare the performance of our method on two real datasets against Template Filtering, which is considered the current state-of-the-art. Experimental results show that our method detects a significantly higher number of nucleosomes than Template Filtering.

In human, over 1000 microRNAs (miRNAs) regulate the expression of about half of the genes. This study addresses the potential of a coordinated action of miRNAs to manipulate hundreds of human pathways. Specifically, we analyzed the effectiveness of disrupting the topology of human pathway graphs through a regulation by miRNAs. We will present the combination of our concept of miRNA ‘working together’ (Friedman et al., Bioinformatics, 2010) with the pathways’ topology considerations. From a set of miRNA candidates, an exhaustive search for all possible doubles and triplets (coined miR-Duo, miR-Trios) that impact the integrity of a pathway is performed. We will discuss the surprising finding that 85% of all pathways are effectively disconnected by a remarkably small number of miRNAs sets. Significantly, the combination of the most effective miR-Trios is unique for each pathway. The impact of the selected miR-Duo/Trios on various diseases will be discussed.

Quantitative analyses of next-generation sequencing (NGS) data, such as the detection of copy number variations (CNVs), remain challenging. Technological or genomic variations in the depth of coverage lead to a high false discovery rate (FDR), even upon correction for GC content. We propose ‘Copy Number estimation by a Mixture Of PoissonS’ (cn.MOPS), a data processing pipeline for CNV detection in NGS data. In contrast to previous approaches, cn.MOPS incorporates modeling of depths of coverage across samples at each genomic position. Therefore, cn.MOPS is not affected by read count variations along chromosomes. Using a Bayesian approach, cn.MOPS decomposes variations in the depth of coverage across samples into integer copy numbers and noise noise by means of its mixture components and Poisson distributions, respectively. The noise estimate allows for reducing the FDR by filtering out detections having high noise, which is the reason for the superior performance.

Splicing is generally regulated by protein factors binding the pre-mRNA. Yeast lacks many of the splicing factors present in metazoans; hence it is thought to have limited regulated splicing. We present experimental evidence that the structure adopted by the pre-mRNA can function as a regulator of 3’ splice site selection in yeast, bringing the selected site close to the branch-site (BS) and occluding the rest.

Based on these observations we built a computational classifier that explains most of the annotated 3’ss in yeast. Our model also predicts the usage of alternative 3’ss at low and/or high temperatures, some of which we validated experimentally. Our results are consistent with the presence of alternative 3’ss selection in yeast that is mediated by the pre-mRNA structure, which can be responsive to external cues, like temperature, and which is possibly related to the control of gene expression.

Prenylation is an important post-translational modification in which a lipid prenyl group is covalently attached to a protein, thereby changing its functional role. As an example, ras uses this mechanism to reach the membrane where it is active.

In this talk I will describe our recent work on the structure-based modeling of prenylation substrates based on Rosetta FlexPepDock, our peptide docking protocol. Based on structural models of the c-terminal peptide sequence of a protein bound to the enzyme farnesyltransferase, our protocol FlexPepBind identifies both known and novel farnesylation substrates. In vitro validation of the latter demonstrates the high accuracy of this approach: 26/29 peptides are indeed farnesylated. Application of our protocol to human as well as pathogenic genomes has identified many new and interesting targets.This work provides a link between the structure of a peptide-protein complex to its biological importance.

Epistatic interactions between genes are crucial for understanding the molecular mechanisms of complex diseases. While systematic testing of genetic interactions with an impact on physiological fitness is possible in simple model organisms, such screens have not been successful in mammals. Here, we propose a computational screening method that only requires genotype information of family trios for predicting epistasis. Based on a Chi-squared test approach, it detects the under-representation of allele pairs in a given population.
We tested our framework on a set of 2,000 heterozygous mice and found 168 imbalanced allele pairs, which is substantially more than expected by chance. We confirmed many of the interactions using independent data and found that interacting loci are enriched for developmental genes. The number of imbalanced allele pairs that we detected is surprisingly large and was not expected based on published evidence. This framework sets the stage for similar work in human trios.

Gene translation is a central process in all living organisms. Thus, attaining a better understanding of this complex process has ramifications to every biomedical discipline. In this talk, I will survey recent results related to this topic.
I will show that features of the transcript, such as its folding strength, the adaptation of its codons to the tRNA pool, and the charge of the amino acids encoded in it, contribute to translation efficiency in a causal and/or non-causal way. Specifically, highly expressed genes have stronger mRNA folding, possibly to prevent aggregation of mRNA molecules. In addition, each of these features contributes to: 1) The spatial distribution of ribosomes along transcripts; 2) Slowing down ribosomes at the beginning of the coding regions, presumably to reduce ribosomal traffic-jams and decrease the translation cost.
I will also demonstrate how these results can be integrated into a comprehensive computational predictive model of translation.

Motivation: Biological networks change in response to genetic and environmental cues. Changes are reflected in the abundances of biomolecules, the composition of protein complexes, and other descriptors of the biological state. Methods to infer the dynamic state of a cell would have great value for understanding how cells change over time to accomplish biological goals. Results: A new method predicts the dynamic state of protein complexes in a cell, with protein expression inferred from transcription profile time courses and protein complexes inferred by joint analysis of protein co-expression and protein-protein interaction maps. Two algorithmic advances are presented: a new method, DHAC (Dynamical Hierarchical Agglomerative Clustering), for clustering time-evolving networks; and a companion method, MATCH-EM, for matching corresponding clusters across time-points. With link prediction as an objective assessment metric, DHAC provides a substantial advance over existing clustering methods. An application to the yeast metabolic cycle demonstrates how waves of gene expression correspond to individual protein complexes. Our results suggest regulatory mechanisms for assembling the mitochondrial ribosome and illustrate dynamic changes in the components of the nuclear pore. Availability: All source code and data will be available through a BSD open source license as supplementary material and at www.baderzone.org.

Motivation: Since many complex disease and expression phenotypes are the outcome of intricate perturbation of molecular networks underlying gene regulation resulted from interdependent genome variations, association mapping of causal QTLs or eQTLs must consider both additive and epistatic effects of multiple candidate genotypes. This problem poses a significant challenge to contemporary genome-wide-association (GWA) mapping technologies because of its computational complexity. Fortunately, a plethora of recent developments in biological network community, especially the availability of genetic interaction networks, make it possible to construct informative priors of complex interactions between genotypes, which can substantially reduce the complexity and increase the statistical power of GWA inference. Results: In this paper, we consider the problem of learning a multi-task regression model while taking advantage of the prior information on structures on both the inputs (genetic variations) and outputs (expression levels). We propose a novel regularization scheme over multi-task regression called structured jointly input/output lasso based on an L1/L2 norm, which allows shared sparsity patterns for related inputs and outputs to be optimally estimated. Such patterns capture multiple related SNPs that jointly influence multiple related expression traits. In addition, we generalize this new multi-task regression to structurally regularized polynomial regression to detect epistatic interactions with manageable complexity by exploiting the prior knowledge on candidate epistatic SNPs from biological experiments. We demonstrate our method on simulated and yeast eQTL datasets.

We present a method, Lineage Program, that uses the developmental lineage relationship of observed gene expression measurements to improve the learning of developmentally relevant cellular states and expression programs. We find that incorporating lineage information allows us to significantly improve both the predictive power and interpretability of expression programs that are derived from expression measurements from in vitro differentiation experiments. The lineage tree of a differentiation experiment is a tree graph whose nodes describe all of the unique expression states in the input expression measurements, and edges describe the experimental perturbations applied to cells. Our method, LineageProgram, is based on a log-linear model with parameters that reflect changes along the lineage tree. Regularization with L1 based methods controls the parameters in three distinct ways: the number of genes which change between two cellular states, the number of unique cellular states, and the number of underlying factors responsible for changes in cell state. The model is estimated with proximal operators to quickly discover a small number of key cell states and gene sets. Comparisons with existing factorization techniques such as singular value decomposition and nonnegative matrix factorization show that our method provides higher predictive power in held-out tests while inducing sparse and biologically relevant gene sets.

Motivation: Inferring the underlying signaling pathways within a gene interaction network is a fundamental problem in Systems Biology to help understand the complex interactions and the transmission and flow of information within a system-of-interest. Given a weighted gene network and a gene in this network, the goal of an inference algorithm is to identify the potential signaling pathways passing through this gene. Results: In a departure from previous approaches that largely rely on the random walk model, we propose a novel single-source $k$ shortest paths based algorithm to address this inference problem. An important element of our approach is to explicitly account for and enhance the diversity of paths discovered by our algorithm. The intuition here is that diversity in paths can help enrich different functions and thereby better position one to understand the underlying system-of-interest. Results on the yeast gene network demonstrate the utility of the proposed approach over extant state-of-the-art inference algorithms. Beyond utility, our algorithm achieves a significant speedup over these baselines.

Recent technological developments in measuring genetic variation have ushered in an era of genome wide association studies which have discovered many genes involved in human disease. Current methods to perform association studies collect genetic information and compare the frequency of variants in a individuals who with and without the disease. Standard approaches do not take into account any information on whether or not a given variant is likely to have an effect on the disease. We propose a novel method for computing an association statistics which takes into account prior information. Our method improves both power and resolution by 43.5% and 45%, repsectively, over traditional methods for performing association studies when applied to simulations using the HapMap data. Advantages of our method are that it is as simple to apply to association studies as standard methods, the results of the method are intepretable since the method reports p-values, and the method is optimal in its use of prior information in regards to statistical power.

Motivation: With the vast increase in the number of gene expression datasets deposited in public databases, novel techniques are required to analyze and mine this wealth of data. Similar to the way BLAST enables cross-species comparison of sequence data, tools that enable cross-species expression comparison will allow us to better utilize these datasets: Cross-species expression comparison enables us to address questions in evolution and development, and further allows the identification of disease related genes and pathways that play similar roles in humans and model organisms. Unlike sequence, which is static, expression data changes over time and under different conditions. Thus, a prerequisite for performing cross-species analysis is the ability to match experiments across species. Results: To enable better cross-species comparisons, we developed methods for automatically identifying pairs of similar expression datasets across species. Our method uses a co-training algorithm to combine a model of expression similarity with a model of the text which accompanies the expression experiments. The co-training method outperforms previous methods based on expression similarity alone. Using expert analysis, we show that the new matches identified by our method indeed capture biological similarities across species. We then use the matched expression pairs between human and mouse to recover known and novel cycling genes as well as to identify genes with possible involvement in diabetes. By providing the ability to identify novel candidate genes in model organisms, our method opens the door to new models for studying diseases.

Sequence-based protein function and structure prediction depends critically on sequence-search sensitivity and accuracy of the resulting sequence alignments. I will present HHblits (HMM-HMM–based lightning-fast iterative sequence search), an open-source, general-purpose search tool, which represents both query and database sequences by profile-hidden hidden Markov models (HMMs). Compared to the PSI-BLAST, HHblits is faster owing to its discretized-profile prefilter, has 50–100% higher sensitivity and generates more accurate alignments. It thus has the potential to improve many downstream analysis and prediction methods. I will first explain how HHblits achieves its sensitivity and speed and then show benchmarks and biological applications. If possible, I will finish by a short software demo.

Motivation: The prediction of RNA three-dimensional structures from its sequence only is a milestone to RNA function analysis and prediction. In recent years, many methods addressed this challenge, ranging from cycle decomposition and fragment assembly to molecular dynamics simulations. However, their predictions remain fragile and limited to small RNAs. To expand the range and accuracy of these techniques, we need to develop algorithms that will enable to use all the structural information available. In particular, the energetic contribution of secondary structure interactions is now well documented, but the quantification of non-canonical interactions – those shaping the tertiary structure – is poorly understood. Nonetheless, even if a complete RNA tertiary structure energy model is currently unavailable, we now have catalogues of local 3D structural motifs including non-canonical base pairings. A practical objective is thus to develop techniques enabling us to use this knowledge for robust RNA tertiary structure predictors. Results: In this work, we introduce RNA-MoIP, a program that benefits from the progresses made over the last 30 years in the field of RNA secondary structure prediction and expands these methods to incorporate the novel local motif information available in databases. Using an integer programming framework, our method refines predicted secondary structures (i.e. removes incorrect canonical base-pairs) to accommodate the insertion of RNA 3D motifs (i.e. hairpins, internal loops and k-way junctions). Then, we use predictions as templates to generate complete 3D structures with the MC-Sym program. We benchmarked RNA-MoIP on a set of 9 RNAs with sizes varying from 53 to 128 nucleotides. We show that our approach (i) improves the accuracy of canonical base pair predictions, (ii) identifies the best secondary structures in a pool of sub-optimal structures, and (iii) predicts accurate 3D structures of large RNA molecules. RNA-MoIP is publicly available at: http://csb.cs.mcgill.ca/RNAMoIP

In this paper, which maps ERα binding via ChIP-seq in tumour tissue from twenty ER+ breast cancer patients, we develop a novel technique for quantitative differential analysis of protein/DNA binding events, identifying ERα sites significantly differentially bound between good prognosis patients vs. those with poor prognosis and metastases. Gene signatures that predict clinical outcome in ER+ disease, validated in publically available breast cancer gene expression datasets, are derived from these sites. These signatures are enriched for genes with relevant proximal cis-regulatory events. Statistical characterization of differentially bound ERα sites enables further downstream analysis, including identification of a differentially enriched motif for the transcription factor FoxA1. Focusing our analysis on differential binding in primary tumour material allows us to show distinct combinations of cis-regulatory elements linked with the different clinical outcomes. These techniques are applicable to other cancers (and indeed other diseases) where master transcription factor regulators are known.

The conventional approach to drug discovery of “one drug – one target – one disease” is insufficient, especially for complex diseases. This inadequacy is partially addressed by accepting the notion of polypharmacology – one drug is likely to bind to multiple targets with varying affinity. However, to identify proteome-wide multiple targets for a drug is a complex and challenging task. We have developed a structural systems biology approach to quantitatively predict potential off-targets for known drugs. This method is applied to identify human off-targets for Nelfinavir, an antiretroviral drug with anti-cancer behavior. We propose inhibition by Nelfinavir of multiple protein kinases. We suggest that broad-spectrum low affinity binding by a drug or drugs to multiple targets may lead to a collective effect important in treating complex diseases such as cancer.

Motivation: Systematic Evolution of Ligands by EXponential Enrichment (SELEX) represents a state of the art technology to isolate single stranded (ribo)nucleic acid fragments, named aptamers, that bind to a molecule (or molecules) of interest via specific structural regions induced by their sequence dependent fold. This powerful method has applications in designing protein inhibitors, molecular detection systems, therapeutic drugs, and antibody replacement among others. However, full understanding and consequently optimal utilization of the process has lagged behind it's wide application due to the lack of dedicated computational approaches. At the same time the combination of SELEX with novel sequencing technologies is beginning to provide the data that will allow the examination of a variety of properties of the selection process. Results: To close this gap we developed, Aptamotif, a computational method for the identification of sequence-structure motifs in SELEX derived aptamers. To increase the chances of identifying functional motifs, Aptamotif uses an ensemble based approach. Our new algorithmic solutions are accompanied with rigorous statistical analysis. We validated the method using two published aptamer datasets containing experimentally determined motifs of increasing complexity. We were able to recreate the authors findings to a high degree, thus proving the capability of our approach to identify binding motifs in SELEX data. Additionally, using our new experimental dataset, we illustrate the application of Aptamotif to elucidate several properties of the selection process.

The goal of network inference is to generate testable hypotheses of gene-to-gene influences and subsequently design bench experiments to confirm network predictions. In [Yeung et al. 2011], we used both time-series and genetics data to infer directionality of edges in regulatory networks: time-series data contain information about the chronological order of regulatory events and genetics data allow us to map DNA variations to variations at the RNA level. We generated time-series gene-expression data profiling 95 genotyped yeast segregants subjected to a drug perturbation. We developed a Bayesian model averaging regression algorithm that incorporates external information from diverse data types to infer regulatory networks from the time-series and genetics data. Our algorithm is capable of generating feedback loops. We showed that our inferred network recovered existing and novel regulatory relationships, and discovered de novo transcription-factor binding sites. We generated independent microarray data on selected deletion mutants to prospectively test network predictions.

Cellular signaling requires that particular protein-protein interactions be tailored to each signaling cascade with either broad or narrow specificity. Understanding the structural code for such selectivity is a major goal in signal transduction research, as well as in drug design. Yet, beyond single representative examples, little is known of how specificity is determined among large protein families, including those involved in signal transduction.

The talk will present a “bottom-up” approach to decipher interaction specificity, using G-protein signaling as a model system. This approach integrates experimental and structure-based energy calculations to map specificity determinants at the protein family level. The resulting residue-level maps are then used to redesign proteins with altered activities and specificities, offering new insights into G-protein signaling and paving the way for the rewiring of signaling networks at the cellular level.

Motivation: Clustering according to sequence-structure similarity has now become a generally accepted scheme for ncRNA annotation. Its application to complete genomic sequences as well as whole transcriptomes is therefore desirable but hindered by extremely high computational costs. Results: We present a novel linear-time, alignment-free method for comparing and clustering RNAs according to sequence and structure. The approach scales to datasets of hundreds of thousands of sequences. The quality of the retrieved clusters has been benchmarked against known ncRNA datasets and is comparable to state-of-the-art sequence-structure methods although achieving speed-ups of several orders of magnitude. A selection of applications aiming at the detection of novel structural non-coding RNAs are presented. Exemplarily, we predicted local structural elements specific to lincRNAs likely functionally associating involved transcripts to vital processes of the human nervous system. In total, we predicted 349 local structural RNA elements.

Identification of DNA motifs from ChIP-seq/ChIP-chip [chromatin immunoprecipitation (ChIP)] data is a powerful method for understanding the transcriptional regulatory network. Here we propose a new k-mer occurrence model to reflect the fact that functional DNA k-mers often cluster around ChIP peak summits. With this model, we introduced a new measure to discover functional k-mers. Using simulation, we demonstrated that our method is more robust against noises in ChIP data than available methods. A novel word clustering method is also implemented to group similar k-mers into position weight matrices (PWMs). Our method was applied to a diverse set of ChIP experiments to demonstrate its high sensitivity and specificity. Importantly, our method is much faster than several other methods for large sample sizes.

We present an approach that integrates protein structure analysis and text mining for protein functional site prediction, called LEAP-FS (Literature Enhanced Automated Prediction of Functional Sites). The structure analysis was carried out using Dynamics Perturbation Analysis (DPA), which predicts functional sites at control points where interactions greatly perturb protein vibrations. The text mining extracts mentions of residues in the literature, and predicts that residues mentioned are functionally important. We assessed the significance of each of these methods by analyzing their performance in finding known functional sites in about 100,000 publicly available protein structures. The overlap of predictions with annotations improved when the text-based and structure-based methods agreed. Our analysis also yielded new high-quality predictions of many functional site residues. We conclude that both DPA and text mining independently provide valuable high-throughput protein functional site predictions, and that integrating the two methods using LEAP-FS further improves the quality of these predictions.

Motivations: High throughput sequencing has made it possible to sequence DNA methylation of a whole genome at the single-base resolution. A sample however may contain a number of distinct methylation patterns. For instance, cells of different types and in different developmental stages may have different methylation patterns. Alleles may be differentially methylated, which may partially explain that the large portions of epigenomes from single cell types are partially methylated, and may have ma jor effects on transcriptional output. Approaches relying on DNA sequence polymorphism to identify individual patterns from a mixture of heterogeneous epigenomes are insufficient as methylcytosines occur at a much higher density than SNPs. Results: We have developed a mixture model-based approach for resolving distinct epigenomes from a heterogeneous sample. In particular, the model is applied for the detection of allele-specific methylations (ASM). The methods are tested on a synthetic methylome and applied to an Arabidopsis single root cell methylome.

Enhancers often diverge much faster than exonic sequence. The role of gene regulatory changes in adaptation of species is one of the factors leading to the accelerated rate of enhancer sequence divergence, and the plasticity of the underlying enhancer encoding is the other contributor. We developed a computational approach capable of using DNA sequence motifs within enhancers to identify their functional orthologs when their sequence diverged beyond recognition by the classical alignment methods. Experimental validation confirmed the enhancer activity of 88% of our functional ortholog predictions. Moreover, 71% of the tested predicted functional enhancer othrolog pairs directed largely identical patterns of expression in zebrafish embryos, confirming both the sensitivity and accuracy of our method. Our study argues that motif composition is often necessary to retain and sufficient to predict regulatory function in the absence of overt sequence conservation, revealing an entire class of functionally conserved, evolutionarily diverged regulatory elements.

Identification of the residues within an antibody (Ab) that recognize and bind the antigen (Ag), which is at the heart of immunological research, is typically done using computational tools for identifying the so called Complementarity Determining Regions (CDRs). We show that CDRs identification tools miss up to 22% of the residues that actually bind the Ag. We show that essentially all antigen binding residues are located within structural consensus regions between antibodies and that these regions could be identified from sequence. Moreover, we demonstrate that Ag binding residues that fall within Ab structural consensus regions and are not identified by the most commonly used CDR identification methods, have a substantial energetic contribution to Ag binding. Finally, we suggest a computational tool for the identification of Ag binding site from Ab sequence and we show that this tool identifies 94% of the residues that actually bind the Ag.

The constellation of molecular factors leading to the emergence of the human pandemic H1N1 (pH1N1) influenza A virus in 2009 is unclear. Using a computational approach, we identified molecular determinants that may discriminate this strain from other strains. Amino acid positions discriminating pH1N1 from seasonal human strains were located in or near known antigenic sites on the hemagglutinin (HA) protein, thus camouflaging pH1N1 from immune recognition. We also detected positions in HA differentiating classical swine viruses from pH1N1. These positions were mostly located around the receptor-binding pocket, possibly influencing binding affinity to the human cell. Such alterations may be liable in part for the virus’s efficient infection and adaptation to humans. Significantly, we showed that the substitutions R133AK and R149K, predicted to be pH1N1 characteristics, each altered virus binding to erythrocytes and conferred virulence to A/swine/NC/18161/02 in mice, reinforcing the computational findings reported here.

Chromatin profiling has emerged as a powerful means of genome annotation and detection of regulatory activity. The approach is especially well suited to the characterization of non-coding portions of the genome, which critically contribute to cellular phenotypes yet remain largely uncharted. Using maps of nine chromatin marks across nine cell types we systematically characterize regulatory elements, their cell-type specificities and their functional interactions. Focusing on cell-type-specific patterns of promoters and enhancers, we define multicell activity profiles for chromatin state, gene expression, regulatory motif enrichment and regulator expression. We then link enhancers to putative target genes, and predict the cell-type-specific activators and repressors that modulate them. The resulting annotations and regulatory predictions have implications for the interpretation of genome-wide association studies. Top-scoring disease SNPs are frequently positioned within enhancer elements specifically active in relevant cell types. Our study presents a general framework for deciphering cis-regulatory connections and their roles in disease.

Computational modeling of cell behavior requires information on the spatiotemporal distribution of proteins. We previously developed the first system for automatically constructing generative models of subcellular location directly from microscope images (Zhao & Murphy, Cytometry 71A, 978-990, 2007). Those models were for 2D images, and the Peng & Murphy 2011 paper made the crucial extension to 3D. The Murphy 2011 paper described using these models for active learning of the effects of many perturbagens on many proteins. Subsequent work has integrated these approaches with generative models of microtubules into a cohesive, open source system, CellOrganizer (http://CellOrganizer.org). The system can output images as an idealized cell or as a convolved image as might have been acquired with a specific microscope. The former is suitable for use in cell simulations, while the latter is useful for testing analysis software with images for which the ground truth is known.

In eukaryotes, the ubiquitin–proteasome pathway regulates fundamental cellular processes. The 26S proteasome resides at the downstream end of the pathway and degrades defective proteins. While the structure of its 20S core particle (CP) has been determined by X-ray crystallography, the structure of the 19S regulatory particle (RP), which recruits substrates and translocates them to the CP for degradation, has remained elusive. We have revealed the entire structure of the RP and describe a completed molecular architecture of the 26S proteasome. By integrating data from cryo-electron microscopy, X-ray crystallography, residue-specific chemical cross-linking, and additional proteomics techniques, we were able to produce a more accurate and higher resolution structural model than any of the data sets alone can provide. In addition, we have identified previously unpublished protein- protein interactions. The modular structure of the proteasome provides insights into the sequence of events that occur prior to the degradation of ubiquitylated substrates.

Next generation sequencing of RNAs (RNA-Seq) has revolutionized the field of transcriptomics for genetics and medical research. De novo transcriptome assembly has become a feasible alternative for transcriptome analysis of novel model organisms, as de novo genome assembly is still a time-consuming process. De novo transcriptome assembly has other important applications for example gene-fusion detection in cancer or detection of trans-splicing events.

This talk will introduce the Oases de novo transcriptome assembler that exploits the relationship between de Bruijn Graphs and Splicing graphs to accurately model alternative gene isoforms in RNA-Seq data. The dynamic range of expression levels, alternative splicing events and repetitive sequences make de novo transcriptome assembly a challenging task and we will show how to strike the balance to deal with these overlapping problems. Further, the talk will reveal new insights into the importance of RNA-Seq data preprocessing and its’ tremendous effect on assembly performance.

Traditional proteomics analysis is plagued by the use of arbitrary thresholds resulting in large loss of information. We propose here a novel method utilizing all detected proteins. Its efficacy is demonstrated in a liver cancer proteomics screen. Utilizing biological and predicted complexes, a Proteomics Signa?ture Profile (PSP) for each patient was derived. Although consistency of individual proteins between patients is low, we found the reported proteins tend to hit clusters in a meaningful and informative manner. By extracting this information in the form of a Proteomics Signature Profile, we confirm that this information is conserved and can be used for (1) clustering of patient samples, (2) identification of significant clusters based on real biological complexes, and (3) overcoming consistency and coverage issues prevalent in proteomics data sets.

The ISA commons (www.isacommons.org) is a growing exemplar ecosystem of data curation and sharing solutions built on a common metadata tracking framework, providing tools and resources to create and manage large, heterogeneous data sets in a coherent manner, and allowing users of (parts of) data sets to ‘connect the metadata dots’. We invite new communities interested in breaching the boundary of their own biodomain to join the growing ISA network to empower ever more scientists to take data management, biocuration and sharing into their own hands, using community standards while remaining blissfully unaware of the underlying complexities of the implementation of those standards.

Motivation: Alignment errors are still the main bottleneck of current template-based protein modeling (TM) methods including protein threading and homology modeling, especially when the sequence identity between two proteins under consideration is low (<30%). Results: We present a novel protein threading method for much more accurate sequence-template alignment by employing a probabilistic graphical model Conditional Neural Fields (CNF), which aligns one protein sequence to its remote template using a nonlinear scoring function. This scoring function can account for correlation among a variety of protein sequence and structure features, make use of information in the neighborhood of two residues to be aligned, and thus, is much more sensitive than the widely-used linear function or profile-based scoring function. To train this CNF threading model, we employ a novel quality-sensitive method that can directly maximize the expected quality of a set of training alignments, instead of the standard maximum-likelihood method. Experimental results show that our CNF method generates significantly better alignments than the best profile-based and threading methods on several public (but small) benchmarks and very large in-house datasets. Our method outperforms others regardless of protein classes and lengths and works particularly well for proteins with sparse sequence profile due to the effective utilization of structure information. The methodology presented here can also be adapted to protein sequence alignment.

Genetic differences between Arabidopsis thaliana accessions underlie the plant's extensive phenotypic variation, and until now these have been interpreted largely in the context of the annotated reference accession Col-0. Here we report the sequencing, assembly and annotation of the genomes of 18 natural A. thaliana accessions, and their transcriptomes. When assessed on the basis of the reference annotation, one-third of protein-coding genes are predicted to be disrupted in at least one accession. However, re-annotation of each genome revealed that alternative gene models often restore coding potential. Gene expression in seedlings differed for nearly half of expressed genes and was frequently associated with cis variants within 5 kilobases, as were intron retention alternative splicing events. Sequence and expression variation is most pronounced in genes that respond to the biotic environment. Our data further promote evolutionary and functional studies in A. thaliana, especially the MAGIC genetic reference population descended from these accessions.

The structural elucidation of organic compounds in complex biofluids and tissues remains a significant challenge. For mass spectrometry, the manual interpretation of tandem mass spectra is cumbersome and requires expert knowledge, as the fragmentation mechanisms of small molecules are not completely understood. Thus, the automated identification of compounds is generally limited to searching in spectral libraries.
We have developed a fully automated pipeline for the identification of truly unknown compounds. First, it annotates the spectra with fragmentation trees, and then compares these trees via tree aligment. This allows for the retrieval of similar compounds from a reference library, even if it contains spectra from a different instrument type. A decoy database strategy enables FDR calculation. In addition, clustering based on tree similarities agrees well with known compound classes. This allows for a basic identification of unknown metabolites in an high-throughput setup.

We have determined the three-dimensional (3D) architecture of the Caulobacter crescentus genome by combining genome-wide chromatin interaction detection, live-cell imaging, and computational modeling. Using chromosome conformation capture carbon copy (5C), we derive around 13 kb resolution 3D models of the Caulobacter genome. The resulting models illustrate that the genome is ellipsoidal with periodically arranged arms. The parS sites, a pair of short contiguous sequence elements known to be involved in chromosome segregation, are positioned at one pole, where they anchor the chromosome to the cell and contribute to the formation of a compact chromatin conformation. Repositioning these elements resulted in rotations of the chromosome that changed the subcellular positions of most genes. Such rotations did not lead to large-scale changes in gene expression, indicating that genome folding does not strongly affect gene regulation. Collectively, our data suggest that genome folding is globally dictated by the parS sites and chromosome segregation.

Chimeric RNA transcripts are generated by different mechanisms, including pre-mRNA trans-splicing, chromosomal translocation and/or gene fusion, and it was recently shown that at least some chimeric transcripts may be translated into functional chimeric proteins. To gain a better understanding of the design principles behind the production of chimeric proteins, we have analyzed 7,424 chimeric RNAs from humans. We focused on the specific domains present in these proteins, comparing their permutations with those of known human proteins. We found that chimeras contain complete protein domains more often than in random datasets and specifically, that eight different types of domains are over represented among all chimeras, as well as in those chimeras confirmed by RNA-seq experiments. Moreover, we discovered that some chimeras potentially encode proteins with novel and unique combinations of such domains. Given the prevalence of complete protein domains observed in chimeras, we predict that putative chimeras that lack activation domains may actively compete with their parental proteins, thereby exerting a dominant negative effect. In more general terms, the generation of chimeric transcripts produces a combinatorial increase in the number of protein products available, which may disturb the function of parental genes and influence their protein-protein interaction network.

Motivation: Shotgun sequence read data derived from xenograft material contains a mixture of reads arising from the host and reads arising from the graft. Classifying the read mixture to separate the two allows for more precise analysis to be performed. Results: We present a technique, with an associated tool Xenome, which performs fast, accurate and specific classification of xenograft derived sequence read data. We have evaluated it on RNA-Seq data from human, mouse and human-in-mouse xenograft data sets. Availability: Xenome is available for non-commercial use from http://www.nicta.com.au/bioinformatics

Mass spectrometry allows sensitive, automated and high- throughput analysis of small molecules such as metabolites. One major bottleneck in metabolomics is the identification of "unknown" small molecules not in any database. Recently, fragmentation tree alignments have been introduced for the automated comparison of the fragmentation patterns of small molecules. Fragmentation pat- tern similarities are strongly correlated with the chemical similarity of molecules, and allow us to cluster compounds based solely on their fragmentation patterns. Aligning fragmentation trees is computationally hard. Nevertheless, we present three exact algorithms for the problem: A dynamic pro- gramming (DP) algorithm, a sparse variant of the DP, and an Integer Linear Program (ILP). Evaluation of our methods on three different datasets showed that thousands of alignments can be computed in a matter of minutes using DP, even for "challenging" instances. Run- ning times of the sparse DP were an order of magnitude better than for the classical DP. The ILP was clearly outperformed by both DP approaches. We also found that for both DP algorithms, computing the 1 % slowest alignments required as much time as computing the 99 % fastest.

Motivation: Computational identification of genomic structural variants via high throughput sequencing is an important problem for which a number of highly sophisticated solutions have been developed recently. With the advent of high-throughput transcriptome sequencing (RNA-Seq), the problem of identifying structural alterations in the transcriptome is now attracting significant attention. In this paper, we introduce two novel algorithmic formulations for identifying transcriptomic structural variants through aligning transcripts to the reference genome under the consideration of such variation. The first formulation is based on a nucleotide-level alignment model; a second, potentially faster formulation is based on chaining fragments shared between each transcript and the reference genome. Based on these formulations, we introduce a novel transcriptome-to-genome alignment tool, Dissect, which can identify and characterize transcriptomic events such as duplications, inversions, rearrangements and fusions. Dissect is suitable for whole transcriptome structural variation discovery problems involving sufficiently long reads or accurately assembled contigs.

Motivation: Molecular Recognition Feature (MoRF) regions are disordered binding sites that become structured upon binding. MoRFs are implicated in important biological processes, including signaling and regulation. However, only a limited number of experimentally validated MoRFs is known, which motivates development of computational methods that predict MoRFs from protein chains. Results: We introduce a new MoRF predictor, MoRFpred, which identifies all MoRF types (alpha, beta, coil, and complex). We develop a comprehensive dataset of annotated MoRFs and use it to build and empirically compare our method. MoRFpred is based on a novel design in which annotations generated by sequence alignment are fused with predictions generated by a Support Vector Machine (SVM), which uses a custom designed set of sequence-derived features. The features provide information about evolutionary pro-files, selected physiochemical properties of amino acids, and predicted disorder, solvent accessibility, and B-factors. Empirical evaluation shows that MoRFpred statistically significantly outperforms existing predictors, alpha-MoRF-Pred and ANCHOR, by 0.07 in AUC and 10% in success rate. We show that our predicted (new) MoRF regions have non-random sequence similarity with native MoRFs. We use this observation along with the fact that predictions with higher probability are more accurate to identify putative MoRF regions. We present case studies to analyze these putative MoRFs. We also identify a few sequence-derived hallmarks of MoRFs. They are characterized by dips in the disorder predictions and higher hydrophobicity and stability when compared to adjacent (in the chain) residues. Availability: http://biomine.ece.ualberta.ca/MoRFpred/ Supplementary information: http://biomine.ece.ualberta.ca/MoRFpred/Supplement.pdf Contact: lkurgan@ece.ualberta.ca

I will present our recent work on reconstructing ancient biological networks. We have developed several methods for recovering interactions between molecules that were present in ancestral species, starting with only the present-day networks that we are able to measure. We have shown that, using these algorithms, ancestral interactions can be inferred with high accuracy. I will discuss several applications of these approaches, including predicting missing interactions between present-day viral proteins, identifying functionally related proteins, and modeling how protein complexes have rewired over time in yeast.

ChIPseq technology has become the state-of-the-art whole-genome technique for analyzing protein-DNA interactions, making it necessary to have rigorous methods for quantifying similarity between datasets, and defining interactions among chromatin features. This presents a statistical problem for which several solutions have been proposed.
While other methods for obtaining significance of similarity must make somewhat arbitrary choices of distance metrics, parametric distributions, or procedures for simulating the null hypothesis, we present a simple and intuitive approach for calculating exact p-values that is essentially assumption-free. Our approach is robust to non-biological variations and involves an asymmetric comparison, allowing one to tease out hierarchical relationships among chromatin proteins.

Motivation: Ontologies are an everyday tool in biomedicine to capture and represent knowledge. However, many ontologies lack a high degree of coverage in their domain and need to improve their overall quality and maturity. Automatically extending sets of existing terms will enable ontology engineers to systematically improve text- based ontologies level by level. Results: We developed an approach to extend ontologies by discovering new terms which are in a sibling relationship to existing terms of an ontology. For this purpose, we combined two approaches which retrieve new terms from the web. The first approach extracts siblings by exploiting the structure of HTML documents, whereas the second approach uses text mining techniques to extract siblings from unstructured text. Our evaluation against MeSH shows that our method for sibling discovery is able to suggest first-class ontology terms and can be used as an initial step towards assessing the completeness of ontologies. The evaluation yields a recall of 80% at a precision of 61% where the two independent approaches are complementing each other. For MeSH in particular, we show that it can be considered complete in its medical focus area. We integrated the work into DOG4DAG, an ontology generation plugin for the editors OBO-Edit and Protégé, making it the first plugin that supports sibling discovery on-the-fly. Availability: Sibling discovery for ontology is available as part of DOG4DAG (www.biotec.tu-dresden.de/research/schroeder/dog4dag) for both Proteégé 4.1 and OBO-Edit 2.1.

Recognition models for protein-DNA interactions, which allow the prediction of specificity for a DNA-binding domain based only on its sequence or the alteration of specificity through rational design, have long been a goal of computational biology. There has been some progress in constructing useful models, especially for C2H2 zinc finger proteins, but it remains a challenging problem with ample room for improvement. For most families of transcription factors the best available methods utilize k-nearest neighbor algorithms to make specificity predictions based on the average of the specificities of the k most similar proteins with defined specificities. Homeodomain proteins are the second most abundant family of transcription factors, after zinc fingers, in most metazoan genomes, and as a consequence an effective recognition model for this family would facilitate predictive models of many transcriptional regulatory networks within these genomes. Using extensive experimental data, we have tested several machine learning approaches and find that both support vector machines and random forests can produce recognition models for homeodomain proteins that are significant improvements over k-nearest neighbor based methods. Cross-validation analyses show that the resulting models are capable of predicting specificities with high accuracy. We have produced a web-based prediction tool, PreMoTF (Predicted Motifs for Transcription Factors) (http://stormo.wustl.edu/PreMoTF), for predicting PFMs from protein sequence using a random forest based model.

General properties of the largely antagonistic biomolecular interactions between pathogens and their hosts remain poorly understood, and may differ significantly from known principles governing the cooperative interactions within the host. Recent host-pathogen systems biology efforts have generated global, but low-resolution, maps of host-pathogen protein-protein interaction networks. Here, we integrate three-dimensional homology models of protein complexes with interaction networks among human and viral proteins to construct the first human-virus structural interaction network. Subsequent analyses reveal significant biophysical, functional, and evolutionary differences between host-virus and within-host structural interaction networks. We find that viral proteins tend to bind to existing within-host interfaces. Compared to within-host protein-protein interfaces, host-virus protein-protein interfaces tend to be more transient, targeted by more host proteins, more regulatory in function, faster evolving, and rely less on sequence similarity to achieve interface mimicry. These results highlight the distinct consequences of cooperation versus antagonism in biological networks within and between species.

The understanding of the genetic determinants of complex disease is undergoing a paradigm shift. Genetic heterogeneity of rare mutations with deleterious effects is more commonly being viewed as a major component of disease. Autism is an excellent example where research is active in identifying matches between the phenotypic and genomic heterogeneities. A substantial portion of autism appears to be correlated with copy number variation which is not directly probed by single nucleotide polymorphism (SNP) array technologies. Identifying the genetic heterogeneity of small deletions remains a major unresolved computational problem due, in part, to the inability of algorithms to detect them. In this paper we present an algorithmic framework, which we term DELISHUS, that implements three highly efficient algorithms for inferring genomic deletions of all sizes and frequencies in SNP array data. We implement a polynomial-time backtracking algorithm -- that finishes on a 1 billion entry genome-wide association study (GWAS) SNP matrix in a few minutes -- to compute all potential deletions in a dataset. Given a set of called deletions, we also give a polynomial time algorithm for detecting regions that contain multiple recurrent deletions. Finally, we give an algorithm for detecting de novo deletions. Because our algorithms consider all individuals in the sample at once, they achieve significantly lower false positive rates and higher power when compared to previously published single individual algorithms. Our method may be used to identify the deletion spectrum for GWAS where deletion polymorphism was previously not analyzed. DELISHUS is available at http://www.brown.edu/Research/Istrail_Lab/

Motivation: The recent development of high-throughput drug profiling (high content screening or HCS) provides a large amount of quantitative multidimensional data. Despite its potentials, it poses several challenges for academia and industry analysts alike. This is especially true for ranking the effectiveness of several drugs from many thousands of images directly. This paper introduces, for the first time, a new framework for automatically ordering the performance of drugs, called fractional adjusted bi-partitional score (FABS). This general strategy takes advantage of graph-based formulations and solutions and avoids many shortfalls of traditionally used methods in practice. We experimented with FABS framework by implementing it with a specific algorithm, a variant of normalized cut – normalized cut prime (FABS-NC′), producing a ranking of drugs. This algorithm is known to run in polynomial time and therefore can scale well in high-throughput applications.

Results: We compare the performance of FABS-NC′ to other methods that could be used for drugs ranking. We devise two variants of the FABS algorithm: FABS-SVM that utilizes support vector machine (SVM) as black box, and FABS-Spectral that utilizes the eigenvector technique (spectral) as black box. We compare the performance of FABS-NC′ also to three other methods that have been previously considered: center ranking (Center), PCA ranking (PCA), and graph transition energy method (GTEM). The conclusion is encouraging: FABS-NC′ consistently outperforms all these five alternatives. FABS-SVM has the second best performance among these six methods, but is far behind FABS-NC′: In some cases FABSNC ′ produces over half correctly predicted ranking experiment trials than FABS-SVM.

Availablility: The system and data for the evaluation reported here will be made available upon request to the authors after this manuscript is accepted for publication.

Motivation: Two types of transmembrane proteins exist, alpha-helical membrane proteins and transmembrane beta-barrels. The later type exists in the outer membrane of gram-negative bacteria and in chloroplast and mitochondria where they play a major role in the translocation machinery. Here, we aim to build three-dimensional models for transmembrane beta-barrels based on a large set of predicted topologies used to generate alternative three-dimensional models.Thereafter, the predicted Z-coordinate, i.e. the distance of a residue from the membrane center, is used to identify the best model.

Results: We present TMBMODEL; a method for generating three-dimensional models based on predicted topologies. TMBMODEL employs theoretic principles from known structures to construct a model for a barrel of a given transmembrane beta-barrel sequence. Firstly, different topologies are obtained from running the BOCTOPUS topology predictor and then three-dimensional models are constructed for different shear numbers. The best model is then selected based on a novel Z-coordinate predictor. Based on a leave-one-out cross-validation, the Z-coordinate predictor predicts 74% residues within 2 Å on a non-redundant dataset of 36 transmembrane beta-barrels. The average error and correctly identified membrane residues is 1.61 Å and 71%, respectively. TMBMODEL chose the correct topology for 75% proteins in the data set, which is a slight improvement over BOCTOPUS. More importantly TMBMODEL provides a C-alpha template for more detailed structural analysis. The average RMSD for this template is 7.24 Å.

Availability: TMBMODEL is freely available as a web-server at: http://tmbmodel.cbr.su.se/. The data sets used for training and evaluations are also available from this site.

Contact: arne@bioinfo.se

Abbreviations: TMB, transmembrane beta-barrel protein; HMM, Hidden
Markov Model; SVM, support vector machine.

HIV Dependency Factors (HDFs) are human proteins that are essential for HIV replication, but are not lethal to the host cell when silenced. Three genome-wide RNAi experiments identified HDF sets with little overlap. We discuss how we combined these three datasets with a human PPI network to predict new HDFs, using an algorithm called SinkSource and four other algorithms published in the literature. A number of HDFs that we predicted are known to interact with HIV proteins. Many predicted HDF genes showed significantly different programs of expression in early response to SIV infection in two non-human primate species that differ in AIDS progression. Our results suggest that many HDFs are yet to be discovered and that they have potential value as prognostic markers of AIDS development.

We conclude with recent results on predicting dependency factors for multiple viruses, in an effort to discover human proteins that may serve as broad-spectrum drug targets for infectious diseases.

Motivation: Assemblies of next generation sequencing data, while accurate, still contain a substantial number of errors that need to be corrected after the assembly process. We develop SEQuel, a tool that corrects errors (i.e., insertions, deletions, and substitution errors) in the assembled contigs. Fundamental to the algorithm behind SEQuel is the positional de Bruijn graph, a graph structure that models k-mers within reads while incorporating the approximate positions of reads into the model. Results: SEQuel reduced the number of small insertions and deletions in the assemblies of standard multi-cell E. coli data by almost half, and corrected between 30% and 94% of the substitution errors. Further, we show SEQuel is imperative to improving single-cell assembly, which is inherently more challenging due to higher error rates and non-uniform coverage; over half of the small indels, and substitution errors in the single-cell assemblies were corrected. We apply SEQuel to the recently-assembled Deltaproteobacterium SAR324 genome, which is the first bacterial genome with a comprehensive single-cell genome assembly, and make over 800 changes (insertions, deletions and substitutions) to refine this assembly. Availability: SEQuel can be used as a post-processing step in combination with any NGS assembler and is freely available at http://bix.ucsd.edu/SEQuel/.

We present DACTAL, a method for phylogeny estimation that produces trees from unaligned sequence datasets without ever needing to estimate an alignment on the entire dataset. DACTAL combines iteration with a novel divide-and-conquer approach, so that each iteration begins with a tree produced in the prior iteration, decomposes the taxon set into overlapping subsets, estimates trees on each subset, and then combines the smaller trees into a tree on the full taxon set using a new supertree method. We prove that DACTAL is guaranteed to produce the true tree under certain conditions. We compare DACTAL to SATe and maximum likelihood trees on estimated alignments using simulated and real datasets with 1000 to 27,643 taxa. Our studies show that DACTAL dramatically outperforms two-phase methods with respect to tree accuracy. The comparison to SAT\{e} shows that both have the same tree accuracy, but that DACTAL achieves this accuracy in a fraction of the time. Furthermore, DACTAL can analyze larger datasets than SAT\'{e}, including a dataset with almost 28,000 sequences.

DACTAL source code is available at www.cs.utexas.edu/users/phylo/software/dactal

Motivation: Secondary structure underpins the folding pattern and architecture of most proteins. Accurate assignment of the secondary structure elements is therefore an important problem. Although many approximate solutions of the secondary structure assignment problem exist, the statement of the problem has resisted a consistent and mathematically rigorous definition. A variety of comparative studies have highlighted major disagreements in the way the available methods define and assign secondary structure to coordinate data. Results: We report a new method to infer secondary structure based on the Bayesian method of Minimum Message Length (MML) inference. It treats assignments of secondary structure as hypotheses that explain the given coordinate data. The method seeks to maximise the joint probability of a hypothesis and the data. There is a natural null hypothesis and any assignment that cannot better it is unacceptable. We developed a program SST based on this approach and compared it to popular programs such as DSSP and STRIDE amongst others. Our evaluation suggests that SST gives reliable assignments even on low resolution structures.

Motivation: Despite the rapid decline in sequencing costs, sequencing large cohorts of individuals is still prohibitively expensive. Recently, several sophisticated pooling designs were suggested that can identify carriers of rare alleles in large cohorts with a significantly smaller number of pools, thus dramatically reducing the cost of such large scale sequencing projects (Erlich et al. 2009). These approaches use combinatorial pooling designs where each individual is either present or absent from a pool. One can then infer the number of carriers in a pool, and by combining information across pools, reconstruct the identity of the carriers. Results: We show that one can gain further efficiency and cost reduction by using "weighted" designs, in which different individuals donate different amounts of DNA to the pools. Intuitively, in this situation the number of mutant reads in a pool does not only indicate the number of carriers, but also their identity. We describe and study a powerful example of such weighted designs, using non-overlapping pools. We demonstrate that this approach is not only easier to implement and analyze but is also competitive in terms of accuracy with combinatorial designs when identifying rare variants, and is superior when sequencing common variants. We then discuss how weighting can be incorporated into existing combinatorial designs to increase their accuracy and demonstrate the resulting improvement using simulations. Finally, we argue that weighted designs have enough power to facilitate detection of common alleles, so they can be used as a cornerstone of whole-exome sequencing projects.

Despite significant progress in the molecular understanding of medulloblastoma, stratification of risk in patients remains a challenge. Focus has shifted from clinical parameters to molecular markers, such as expression of specific genes and selected genomic abnormalities, to improve accuracy of treatment outcome prediction. Here, we show how integration of high-level clinical and genomic features or risk factors, including disease subtype, can yield more comprehensive, accurate, and biologically interpretable prediction models for relapse versus no-relapse classification. We also introduce a novel Bayesian nomogram indicating the amount of evidence that each feature contributes on a patient-by-patient basis.

Chemical-Protein Interactome is a computational methodology with a focus on characterizing differential drug efficacy and side effects through the combined analysis of genetic polymorphisms and their impact on chemical-protein interactions and gene expression perturbations. The methodology opens opportunities for developing patient-specific medication in terms of decreasing adverse drug reactions and broadening new uses for old drugs.

Genomic innovation is thought to be mediated by slow accumulation of uncorrelated mutations. Here, we show that mammalians utilized an antiviral mechanism to accelerate their genome evolution by large-scale, parallel editing of their retrotransposons. We found thousands of clusters of G-to-A mismatches between pairs of retrotransposon sequences, indicating massive editing of retrotransposons prior to their integration. Such clusters are the hallmark of the activity of APOBEC3, a potent antiretroviral protein family with cytidine deamination function. We found DNA editing to span many mammalian genomes and retrotransposon families, as well as human-specific elements. Since DNA editing simultaneously generates a large number of mutations, each affected element can begin its evolutionary trajectory from a unique starting point, thereby increasing the probability of developing a novel function.

The large number of single-nucleotide polymorphisms (SNP) from genome-wide association studies (GWAS) that implicate non-coding regions in human disease poses the important challenge of interpreting their molecular mechanisms of action, needed for drug targets and therapeutics. Comparison of many related genomes has emerged as a powerful lens for genome interpretation, which complements large-scale experimental datasets of gene and genome activity by providing information on selective pressures for functional nucleotides. We have used the comparative analysis of 29 eutherian genomes to provide a high-resolution map of selective constraint in the human genome, revealing 3 million novel elements, and used distinct evolutionary signatures and chromatin information to suggest their candidate functions. We have further automated their use for interpreting disease-associated regions, by exploiting the population-specific linkage disequilibrium (LD) structure from the 1000 Genomes Project, to facilitate development of mechanistic hypotheses of the impact of non-coding variants on clinical phenotypes and normal variation.

We integrated small molecule bioactivity data and homology information and compared small molecule binding between pairs of human paralogs and also between curated pairs of human to rat orthologs. To account for noise in the data set, we further compared measurements of the same ligand and target in different assays. We found that differences in small molecule binding between human paralogs are greater than the assay sample error. In contrast, differences between human to rat orthologs are no greater than the sample error. We then analyzed, for pairs of human paralogs, the relationship between sequence identity and differences in small molecule binding. For a subset of the data, differences in small molecule binding are greater for pairs with more divergent sequences. We conclude that small molecule binding between human to rat orthologs is largely conserved while selectivity of small molecule binding was observed between pairs of human paralogs.

According to the “ortholog conjecture”, orthologous proteins are expected to retain function more often than other homologs. Several proxies for functional conservation have been used, such as GO annotations and tissue expression. We here test the ortholog conjecture using conservation of domain architecture as an alternative proxy for protein function.

We studied domain architecture conservation in orthologs and paralogs between human and 40 other species. The analysis shows that orthologs exhibit greater domain architecture conservation than paralogs, even when differences in average sequence divergence are compensated for, for homologs that have diverged beyond a certain threshold.

Our results support the hypothesis that function conservation between orthologs demands higher domain architecture conservation than other types of homologs, relative to primary sequence conservation. This supports the notion that orthologs are functionally more similar than other types of homologs at the same evolutionary distance.

Motivation: In cancer genomes, chromosomal regions harboring cancer genes are often subjected to genomic aberrations like copy number alteration and loss of heterozygosity (LOH). Given this, finding recurrent genomic aberrations is considered an apt approach for screening cancer genes. Although several permutation-based tests have been proposed for this purpose, none of them are designed to find recurrent aberrations from the genomic data set without paired normal sample controls. Their application to unpaired genomic data may lead to false discoveries, because they retrieve pseudo-aberrations that exist in normal genomes as polymorphisms. Results: We develop a new parametric method named parametric aberration recurrence test (PART) to test for the recurrence of genomic aberrations. The introduction of Poisson-binomial statistics allow us to compute small p-values more efficiently and precisely than the previously proposed permutation-based approach. Moreover, we extended PART to cover unpaired data (PART-up) so that there is a statistical basis for analyzing unpaired genomic data. PART-up utilizes information from unpaired normal sample controls to remove pseudo-aberrations in unpaired genomic data. Using PART-up, we successfully predict recurrent genomic aberrations in cancer cell line samples whose paired normal sample controls are unavailable. This paper thus proposes a powerful statistical framework for the identification of driver aberrations, which would be applicable to ever-increasing amounts of cancer genomic data seen in the era of next generation sequencing.

In the development of cellular tissues, not only growth factors play a role, but also the structural environment. With material surfaces shown to affect stem cell fate, new avenues are opening for improving the biological performance of (implant) surfaces used in the human body. In the present study, we developed a chip, allowing us to chart cell – surface topography interactions in high-throughput. Human mesenchymal stromal cells (hMSCs) were grown on the chips, and using high-content imaging, each individual cell response was measured. The results reveal formerly unknown surface topographies that are able to induce MSC proliferation or osteogenic differentiation. Moreover, using machine learning techniques, we correlate parameters of the surface designs to cellular responses, yielding new insight into surface design criteria, and enabling us to predict the performance of untested surfaces.

Ample of studies focuses on the exchange of genetic material between viruses and cellular hosts. The common view claims that along the evolutionary history (bacteria to humans), viruses have shaped the host genomes. We will present evidence that, in addition to codon usage adaptation (Bahir et al. MSB 5:311), shaping viral proteomes is executed by ‘stealing and refinement’ of genetic material from the host. Tracing such events is challenging as the origin of the sequences is masked by viruses’ high mutation rate. We will present evidence for “stolen” genetic material from metazoan hosts to their viruses. For about 75% of the cross-taxa families, viral proteins are significantly shorter than their counterpart host proteins. We expose instances for active trimming of domain tails, and removal of internal domains by viruses. The inventory of viral stolen proteins provides insights on the overlooked intimacy of viruses and their multicellular hosts.

Complex diseases, such as Type 2 Diabetes Mellitus (T2D), result from the interplay of both environmental and genetic factors. However, most studies either investigate either the genetics or the environment in context of disease and there are a few that study their possible interaction. One key challenge in documenting interactions between genes and environment includes choosing which of each to test jointly. Here, we attempt to address this challenge through a data-driven integration of epidemiological and toxicological studies. Specifically, we derive lists of candidate interacting genetic and environmental factors by integrating findings from genome-wide and environment-wide association studies (GWAS and EWAS). Next, we search for evidence of toxicological relationships between these genetic and environmental factors that may have an etiological role in the disease. We illustrate our method by selecting candidate interacting factors for Type 2 Diabetes.

Motivation: Recent advances in brain imaging and high-throughput genotyping techniques enable new approaches to study the influence of genetic and anatomical variations on brain functions and disorders. Traditional association studies typically perform independent and pairwise analysis among neuroimaging measures, cognitive scores, and disease status, and ignore the important underlying interacting relationships between these units. Results: To overcome this limitation, in this paper, we propose a new sparse multi-modal multi-task learning method to reveal complex relationships from gene to brain to symptom. Our main contributions are three-fold: 1) utilizing a joint classification and regression learning model to identify disease-sensitive and cognition-relevant biomarkers; 2) introducing combined structured sparsity regularizations into multimodal multi-task learning to integrate heterogenous imaging genetics data and identify multi-modal biomarkers; 3) deriving a new efficient optimization algorithm to solve our non-smooth objective function and providing rigorous theoretical analysis on the global optimum convergency. Using the imaging genetics data from the Alzheimer’s Disease Neuroimaging Initiative database, the effectiveness of the proposed method is demonstrated by clearly improved performance on predicting both cognitive scores and disease status. The identified multi-modal biomarkers could predict not only disease status but also cognitive function to help elucidate the biological pathway from gene to brain structure and function, and to cognition and disease.

Motivation: Gene family evolution is driven by evolutionary events like speciation, gene duplication, horizontal gene transfer, and gene loss, and inferring these events in the evolutionary history of a given gene family is a fundamental problem in comparative and evolutionary genomics with numerous important applications. Solving this problem requires the use of a reconciliation framework, where the input consists of a gene family phylogeny and the corresponding species phylogeny, and the goal is to reconcile the two by postulating speciation, gene duplication, horizontal gene transfer, and gene loss events. This reconciliation problem is referred to as Duplication-Transfer-Loss (DTL) reconciliation and has been extensively studied in the literature. Yet, even the fastest existing algorithms for DTL-reconciliation are too slow for reconciling large gene families and for use in more sophisticated applications such as gene tree or species tree reconstruction. Results: We present two new algorithms for the DTL-reconciliation problem that are dramatically faster than existing algorithms, both asymptotically and in practice. We also extend the standard DTL-reconciliation model by considering distance-dependent transfer costs, that allow for more accurate reconciliation, and give an efficient algorithm for DTL-reconciliation under this extended model. We implemented our new algorithms and demonstrate up to 100,000-fold speed-up over existing methods, using both simulated and biological datasets. This dramatic improvement makes it possible to use DTL-reconciliation for performing rigorous evolutionary analyses of large gene families, and enables its use in advanced reconciliation-based gene and species tree reconstruction methods.