SPINE: a framework for signaling-regulatory pathway inference from cause-effect experiments

MOTIVATION: The complex program of gene expression allows the cell to cope with changing genetic, developmental and environmental conditions. The accumulating large-scale measurements of gene knockout effects and molecular interactions allow us to begin to uncover regulatory and signaling pathways within the cell that connect causal to affected genes on a network of physical interactions. RESULTS: We present a novel framework, SPINE, for Signaling-regulatory Pathway INferencE. The framework aims at explaining gene expression experiments in which a gene is knocked out and as a result multiple genes change their expression levels. To this end, an integrated network of protein-protein and protein-DNA interactions is constructed, and signaling pathways connecting the causal gene to the affected genes are searched for in this network. The reconstruction problem is translated into that of assigning an activation/repression attribute with each protein so as to explain (in expectation) a maximum number of the knockout effects observed. We provide an integer programming formulation for the latter problem and solve it using a commercial solver. We validate the method by applying it to a yeast subnetwork that is involved in mating. In cross-validation tests, SPINE obtains very high accuracy in predicting knockout effects (99%). Next, we apply SPINE to the entire yeast network to predict protein effects and reconstruct signaling and regulatory pathways. Overall, we are able to infer 861 paths with confidence and assign effects to 183 genes. The predicted effects are found to be in high agreement with current biological knowledge. AVAILABILITY: The algorithm and data are available at http://cs.tau.ac.il/~roded/SPINE.html.     

Inferring pairwise regulatory relationships from multiple time series datasets

MOTIVATION: Time series expression experiments have emerged as a popular method for studying a wide range of biological systems under a variety of conditions. One advantage of such data is the ability to infer regulatory relationships using time lag analysis. However, such analysis in a single experiment may result in many false positives due to the small number of time points and the large number of genes. Extending these methods to simultaneously analyze several time series datasets is challenging since under different experimental conditions biological systems may behave faster or slower making it hard to rely on the actual duration of the experiment. RESULTS: We present a new computational model and an associated algorithm to address the problem of inferring time-lagged regulatory relationships from multiple time series expression experiments with varying (unknown) time-scales. Our proposed algorithm uses a set of known interacting pairs to compute a temporal transformation between every two datasets. Using this temporal transformation we search for new interacting pairs. As we show, our method achieves a much lower false-positive rate compared to previous methods that use time series expression data for pairwise regulatory relationship discovery. Some of the new predictions made by our method can be verified using other high throughput data sources and functional annotation databases. AVAILABILITY: Matlab implementation is available from the supporting website: http://www.cs.cmu.edu/~yanxins/regulation_inference/index.html.     

An approximation method for solving the steady-state probability distribution of probabilistic Boolean networks

MOTIVATION: Probabilistic Boolean networks (PBNs) have been proposed to model genetic regulatory interactions. The steady-state probability distribution of a PBN gives important information about the captured genetic network. The computation of the steady-state probability distribution usually includes construction of the transition probability matrix and computation of the steady-state probability distribution. The size of the transition probability matrix is 2(n)-by-2(n) where n is the number of genes in the genetic network. Therefore, the computational costs of these two steps are very expensive and it is essential to develop a fast approximation method. RESULTS: In this article, we propose an approximation method for computing the steady-state probability distribution of a PBN based on neglecting some Boolean networks (BNs) with very small probabilities during the construction of the transition probability matrix. An error analysis of this approximation method is given and theoretical result on the distribution of BNs in a PBN with at most two Boolean functions for one gene is also presented. These give a foundation and support for the approximation method. Numerical experiments based on a genetic network are given to demonstrate the efficiency of the proposed method.     

The core diseasome

Large amounts of protein-protein interaction (PPI) data are available. The human PPI network currently contains over 56?000 interactions between 11?100 proteins. It has been demonstrated that the structure of this network is not random and that the same wiring patterns in it underlie the same biological processes and diseases. In this paper, we ask if there exists a subnetwork of the human PPI network such that its topology is the key to disease formation and hence should be the primary object of therapeutic intervention. We demonstrate that such a subnetwork exists and can be obtained purely computationally. In particular, by successively pruning the entire human PPI network, we are left with a "core" subnetwork that is not only topologically and functionally homogeneous, but is also enriched in disease genes, drug targets, and it contains genes that are known to drive disease formation. We call this subnetwork the Core Diseasome. Furthermore, we show that the topology of the Core Diseasome is unique in the human PPI network suggesting that it may be the wiring of this network that governs the mutagenesis that leads to disease. Explaining the mechanisms behind this phenomenon and exploiting them remains a challenge.     

Stochastic Boolean networks: An efficient approach to modeling gene regulatory networks

