NET-SYNTHESIS: a software for synthesis, inference and simplification of signal transduction networks

We present a software for combined synthesis, inference and simplification of signal transduction networks. The main idea of our method lies in representing observed indirect causal relationships as network paths and using techniques from combinatorial optimization to find the sparsest graph consistent with all experimental observations. We illustrate the biological usability of our software by applying it to a previously published signal transduction network and by using it to synthesize and simplify a novel network corresponding to activation-induced cell death in large granular lymphocyte leukemia. AVAILABILITY: NET-SYNTHESIS is freely downloadable from http://www.cs.uic.edu/~dasgupta/network-synthesis/     

Simulating the evolution of signal transduction pathways

We use a generic model of a network of proteins that can activate or deactivate each other to explore the emergence and evolution of signal transduction networks and to gain a basic understanding of their general properties. Starting with a set of non-interacting proteins, we evolve a signal transduction network by random mutation and selection to fulfill a complex biological task. In order to validate this approach we base selection on a fitness function that captures the essential features of chemotactic behavior as seen in bacteria. We find that a system of as few as three proteins can evolve into a network mediating chemotaxis-like behavior by acting as a "derivative sensor". Furthermore, we find that the dynamics and topology of such networks show many similarities to the natural chemotaxis pathway, that the response magnitude can increase with increasing network size and that network behavior shows robustness towards variations in some of the internal parameters. We conclude that simulating the evolution of signal transduction networks to mediate a certain behavior may be a promising approach for understanding the general properties of the natural pathway for that behavior.     

Causal inference in biomolecular pathways using a Bayesian network approach and an Implicit method

We introduce here the concept of Implicit networks which provide, like Bayesian networks, a graphical modelling framework that encodes the joint probability distribution for a set of random variables within a directed acyclic graph. We show that Implicit networks, when used in conjunction with appropriate statistical techniques, are very attractive for their ability to understand and analyze biological data. Particularly, we consider here the use of Implicit networks for causal inference in biomolecular pathways. In such pathways, an Implicit network encodes dependencies among variables (proteins, genes), can be trained to learn causal relationships (regulation, interaction) between them and then used to predict the biological response given the status of some key proteins or genes in the network. We show that Implicit networks offer efficient methodologies for learning from observations without prior knowledge and thus provide a good alternative to classical inference in Bayesian networks when priors are missing. We illustrate our approach by an application to simulated data for a simplified signal transduction pathway of the epidermal growth factor receptor (EGFR) protein.     

Simulated Evolution of Signal Transduction Networks

Signal transduction is the process of routing information inside cells when receiving stimuli from their environment that modulate the behavior and function. In such biological processes, the receptors, after receiving the corresponding signals, activate a number of biomolecules which eventually transduce the signal to the nucleus. The main objective of our work is to develop a theoretical approach which will help to better understand the behavior of signal transduction networks due to changes in kinetic parameters and network topology. By using an evolutionary algorithm, we designed a mathematical model which performs basic signaling tasks similar to the signaling process of living cells. We use a simple dynamical model of signaling networks of interacting proteins and their complexes. We study the evolution of signaling networks described by mass-action kinetics. The fitness of the networks is determined by the number of signals detected out of a series of signals with varying strength. The mutations include changes in the reaction rate and network topology. We found that stronger interactions and addition of new nodes lead to improved evolved responses. The strength of the signal does not play any role in determining the response type. This model will help to understand the dynamic behavior of the proteins involved in signaling pathways. It will also help to understand the robustness of the kinetics of the output response upon changes in the rate of reactions and the topology of the network.     

Detecting and Removing Inconsistencies between Experimental Data and Signaling Network Topologies Using Integer Linear Programming on Interaction Graphs

