Abstracts

Jonathan Carlson, Carl Kadie and D. Heckerman: Identifying the effects of human immune pressure on the evolution of HIV

An important open question in HIV vaccine design is how much of HIV's mutation is a predictable response to the selection pressure imposed by the human immune system. If mutation is heavily influenced by immune pressure, following predictable escape routes, then we can then use these predictable escape routes to design a vaccine payload that pre-trains the immune system to recognize and block these paths. In this work, we concentrate on HIV's response to selection pressure from the cellular arm of the immune system. Identification of predictable escape paths are facilitated by two facts. One, the HLA-I system is highly diverse-in particular, there are hundreds of A, B, and C HLA-I alleles; and each of us have at least one and at most two of each allele. Two, an epitope that can be presented by one HLA-I molecule can usually not be presented by another. Thus, if selection pressure from the cellular arm is substantial, the HIV escapes (point mutations) that we see in one individual are likely to be different from those we see in another individual. By identifying correlations between the presence or absence of particular HLA alleles and the presence or absence of particular HIV mutations in a population of infected people, we can identify the effects of immune pressure. Existing methods for identifying such correlations have shown that the affects of immune pressure exist but are not particularly strong. These methods, however, make the assumption that data (the observed sequences) are exchangeable. This assumption is a poor one, because the HIV sequences are related through their phylogeny (evolutionary tree). We have developed an approach that takes the phylogeny into account and have applied our approach to several real data sets. Using known epitopes as a benchmark, we find that our approach is significantly more accurate at distinguishing true from false correlations than previous methods that assume the data to be exchangeable. Furthermore, studies on synthetic data indicate that our approach is better calibrated-that is, it can estimate its false positive rate more accurately than previous methods. Most important, we use a combination of real and synthetic data to demonstrate that the amount of selection pressure from the cellular arm is much stronger than previously estimated.

A. Jaimovitch, O. Meshi and N. Friedman: Compact belief propagation: using symmetry properties in relational graphical models for efficient inference

The challenge of identifying and charecterizing the full repertoire of protein interactions in the cell is of great importance, and has recently been addressed both experimentally and computationally. We have recently used Relational Markov Random Fields (rMRFs) to integrate many data sources into a simultaneous prediction of the entire protein interaction network. A central difficulty for learning such models is performing inference, and the typical solution to this problem is to resort to approximate inference procedures, such as loopy belief propagation. Although these procedures are quite efficient, they still require computational cost on the order of the number of interactions (or features) in the model. When learning a large relational model over a complex domain, such approximations have unrealistic running time. In this paper we show that for a particular class of rMRFs which have inherent symmetry, such as our protein interaction network model, we can perform approximate inference using a template-level loopy belief propagation algorithm. We prove that this template-level algorithm yields the same results as the standard loopy belief propagation. Our new algorithm introduces a significant saving in time and space complexity as its computational cost is proportional to the size of the relational model rather than the size of the entire domain. Finally, We show how this procedure can be used to learn rMRFs for capturing the joint distribution of large protein-protein interaction networks.

Terrence Furey, Sayan Mukherjee, Gunjan Verma, Justin Guinne: Analysis of heterogeneous microarray-based data using regularized multi-task learning