ABSTRACT: BACKGROUND: Various computational models have been of interest due to their use in the modelling of gene regulatory networks (GRNs). As a logical model, probabilistic Boolean networks (PBNs) consider molecular and genetic noise, so the study of PBNs provides significant insights into the understanding of the dynamics of GRNs. This will ultimately lead to advances in developing therapeutic methods that intervene in the process of disease development and progression. The applications of PBNs, however, are hindered by the complexities involved in the computation of the state transition matrix and the steady-state distribution of a PBN. For a PBN with n genes and N Boolean networks, the complexity to compute the state transition matrix is O(nN22n) or O(nN2n) for a sparse matrix. RESULTS: This paper presents a novel implementation of PBNs based on the notions of stochastic logic and stochastic computation. This stochastic implementation of a PBN is referred to as a stochastic Boolean network (SBN). An SBN provides an accurate and efficient simulation of a PBN without and with random gene perturbation. The state transition matrix is computed in an SBN with a complexity of O(nL2n), where L is a factor related to the stochastic sequence length. Since the minimum sequence length required for obtaining an evaluation accuracy approximately increases in a polynomial order with the number of genes, n, and the number of Boolean networks, N, usually increases exponentially with n, L is typically smaller than N, especially in a network with a large number of genes. Hence, the computational complexity of an SBN is primarily limited by the number of genes, but not directly by the total possible number of Boolean networks. Furthermore, a time-frame expanded SBN enables an efficient analysis of the steady-state distribution of a PBN. These findings are supported by the simulation results of a simplified p53 network, several randomly generated networks and a network inferred from a T cell immune response dataset. An SBN can also implement the function of an asynchronous PBN and is potentially useful in a hybrid approach in combination with a continuous or single-molecule level stochastic model. CONCLUSIONS: Stochastic Boolean networks (SBNs) are proposed as an efficient approach to modelling gene regulatory networks (GRNs). The SBN approach is able to recover biologically-proven regulatory behaviours, such as the oscillatory dynamics of the p53-Mdm2 network and the dynamic attractors in a T cell immune response network. The proposed approach can further predict the network dynamics when the genes are under perturbation, thus providing biologically meaningful insights for a better understanding of the dynamics of GRNs. The algorithms and methods described in this paper have been implemented in Matlab packages, which are attached as Additional files.     

Network-Based Inference of Cancer Progression from Microarray Data

Cancer cells exhibit a common phenotype of uncontrolled cell growth, but this phenotype may arise from many different combinations of mutations. By inferring how cells evolve in individual tumors, a process called cancer progression, we may be able to identify important mutational events for different tumor types, potentially leading to new therapeutics and diagnostics. Prior work has shown that it is possible to infer frequent progression pathways by using gene expression profiles to estimate ldquodistancesrdquo between tumors. Here, we apply gene network models to improve these estimates of evolutionary distance by controlling for correlations among coregulated genes. We test three variants of this approach: one using an optimized best-fit network, another using sampling to infer a high-confidence subnetwork, and one using a modular network inferred from clusters of similarly expressed genes. Application to lung cancer and breast cancer microarray data sets shows small improvements in phylogenies when correcting from the optimized network and more substantial improvements when correcting from the sampled or modular networks. Our results suggest that a network correction approach improves estimates of tumor similarity, but sophisticated network models are needed to control for the large hypothesis space and sparse data currently available.     

A Network Approach to Predict Pathogenic Genes for Fusarium graminearum

Fusarium graminearum is the pathogenic agent of Fusarium head blight (FHB), which is a destructive disease on wheat and barley, thereby causing huge economic loss and health problems to human by contaminating foods. Identifying pathogenic genes can shed light on pathogenesis underlying the interaction between F. graminearum and its plant host. However, it is difficult to detect pathogenic genes for this destructive pathogen by time-consuming and expensive molecular biological experiments in lab. On the other hand, computational methods provide an alternative way to solve this problem. Since pathogenesis is a complicated procedure that involves complex regulations and interactions, the molecular interaction network of F. graminearum can give clues to potential pathogenic genes. Furthermore, the gene expression data of F. graminearum before and after its invasion into plant host can also provide useful information. In this paper, a novel systems biology approach is presented to predict pathogenic genes of F. graminearum based on molecular interaction network and gene expression data. With a small number of known pathogenic genes as seed genes, a subnetwork that consists of potential pathogenic genes is identified from the protein-protein interaction network (PPIN) of F. graminearum, where the genes in the subnetwork are further required to be differentially expressed before and after the invasion of the pathogenic fungus. Therefore, the candidate genes in the subnetwork are expected to be involved in the same biological processes as seed genes, which imply that they are potential pathogenic genes. The prediction results show that most of the pathogenic genes of F. graminearum are enriched in two important signal transduction pathways, including G protein coupled receptor pathway and MAPK signaling pathway, which are known related to pathogenesis in other fungi. In addition, several pathogenic genes predicted by our method are verified in other pathogenic fungi, which demonstrate the effectiveness of the proposed method. The results presented in this paper not only can provide guidelines for future experimental verification, but also shed light on the pathogenesis of the destructive fungus F. graminearum.     

An Efficient Steady-State Analysis Method for Large Boolean Networks with High Maximum Node Connectivity