Cross-referencing experimental data with our current knowledge of signaling network topologies is one central goal of mathematical modeling of cellular signal transduction networks. We present a new methodology for data-driven interrogation and training of signaling networks. While most published methods for signaling network inference operate on Bayesian, Boolean, or ODE models, our approach uses integer linear programming (ILP) on interaction graphs to encode constraints on the qualitative behavior of the nodes. These constraints are posed by the network topology and their formulation as ILP allows us to predict the possible qualitative changes (up, down, no effect) of the activation levels of the nodes for a given stimulus. We provide four basic operations to detect and remove inconsistencies between measurements and predicted behavior: (i) find a topology-consistent explanation for responses of signaling nodes measured in a stimulus-response experiment (if none exists, find the closest explanation); (ii) determine a minimal set of nodes that need to be corrected to make an inconsistent scenario consistent; (iii) determine the optimal subgraph of the given network topology which can best reflect measurements from a set of experimental scenarios; (iv) find possibly missing edges that would improve the consistency of the graph with respect to a set of experimental scenarios the most. We demonstrate the applicability of the proposed approach by interrogating a manually curated interaction graph model of EGFR/ErbB signaling against a library of high-throughput phosphoproteomic data measured in primary hepatocytes. Our methods detect interactions that are likely to be inactive in hepatocytes and provide suggestions for new interactions that, if included, would significantly improve the goodness of fit. Our framework is highly flexible and the underlying model requires only easily accessible biological knowledge. All related algorithms were implemented in a freely available toolbox SigNetTrainer making it an appealing approach for various applications.     

A highly sensitive near‐infrared fluorescent detection method to analyze signalling pathways by reverse‐phase protein array

The comprehensive and quantitative analysis of the protein phosphorylation patterns in different cellular context is of considerable and general interest. The ability to quantify phosphorylation of discrete signalling proteins in large collections of biological samples would greatly favour the development of systems biology in the field of cell signalling. Reverse‐phase protein array (RPPA) potentially represents a very attractive approach to map signal transduction networks with high throughput. In the present report, we describe an improved detection method for RPPA combining near‐infrared with one or two rounds of tyramide‐based signal amplification. The LOQ was lowered from 6.84 attomoles with a direct detection protocol to 0.21 attomole with two amplification steps. We validated this method in the context of intracellular signal transduction triggered by follicle‐stimulating hormone in HEK293 cells. We consistently detected phosphorylated proteins in the sub‐attomole range from less than 1 ng of total cell extracts. Importantly, the method correlated with Western blot analysis of the same samples while displaying excellent intra‐ and inter‐slide reproducibility. We conclude that RPPA combined with amplified near‐infrared detection can be used to capture the subtle regulations intrinsic to signalling network dynamics at an unprecedented throughput, from minute amounts of biological samples.     

Sensitivity, principal component and flux analysis applied to signal transduction: the case of epidermal growth factor mediated signaling

MOTIVATION: Novel high-throughput genomic and proteomic tools are allowing the integration of information from a range of biological assays into a single conceptual framework. This framework is often described as a network of biochemical reactions. We present strategies for the analysis of such networks. RESULTS: The direct differential method is described for the systematic evaluation of scaled sensitivity coefficients in reaction networks. Principal component analysis, based on an eigenvalue-eigenvector analysis of the scaled sensitivity coefficient matrix, is applied to rank individual reactions in the network based on their effect on system output. When combined with flux analysis, sensitivity analysis allows model reduction or simplification. Using epidermal growth factor (EGF) mediated signaling and trafficking as an example of signal transduction, we demonstrate that sensitivity analysis quantitatively reveals the dependence of dual-phosphorylated extracellular signal-regulated kinase (ERK) concentration on individual reaction rate constants. It predicts that EGF mediated reactions proceed primarily via an Shc-dependent pathway. Further, it suggests that receptor internalization and endosomal signaling are important features regulating signal output only at low EGF dosages and at later times.     

Dynamic properties of network motifs contribute to biological network organization

Biological networks, such as those describing gene regulation, signal transduction, and neural synapses, are representations of large-scale dynamic systems. Discovery of organizing principles of biological networks can be enhanced by embracing the notion that there is a deep interplay between network structure and system dynamics. Recently, many structural characteristics of these non-random networks have been identified, but dynamical implications of the features have not been explored comprehensively. We demonstrate by exhaustive computational analysis that a dynamical property—stability or robustness to small perturbations—is highly correlated with the relative abundance of small subnetworks (network motifs) in several previously determined biological networks. We propose that robust dynamical stability is an influential property that can determine the non-random structure of biological networks.     

Mathematical Modeling of Sustainable Synaptogenesis by Repetitive Stimuli Suggests Signaling Mechanisms In Vivo