High-throughput data-generation platforms have become standard tools in computational biology, but methods are needed to jointly analyze the resulting large volumes of data systematically. In this work, we seek to combine the domain information contained in gene expression and comparative genomic hybridization (CGH) data through the framework of regularized multi-task learning (MTL), and apply it to the problem of dichotomous classification of phenotype. In the MTL framework, separate tasks must share a common feature space, a challenge for cross-platform genomic analysis having distinct feature spaces. Our solution is to map expression and CGH data into a common, comparable space of gene set enrichment scores using ASSESS (http://people.genome.duke.edu/~jhg9/assess/).

Our primary goal is the elucidation of biomarkers of disease status or prognosis. We hypothesize that biomarkers identified through the MTL framework will be more robust to clinically spurious genotype heterogeneity and more fundamentally reflective of the disease process, and therefore be more clinically relevant indicators of phenotype and more pharmacologically effective targets for drug design. Preliminary results on an analysis of breast cancer data show that amongst the most salient gene sets are cancer-related pathways such as those governing mitotic cell-cycle control, NK-cell induction, and regions of known oncogenes. We note a qualitatively substantial difference between important gene sets identified in the MTL framework as contrasted with those obtained from gene expression or CGH data separately. Therefore, MTL-based biomarker discovery is achieved through a synergistic interaction between the training signals of expression and CGH data sets.

We look to extend this framework to include repeated measures time-course gene expression data and data from several possibly related disease subtypes. We also look to develop statistical tools to test our hypothesis that MTL-based biomarker discovery is superior to conventional approaches.

F. Guo, W. Fu, Y. Shi and E. P. Xing: Reverse engineering temporally rewiring gene networks

We present a probabilistic graphical model for reverse engineering temporally rewiring relevance networks from gene expression time series. Sampling-based algorithm is developed to infer the timestep-specific structure of the networks. We present empirical results on both synthetic data and Drosophila lifecycle gene expression data. Our approach makes a preliminary step to an in-depth investigation of the mechanisms and processes of network generation and rewiring in cell biology.

J.-P. Vert, J. Qiu and W. S. Noble: Metric learning pairwise kernel for graph inference

Much recent work in bioinformatics has focused on the inference of various types of biological networks, representing gene regulation, metabolic processes, protein-protein interactions, etc. A common setting involves inferring network edges in a supervised fashion from a set of high-confidence edges, possibly characterized by multiple, heterogeneous data sets (protein sequence, gene expression, etc.). Here, we distinguish between two modes of inference in this setting: direct inference based upon similarities between nodes joined by an edge, and indirect inference based upon similarities between one pair of nodes and another pair of nodes. We propose a supervised approach for the direct case by translating it into a distance metric learning problem. A relaxation of the resulting convex optimization problem leads to the support vector machine (SVM) algorithm with a particular kernel for pairs, which we call the metric learning pairwise kernel (MLPK). We demonstrate, using several real biological networks, that this direct approach often improves upon the state-of-the-art SVM for indirect inference with the tensor product pairwise kernel.

S. Lianoglou, A. Kundaje and C. Leslie: Inferring active signaling pathways by boosting the phosphorylation network

We present a novel machine learning algorithm for integrating gene expression data with kinase - substrate and protein-DNA interaction data in order to infer the activity of signaling pathways and their genome-wide regulatory effects. Our algorithmic approach combines boosting with an efficient, state-of-the-art, graph mining technique to learn subgraphs of the phosphorylome whose patterns of expression predict the differential regulation of the target genes of transcription factors.

Our algorithm was able to recover known biological information about signaling in S. cerevisiae. The PKA pathway has previously been implicated in the regulation of stress response. Our algorithm not only recovered all of the members of the cAMP-dependent PKA pathway but also found it to be associated with the regulation of targets of the stress-related transcription factors MSN4, YAP1, and HSF1.

Dana Pe'er: Genetic variation and regulatory networks: mechanisms and complexity

Sequence polymorphisms affect gene expression by perturbing the complex network of regulatory interactions. Standard methods attempt to associate each gene expression phenotype with genetic polymorphisms. We suggest a novel computational method, called Geronemo, which aims to understand the mechanism by which genetic changes perturb gene regulation. By exploiting the modularity of biological systems, Geronemo reveals regulatory relationships that are indiscernible when genes are considered in isolation, allowing the recovery of intricate combinatorial regulation. We applied Geronemo to a set of yeast recombinants generated by a cross between laboratory (BY) and wild (RM) strains of S. cerevisiae (Brem & Kruglyak, 2005), resulting in multiple novel hypotheses about genetic perturbations in the yeast regulatory network, including in transcriptional regulation, signal transduction, and chromatin modification. In this talk we will present 3 key findings:

• A significant part of the observed expression change arises from individual genetic variation of a small number of chromatin modifying factors.
• Our method uncovered a novel mRNA degradation mechanism that couples P- bodies and the Puf family of mRNA factors, which we validated experimentally.
• Based on individual gene expression in rich media, we predicts sensitivity of individuals to the drug Rapamycin, which we also validated experimentally.

N. Novershtern, A. Regev and N. Friedman: Stochastic integrative modeling of transcription regulation

Modeling the complex mechanisms by which regulatory networks control the expression of genes in response to external signals, is still a major challenge. One approach to address this complexity relies on Bayesian networks to describe the dependencies between the expression levels of many genes.

Here we present the Physical Module Networks - an integrative model that combines protein interactions, binding data and expression data into a unified framework. The model consists of two components: a "Module Network" (Segal et al, Nat Gen 2003), a Bayesian model describing modules of co- expressed genes and their shared regulation programs, and a physical interaction graph, describing protein-protein interactions and protein-DNA binding events. Both components are stochastic and can be learned from observations. To ensure the model's coherence we rely on a set of rules that define which interactions are permissible given the modules' configuration. To learn a model from data, we use a greedy heuristic that follows local changes in the modules' composition and their choice of regulators. Importantly, each change is examined simultaneously in the module network and in the interaction graph, while the target function (a Bayesian score), is being optimized.

We used the Physical Module Network to learn the physical regulatory mechanisms associated with a set of modules in the yeast stress response (Gasch et al, MBC 2000). In addition, we used a set of KO experiments (Hughes et al, Cell 2000) to reconstructed regulatory pathways between the knocked out regulators and their target genes.

M. N.Jagalur, C. Pal, E. L. Miller, R. T. Zoeller and D. Kulp: The processing and analysis of in situ gene expression images of the mouse brain

Many important high throughput projects use in situ gene expression detection technology and require the analysis of images of spatial cross sections of organisms taken at cellular level resolution. Projects creating gene expression atlases at unprecedented scales for the embryonic fruit fly as well as the embryonic and adult mouse already involve the analysis of hundreds of thousands of high resolution experimental images. We present an end-to-end approach for processing raw in situ expression imagery and performing subsequent analysis. We use a nonlinear image registration technique specifically adapted for mapping expression images to anatomical annotations and a method for extracting expression information within an anatomical region. We also present a new approach for jointly clustering the rows and columns of a matrix and we relate clustered patterns to Gene Ontology (GO) annotations. Our approach should be applicable to a variety of in situ experiments but we focus here on imagery and experiments of the mouse brain - an application with tremendous potential for increasing our fundamental understanding of neural information processing systems.

We propose a new boosting method that systematically combines graph mining and mathematical programming-based machine learning. Informative and interpretable subgraph features are greedily found by a series of graph mining calls. Due to our mathematical programming formulation, subgraph features and pre-calculated real-valued features are seemlessly integrated. We tested our algorithm on a quantitative structure-activity relationship (QSAR) problem, which is basically a regression problem when given a set of chemical compounds. In benchmark experiments, the prediction accuracy of our method favorably compared with the best results reported on each dataset.

X. Chen and M. Blanchette: Prediction of tissue-specific cis-regulatory modules using Bayesian networks and probability trees

Cis-regulatory modules (CRMs) are clusters of transcription factor (TF) b inding sites, and many are believed to be responsible for tissue-specific expression. The PReMod database [Blanchette 2006] contains more than 100,000 human CRM predictions in a genome-wide scale, but provides limited insights into their functions. In this paper, we introduce an unsupervised learning approach to predict which of these putative CRMs are likely to drive tissue-specific expression, in a wide set of tissues. A Bayesian network is developed to identify tissue-specific CRMs by integrating compa rative sequence data and expression data. The Bayesian network contains at its core a probability tree to represent the dependence between the regulatory activity of a CRM and the set of TFs predicted to bind the module, and a new unsupervised Expectation - Maximization - based algorithm is developed to infer the parameters of the network. We first show that our algorithm successfully discriminates among liver-specific, erythroid-specific, and negative-control modules. In a genome-wide scale, we train a network to identify CRMs driving expression in one of ten different tissues, and new combinations of TFs are discovered to be associated with expression in some tissues.

B. Fischer, V. Roth and J. M. Buhmann: Time-series alignment by non-negative multiple generalized CCA for quantitative proteomics

For a quantitative analysis of differential protein expression, one has to overcome a problem of aligning time series of measurements from liquid chromatography coupled to mass spectrometry. When repeating experiments one can observe that the time axis is deformed in a non-linear way. In this paper we propose a technique to align the time series based on generalized canonical correlation analysis (GCCA) for multiple datasets. The time series alignment required a monotonicity constraint that is incorporated in GCCA. The learning of the alignment function is performed in a supervised as well as in a semi-supervised fashion. We compared our method with previously published methods for aligning mass spectrometry data on a large proteomics dataset.

Improved Prediction of HIV Resistance In-Vitro by Biochemically-DrivenModels, H. Neuvirth, M. Rosen-Zvi, N. Srebro, E. Aharoni, M. Zazzi and N. Tishby

A crucial aspect in anti-HIV therapy is choosing the best treatment among the many available. To this aim studies try to extract information from the HIV virus’ genotype that can be used to computationally predict its in-vitro susceptibility to the available drugs. This paper combines the generative and discriminative approaches in a novel model that improves the utilization of the biological structure of the system. Two aspects are considered. First is the prior distribution of the data which is a mixture of two Gaussians, representing viruses that are either susceptible or resistant to the drugs. Second are the strong dependencies between drugs of the same mechanism. The performance is improved showing error rates of up to 38% of the error achieved by previous studies.

Reconstructing the Phylogeny of Mobile Elements, S. O'Rourke, , Noah Zaitlen, Nebojsa Jojic and Elazar Eskin

The study of mobile element evolution yields valuable insights into the mechanism and history of genome rearrangement, and can help answer questions about our evolutionary history. However, because there are millions of repeats in the mammalian genome, and because these elements exhibit complex evolutionary history, traditional phylogenetic methods are ill-suited to reconstructing their history. New phylogenetic reconstruction algorithms which exploit the unique properties of repeat phylogenies and handle large numbers of repeats are therefore necessary to better understand both mobile elements' evolution and our own.

We propose a randomized algorithm for phylogenetic reconstruction that scales easily to a million or more elements. We apply our algorithm to human and chimpanzee \textit{Alu} and L1 repeats, and to SINE repeats from 61 species, finding finding 32 new L1, 111 new SINE, and over 1000 new \textit{Alu} subfamilies. We also show that our SINE results agree well with current knowledge of SINE and species phylogeny, validating our approach. Our results suggest that the history of mobile elements is significantly more complex than we currently understand, and open avenues for further biological inquiry.