Boolean networks have been widely used to model biological processes lacking detailed kinetic information. Despite their simplicity, Boolean network dynamics can still capture some important features of biological systems such as stable cell phenotypes represented by steady states. For small models, steady states can be determined through exhaustive enumeration of all state transitions. As the number of nodes increases, however, the state space grows exponentially thus making it difficult to find steady states. Over the last several decades, many studies have addressed how to handle such a state space explosion. Recently, increasing attention has been paid to a satisfiability solving algorithm due to its potential scalability to handle large networks. Meanwhile, there still lies a problem in the case of large models with high maximum node connectivity where the satisfiability solving algorithm is known to be computationally intractable. To address the problem, this paper presents a new partitioning-based method that breaks down a given network into smaller subnetworks. Steady states of each subnetworks are identified by independently applying the satisfiability solving algorithm. Then, they are combined to construct the steady states of the overall network. To efficiently apply the satisfiability solving algorithm to each subnetwork, it is crucial to find the best partition of the network. In this paper, we propose a method that divides each subnetwork to be smallest in size and lowest in maximum node connectivity. This minimizes the total cost of finding all steady states in entire subnetworks. The proposed algorithm is compared with others for steady states identification through a number of simulations on both published small models and randomly generated large models with differing maximum node connectivities. The simulation results show that our method can scale up to several hundreds of nodes even for Boolean networks with high maximum node connectivity. The algorithm is implemented and available at http://cps.kaist.ac.kr/∼ckhong/tools/download/PAD.tar.gz.     

Inference of gene regulatory networks and compound mode of action from time course gene expression profiles

MOTIVATION: Time series expression experiments are an increasingly popular method for studying a wide range of biological systems. Here we developed an algorithm that can infer the local network of gene-gene interactions surrounding a gene of interest. This is achieved by a perturbation of the gene of interest and subsequently measuring the gene expression profiles at multiple time points. We applied this algorithm to computer simulated data and to experimental data on a nine gene network in Escherichia coli. RESULTS: In this paper we show that it is possible to recover the gene regulatory network from a time series data of gene expression following a perturbation to the cell. We show this both on simulated data and on a nine gene subnetwork part of the DNA-damage response pathway (SOS pathway) in the bacteria E. coli. CONTACT: dibernardo@tigem.it SUPLEMENTARY INFORMATION: Supplementary data are available at http://dibernado.tigem.it     

GenRev: exploring functional relevance of genes in molecular networks

We introduce GenRev, a network-based software package developed to explore the functional relevance of genes generated as an intermediate result from numerous high-throughput technologies. GenRev searches for optimal intermediate nodes (genes) for the connection of input nodes via several algorithms, including the Klein-Ravi algorithm, the limited kWalks algorithm and a heuristic local search algorithm. Gene ranking and graph clustering analyses are integrated into the package. GenRev has the following features. (1) It provides users with great flexibility to define their own networks. (2) Users are allowed to define each gene's importance in a subnetwork search by setting its score. (3) It is standalone and platform independent. (4) It provides an optimization in subnetwork search, which dramatically reduces the running time. GenRev is particularly designed for general use so that users have the flexibility to choose a reference network and define the score of genes. GenRev is freely available at http://bioinfo.mc.vanderbilt.edu/GenRev.html.     

Gene Regulatory Network Inferences Using a Maximum-Relevance and Maximum-Significance Strategy

Recovering gene regulatory networks from expression data is a challenging problem in systems biology that provides valuable information on the regulatory mechanisms of cells. A number of algorithms based on computational models are currently used to recover network topology. However, most of these algorithms have limitations. For example, many models tend to be complicated because of the “large p, small n” problem. In this paper, we propose a novel regulatory network inference method called the maximum-relevance and maximum-significance network (MRMSn) method, which converts the problem of recovering networks into a problem of how to select the regulator genes for each gene. To solve the latter problem, we present an algorithm that is based on information theory and selects the regulator genes for a specific gene by maximizing the relevance and significance. A first-order incremental search algorithm is used to search for regulator genes. Eventually, a strict constraint is adopted to adjust all of the regulatory relationships according to the obtained regulator genes and thus obtain the complete network structure. We performed our method on five different datasets and compared our method to five state-of-the-art methods for network inference based on information theory. The results confirm the effectiveness of our method.     

Modularized study of human calcium signalling pathway

Signalling pathways are complex biochemical networks responsible for regulation of numerous cellular functions. These networks function by serial and successive interactions among a large number of vital biomolecules and chemical compounds. For deciphering and analysing the underlying mechanism of such networks, a modularized study is quite helpful. Here we propose an algorithm for modularization of calcium signalling pathway of H. sapiens. The idea that “a node whose function is dependant on maximum number of other nodes tends to be the center of a subnetwork” is used to divide a large signalling network into smaller subnetworks. Inclusion of node(s) into subnetworks(s) is dependant on the outdegree of the node(s). Here outdegree of a node refers to the number of relations of the considered node lying outside the constructed subnetwork. Node(s) having more than c relations lying outside the expanding subnetwork have to be excluded from it. Here c is a specified variable based on user preference, which is finally fixed during adjustments of created subnetworks, so that certain biological significance can be conferred on them.