The mechanisms of long-term synaptic maintenance are a key component to understanding the mechanism of long-term memory. From biological experiments, a hypothesis arose that repetitive stimuli with appropriate intervals are essential to maintain new synapses for periods of longer than a few days. We successfully reproduce the time-course of relative numbers of synapses with our mathematical model in the same conditions as biological experiments, which used Adenosine-3′, 5′-cyclic monophosphorothioate, Sp-isomer (Sp-cAMPS) as external stimuli. We also reproduce synaptic maintenance responsiveness to intervals of Sp-cAMPS treatment accompanied by PKA activation. The model suggests a possible mechanism of sustainable synaptogenesis which consists of two steps. First, the signal transduction from an external stimulus triggers the synthesis of a new signaling protein. Second, the new signaling protein is required for the next signal transduction with the same stimuli. As a result, the network component is modified from the first network, and a different signal is transferred which triggers the synthesis of another new signaling molecule. We refer to this hypothetical mechanism as network succession. We build our model on the basis of two hypotheses: (1) a multi-step network succession induces downregulation of SSH and COFILIN gene expression, which triggers the production of stable F-actin; (2) the formation of a complex of stable F-actin with Drebrin at PSD is the critical mechanism to achieve long-term synaptic maintenance. Our simulation shows that a three-step network succession is sufficient to reproduce sustainable synapses for a period longer than 14 days. When we change the network structure to a single step network, the model fails to follow the exact condition of repetitive signals to reproduce a sufficient number of synapses. Another advantage of the three-step network succession is that this system indicates a greater tolerance of parameter changes than the single step network.     

Elementary Flux Modes Analysis of Functional Domain Networks Allows a Better Metabolic Pathway Interpretation

Metabolic network analysis is an important step for the functional understanding of biological systems. In these networks, enzymes are made of one or more functional domains often involved in different catalytic activities. Elementary flux mode (EFM) analysis is a method of choice for the topological studies of these enzymatic networks. In this article, we propose to use an EFM approach on networks that encompass available knowledge on structure-function. We introduce a new method that allows to represent the metabolic networks as functional domain networks and provides an application of the algorithm for computing elementary flux modes to analyse them. Any EFM that can be represented using the classical representation can be represented using our functional domain network representation but the fine-grained feature of functional domain networks allows to highlight new connections in EFMs. This methodology is applied to the tricarboxylic acid cycle (TCA cycle) of Bacillus subtilis, and compared to the classical analyses. This new method of analysis of the functional domain network reveals that a specific inhibition on the second domain of the lipoamide dehydrogenase (pdhD) component of pyruvate dehydrogenase complex leads to the loss of all fluxes. Such conclusion was not predictable in the classical approach.     

RINQ: Reference-based Indexing for Network Queries

We consider the problem of similarity queries in biological network databases. Given a database of networks, similarity query returns all the database networks whose similarity (i.e. alignment score) to a given query network is at least a specified similarity cutoff value. Alignment of two networks is a very costly operation, which makes exhaustive comparison of all the database networks with a query impractical. To tackle this problem, we develop a novel indexing method, named RINQ (Reference-based Indexing for Biological Network Queries). Our method uses a set of reference networks to eliminate a large portion of the database quickly for each query. A reference network is a small biological network. We precompute and store the alignments of all the references with all the database networks. When our database is queried, we align the query network with all the reference networks. Using these alignments, we calculate a lower bound and an approximate upper bound to the alignment score of each database network with the query network. With the help of upper and lower bounds, we eliminate the majority of the database networks without aligning them to the query network. We also quickly identify a small portion of these as guaranteed to be similar to the query. We perform pairwise alignment only for the remaining networks. We also propose a supervised method to pick references that have a large chance of filtering the unpromising database networks. Extensive experimental evaluation suggests that (i) our method reduced the running time of a single query on a database of around 300 networks from over 2 days to only 8 h; (ii) our method outperformed the state of the art method Closure Tree and SAGA by a factor of three or more; and (iii) our method successfully identified statistically and biologically significant relationships across networks and organisms.     

Parameter estimation using Simulated Annealing for S-system models of biochemical networks

MOTIVATION: High-throughput technologies now allow the acquisition of biological data, such as comprehensive biochemical time-courses at unprecedented rates. These temporal profiles carry topological and kinetic information regarding the biochemical network from which they were drawn. Retrieving this information will require systematic application of both experimental and computational methods. RESULTS: S-systems are non-linear mathematical approximative models based on the power-law formalism. They provide a general framework for the simulation of integrated biological systems exhibiting complex dynamics, such as genetic circuits, signal transduction and metabolic networks. We describe how the heuristic optimization technique simulated annealing (SA) can be effectively used for estimating the parameters of S-systems from time-course biochemical data. We demonstrate our methods using three artificial networks designed to simulate different network topologies and behavior. We then end with an application to a real biochemical network by creating a working model for the cadBA system in Escherichia coli. AVAILABILITY: The source code written in C++ is available at http://www.engg.upd.edu.ph/~naval/bioinformcode.html. All the necessary programs including the required compiler are described in a document archived with the source code. SUPPLEMENTARY INFORMATION: Supplementary material is available at Bioinformatics online.     

Discovery of intramolecular signal transduction network based on a new protein dynamics model of energy dissipation

A novel approach to reveal intramolecular signal transduction network is proposed in this work. To this end, a new algorithm of network construction is developed, which is based on a new protein dynamics model of energy dissipation. A key feature of this approach is that direction information is specified after inferring protein residue-residue interaction network involved in the process of signal transduction. This enables fundamental analysis of the regulation hierarchy and identification of regulation hubs of the signaling network. A well-studied allosteric enzyme, E. coli aspartokinase III, is used as a model system to demonstrate the new method. Comparison with experimental results shows that the new approach is able to predict all the sites that have been experimentally proved to desensitize allosteric regulation of the enzyme. In addition, the signal transduction network shows a clear preference for specific structural regions, secondary structural types and residue conservation. Occurrence of super-hubs in the network indicates that allosteric regulation tends to gather residues with high connection ability to collectively facilitate the signaling process. Furthermore, a new parameter of propagation coefficient is defined to determine the propagation capability of residues within a signal transduction network. In conclusion, the new approach is useful for fundamental understanding of the process of intramolecular signal transduction and thus has significant impact on rational design of novel allosteric proteins.     

A systems biology approach for the study of cumulative oncogenes with applications to the MAPK signal transduction pathway

The Extracellular signal Regulated Kinase (ERK) pathway is one of the most well-studied signaling pathways in cell cycle regulation. Disruption in the normal functioning of this pathway is linked to many forms of cancer. In a previous study [D.K. Pant, A. Ghosh, Automated oncogene detection in complex protein networks, with applications to the MAPK signal transduction pathway, Biophys. Chem. 113 (2005) 275-288.], we developed a novel approach to predict single point mutations that are likely to cause cellular transformation in signaling transduction networks. We have extended this method to study disparate pair mutation in enzyme/protein interactions and in expression levels in signal transduction pathway and have applied it to the MAPK signaling pathway to study how synergistic or cooperative mutation within signaling networks acts in unison to cause malignant transformation. The method provides a quantitative ranking of the modifier pair of ERK activation. It is seen that the highest ranking single point mutations comprise the highest ranking pair mutations. We validate some of our results with experimental literature on multiple mutations. A second order sensitivity analysis scheme is additionally used to determine the effect of correlations among mutations at different sites in the pathways.     

Reconciling taxonomy and phylogenetic inference: formalism and algorithms for describing discord and inferring taxonomic roots

Background

Understanding the evolution of biological networks can provide insight into how their modular structure arises and how they are affected by environmental changes. One approach to studying the evolution of these networks is to reconstruct plausible common ancestors of present-day networks, allowing us to analyze how the topological properties change over time and to posit mechanisms that drive the networks?? evolution. Further, putative ancestral networks can be used to help solve other difficult problems in computational biology, such as network alignment.

Results

We introduce a combinatorial framework for encoding network histories, and we give a fast procedure that, given a set of gene duplication histories, in practice finds network histories with close to the minimum number of interaction gain or loss events to explain the observed present-day networks. In contrast to previous studies, our method does not require knowing the relative ordering of unrelated duplication events. Results on simulated histories and real biological networks both suggest that common ancestral networks can be accurately reconstructed using this parsimony approach. A software package implementing our method is available under the Apache 2.0 license at http://cbcb.umd.edu/kingsford-group/parana.

Conclusions

Our parsimony-based approach to ancestral network reconstruction is both efficient and accurate. We show that considering a larger set of potential ancestral interactions by not assuming a relative ordering of unrelated duplication events can lead to improved ancestral network inference.