Detecting conserved interaction patterns in biological networks.

Molecular interaction data plays an important role in understanding biological processes at a modular level by providing a framework for understanding cellular organization, functional hierarchy, and evolutionary conservation. As the quality and quantity of network and interaction data increases rapidly, the problem of effectively analyzing this data becomes significant. Graph theoretic formalisms, commonly used for these analysis tasks, often lead to computationally hard problems due to their relation to subgraph isomorphism. This paper presents an innovative new algorithm, MULE, for detecting frequently occurring patterns and modules in biological networks. Using an innovative graph simplification technique based on ortholog contraction, which is ideally suited to biological networks, our algorithm renders these problems computationally tractable and scalable to large numbers of networks. We show, experimentally, that our algorithm can extract frequently occurring patterns in metabolic pathways and protein interaction networks from the KEGG, DIP, and BIND databases within seconds. When compared to existing approaches, our graph simplification technique can be viewed either as a pruning heuristic, or a closely related, but computationally simpler task. When used as a pruning heuristic, we show that our technique reduces effective graph sizes significantly, accelerating existing techniques by several orders of magnitude! Indeed, for most of the test cases, existing techniques could not even be applied without our pruning step. When used as a stand-alone analysis technique, MULE is shown to convey significant biological insights at near-interactive rates. The software, sample input graphs, and detailed results for comprehensive analysis of nine eukaryotic PPI networks are available at www.cs.purdue.edu/homes/koyuturk/mule.     

Cooperative recurrent modular neural networks for constrained optimization: a survey of models and applications

Constrained optimization problems arise in a wide variety of scientific and engineering applications. Since several single recurrent neural networks when applied to solve constrained optimization problems for real-time engineering applications have shown some limitations, cooperative recurrent neural network approaches have been developed to overcome drawbacks of these single recurrent neural networks. This paper surveys in details work on cooperative recurrent neural networks for solving constrained optimization problems and their engineering applications, and points out their standing models from viewpoint of both convergence to the optimal solution and model complexity. We provide examples and comparisons to shown advantages of these models in the given applications.     

Modular engineering of cellular signaling proteins and networks

Living cells respond to their environment using networks of signaling molecules that act as sensors, information processors, and actuators. These signaling systems are highly modular at both the molecular and network scales, and much evidence suggests that evolution has harnessed this modularity to rewire and generate new physiological behaviors. Conversely, we are now finding that, following nature's example, signaling modules can be recombined to form synthetic tools for monitoring, interrogating, and controlling the behavior of cells. Here we highlight recent progress in the modular design of synthetic receptors, optogenetic switches, and phospho-regulated proteins and circuits, and discuss the expanding role of combinatorial design in the engineering of cellular signaling proteins and networks.     

Basic networks: Definition and applications

We define basic networks as the undirected subgraphs with minimal number of units in which the distances (geodesics, minimal path lengths) among a set of selected nodes, which we call seeds, in the original graph are conserved. The additional nodes required to draw the basic network are called connectors. We describe a heuristic strategy to find the basic networks of complex graphs. We also show how the characterization of these networks may help to obtain relevant biological information from highly complex protein-protein interaction data.     

Quantitative phosphoproteomics by mass spectrometry: past, present, and future

Protein phosphorylation-mediated signaling networks regulate much of the cellular response to external stimuli, and dysregulation in these networks has been linked to multiple disease states. Significant advancements have been made over the past decade to enable the analysis and quantification of cellular protein phosphorylation events, but comprehensive analysis of the phosphoproteome is still lacking, as is the ability to monitor signaling at the network level while comprehending the biological implications of each phosphorylation site. In this review we highlight many of the technological advances over the past decade and describe some of the latest applications of these tools to uncover signaling networks in a variety of biological settings. We finish with a concise discussion of the future of the field, including additional advances that are required to link protein phosphorylation analysis with biological insight.     

GeneInfoViz: constructing and visualizing gene relation networks

Large amounts of knowledge about genes have been stored in public databases. One of the most challenging problems in Bioinformatics is, given all the information about the genes in the databases, determining the relationships between the genes. For example, how can we determine if genes are related and how closely they are related based on existing knowledge about their biological roles. We developed GeneInfoViz, a web tool for batch retrieval of gene information and construction and visualization of gene relation networks. We created a database containing compiled Gene Ontology information for the genes of several model organisms. Users can batch search for a group of genes and get the Gene Ontology terms that are associated with the genes. Directed acyclic graphs are generated to show the hierarchical structure of the Gene Ontology tree. GeneInfoViz calculates an adjacency matrix to determine whether the genes are related and, if so, how closely they are related based on biological processes, molecular functions, or cellular components they are associated with and then displays a dynamic graph layout of the network among the selected genes.     

The signaling petri net-based simulator: a non-parametric strategy for characterizing the dynamics of cell-specific signaling networks

Reconstructing cellular signaling networks and understanding how they work are major endeavors in cell biology. The scale and complexity of these networks, however, render their analysis using experimental biology approaches alone very challenging. As a result, computational methods have been developed and combined with experimental biology approaches, producing powerful tools for the analysis of these networks. These computational methods mostly fall on either end of a spectrum of model parameterization. On one end is a class of structural network analysis methods; these typically use the network connectivity alone to generate hypotheses about global properties. On the other end is a class of dynamic network analysis methods; these use, in addition to the connectivity, kinetic parameters of the biochemical reactions to predict the network's dynamic behavior. These predictions provide detailed insights into the properties that determine aspects of the network's structure and behavior. However, the difficulty of obtaining numerical values of kinetic parameters is widely recognized to limit the applicability of this latter class of methods. Several researchers have observed that the connectivity of a network alone can provide significant insights into its dynamics. Motivated by this fundamental observation, we present the signaling Petri net, a non-parametric model of cellular signaling networks, and the signaling Petri net-based simulator, a Petri net execution strategy for characterizing the dynamics of signal flow through a signaling network using token distribution and sampling. The result is a very fast method, which can analyze large-scale networks, and provide insights into the trends of molecules' activity-levels in response to an external stimulus, based solely on the network's connectivity. We have implemented the signaling Petri net-based simulator in the PathwayOracle toolkit, which is publicly available at http://bioinfo.cs.rice.edu/pathwayoracle. Using this method, we studied a MAPK1,2 and AKT signaling network downstream from EGFR in two breast tumor cell lines. We analyzed, both experimentally and computationally, the activity level of several molecules in response to a targeted manipulation of TSC2 and mTOR-Raptor. The results from our method agreed with experimental results in greater than 90% of the cases considered, and in those where they did not agree, our approach provided valuable insights into discrepancies between known network connectivities and experimental observations.     

细胞信号网络功能鲁棒的简并性拓扑特征

细胞信号网络对于外界环境的干扰表现出优良的鲁棒性,但是其维持功能鲁棒的内在机制尚未明确,本文研究了细胞信号网络功能鲁棒性的拓扑特征。选择布尔网络模型模拟细胞网络的动态行为,利用网络节点状态的扰动模拟外界环境干扰。基于演化策略探寻不同网络拓扑的功能并分析其在干扰环境下的鲁棒性,采用埃德尔曼提出的基于信息论的计算方法评估网络拓扑的简并度、冗余度和复杂度等拓扑属性,对比分析它们与功能鲁棒度的相关性及作用机理。结果显示,在网络模型的演化过程中,其拓扑简并度与功能鲁棒度显著正相关,相关性水平高于拓扑冗余度与鲁棒度的相关性。并且,随着鲁棒度的提升,网络的节点数和复杂度也随之升高,同样简并度与网络的节点数和复杂度的相关性高于拓扑冗余度与网络的节点数和复杂度的相关性。这说明增加的网络节点以简并的方式同时提高了网络拓扑的鲁棒度和复杂度。因此,细胞网络功能鲁棒性的拓扑特征是简并而不是冗余,简并为解决生物系统的复杂问题提供了有效手段,为人工系统的可靠性设计提供有益的借鉴。     

The complexity of comparing reaction systems

MOTIVATION: As more genomic data becomes available there is increased attention on understanding the mechanisms encoded in the genome. New XML dialects like CellML and Systems Biology Markup Language (SBML) are being developed to describe biological networks of all types. In the absence of detailed kinetic information for these networks, stoichiometric data is an especially valuable source of information. Network databases are the next logical step beyond storing purely genomic information. Just as comparison of entries in genomic databases has been a vital algorithmic problem through the course of the sequencing project, comparison of networks in network databases will be a crucial problem as we seek to integrate higher-order network knowledge. RESULTS: We show that comparing the stoichiometric structure of two reactions systems is equivalent to the graph isomorphism problem. This is encouraging because graph isomorphism is, in practice, a tractable problem using heuristics. The analogous problem of searching for a subsystem of a reaction system is NP-complete. We also discuss heuristic issues in implementations for practical comparison of stoichiometric matrices.     

On problem solving with Hopfield neural networks

Hopfield and Tank have shown that neural networks can be used to solve certain computationally hard problems, in particular they studied the Traveling Salesman Problem (TSP). Based on network simulation results they conclude that analog VLSI neural nets can be promising in solving these problems. Recently, Wilson and Pawley presented the results of their simulations which contradict the original results and cast doubts on the usefulness of neural nets. In this paper we give the results of our simulations that clarify some of the discrepancies. We also investigate the scaling of TSP solutions found by neural nets as the size of the problem increases. Further, we consider the neural net solution of the Clustering Problem, also a computationally hard problem, and discuss the types of problems that appear to be well suited for a neural net approach.     

Algorithms for effective querying of compound graph-based pathway databases

Background  

Graph-based pathway ontologies and databases are widely used to represent data about cellular processes. This representation makes it possible to programmatically integrate cellular networks and to investigate them using the well-understood concepts of graph theory in order to predict their structural and dynamic properties. An extension of this graph representation, namely hierarchically structured or compound graphs, in which a member of a biological network may recursively contain a sub-network of a somehow logically similar group of biological objects, provides many additional benefits for analysis of biological pathways, including reduction of complexity by decomposition into distinct components or modules. In this regard, it is essential to effectively query such integrated large compound networks to extract the sub-networks of interest with the help of efficient algorithms and software tools.     

Detection of the dominant direction of information flow and feedback links in densely interconnected regulatory networks

Background  

Finding the dominant direction of flow of information in densely interconnected regulatory or signaling networks is required in many applications in computational biology and neuroscience. This is achieved by first identifying and removing links which close up feedback loops in the original network and hierarchically arranging nodes in the remaining network. In mathematical language this corresponds to a problem of making a graph acyclic by removing as few links as possible and thus altering the original graph in the least possible way. The exact solution of this problem requires enumeration of all cycles and combinations of removed links, which, as an NP-hard problem, is computationally prohibitive even for modest-size networks.     

The Logic of EGFR/ErbB Signaling: Theoretical Properties and Analysis of High-Throughput Data

The epidermal growth factor receptor (EGFR) signaling pathway is probably the best-studied receptor system in mammalian cells, and it also has become a popular example for employing mathematical modeling to cellular signaling networks. Dynamic models have the highest explanatory and predictive potential; however, the lack of kinetic information restricts current models of EGFR signaling to smaller sub-networks. This work aims to provide a large-scale qualitative model that comprises the main and also the side routes of EGFR/ErbB signaling and that still enables one to derive important functional properties and predictions. Using a recently introduced logical modeling framework, we first examined general topological properties and the qualitative stimulus-response behavior of the network. With species equivalence classes, we introduce a new technique for logical networks that reveals sets of nodes strongly coupled in their behavior. We also analyzed a model variant which explicitly accounts for uncertainties regarding the logical combination of signals in the model. The predictive power of this model is still high, indicating highly redundant sub-structures in the network. Finally, one key advance of this work is the introduction of new techniques for assessing high-throughput data with logical models (and their underlying interaction graph). By employing these techniques for phospho-proteomic data from primary hepatocytes and the HepG2 cell line, we demonstrate that our approach enables one to uncover inconsistencies between experimental results and our current qualitative knowledge and to generate new hypotheses and conclusions. Our results strongly suggest that the Rac/Cdc42 induced p38 and JNK cascades are independent of PI3K in both primary hepatocytes and HepG2. Furthermore, we detected that the activation of JNK in response to neuregulin follows a PI3K-dependent signaling pathway.     

Multi-layered representation for cell signaling pathways

To understand complex signaling pathways and networks, it is necessary to develop a formal and structured representation of the available information in a format suitable for analysis by software tools. Due to the complexity and incompleteness of the current biological knowledge about cell signaling, such a device must be able to represent cellular pathways at differing levels of details, one level of information abstract enough to convey an essential signaling flow while hiding its details and another level of information detailed enough to explain the underlying mechanisms that account for the signaling flow described at a more abstract level. We have defined a formal ontology for cell-signaling events that allows us to describe these cellular pathways at various levels of abstraction. Using this formal representation, ROSPath (reactive oxygen species-mediated signaling pathway) database system has been implemented and made available on the web (rospath.ewha.ac.kr). ROSPath is a database system for reactive oxygen species (ROS)-mediated cell signaling pathways and signaling processes in molecular detail, which facilitates a comprehensive understanding of the regulatory mechanisms in signaling pathways. ROSPath includes growth factor-, stress-, and cytokine-induced signaling pathways containing about 500 unique proteins (mostly mammalian) and their related protein states, protein complexes, protein complex states, signaling interactions, signaling steps, and pathways. It is a web-based structured repository of information on the signaling pathways of interest and provides a means for managing data produced by large-scale and high-throughput techniques such as proteomics. Also, software tools are provided for querying, displaying, and analyzing pathways, thus furnishing an integrated web environment for visualizing and manipulating ROS-mediated cell-signaling events.     

Nonparametric simulation of signal transduction networks with semi-synchronized update

Simulating signal transduction in cellular signaling networks provides predictions of network dynamics by quantifying the changes in concentration and activity-level of the individual proteins. Since numerical values of kinetic parameters might be difficult to obtain, it is imperative to develop non-parametric approaches that combine the connectivity of a network with the response of individual proteins to signals which travel through the network. The activity levels of signaling proteins computed through existing non-parametric modeling tools do not show significant correlations with the observed values in experimental results. In this work we developed a non-parametric computational framework to describe the profile of the evolving process and the time course of the proportion of active form of molecules in the signal transduction networks. The model is also capable of incorporating perturbations. The model was validated on four signaling networks showing that it can effectively uncover the activity levels and trends of response during signal transduction process.     

Learning Bayesian network classifiers using ant colony optimization

Bayesian networks are knowledge representation tools that model the (in)dependency relationships among variables for probabilistic reasoning. Classification with Bayesian networks aims to compute the class with the highest probability given a case. This special kind is referred to as Bayesian network classifiers. Since learning the Bayesian network structure from a dataset can be viewed as an optimization problem, heuristic search algorithms may be applied to build high-quality networks in medium- or large-scale problems, as exhaustive search is often feasible only for small problems. In this paper, we present our new algorithm, ABC-Miner, and propose several extensions to it. ABC-Miner uses ant colony optimization for learning the structure of Bayesian network classifiers. We report extended computational results comparing the performance of our algorithm with eight other classification algorithms, namely six variations of well-known Bayesian network classifiers, cAnt-Miner for discovering classification rules and a support vector machine algorithm.     

Synthetic regulatory tools for microbial engineering

Microbial engineering requires accurate information about cellular metabolic networks and a set of molecular tools that can be predictably applied to the efficient redesign of such networks. Recent advances in the field of metabolic engineering and synthetic biology, particularly the development of molecular tools for synthetic regulation in the static and dynamic control of gene expression, have increased our ability to efficiently balance the expression of genes in various biological systems. It would accelerate the creation of synthetic pathways and genetic programs capable of adapting to environmental changes in real time to perform the programmed cellular behavior. In this paper, we review current developments in the field of synthetic regulatory tools for static and dynamic control of microbial gene expression.     

PKC and PLA2: Probing the complexities of the calcium network

Lipid signaling and phosphorylation cascades are fundamental to calcium signaling networks. In this review, we will discuss the recent laboratory findings for the phospholipase A₂ (PLA₂)/protein kinase C (PKC) pathway within cellular calcium networks. The complexity and connectivity of these ubiquitous cellular signals make interpretation of experimental results extremely challenging. We present here computational methods which have been developed to conquer such complex data, and how they can be used to make models capable of accurately predicting cellular responses within multiple calcium signaling pathways. We propose that information obtained from network analysis and computational techniques provides a rich source of knowledge which can be directly translated to the laboratory benchtop.     

Petri net-based method for the analysis of the dynamics of signal propagation in signaling pathways

MOTIVATION: Cellular signaling networks are dynamic systems that propagate and process information, and, ultimately, cause phenotypical responses. Understanding the circuitry of the information flow in cells is one of the keys to understanding complex cellular processes. The development of computational quantitative models is a promising avenue for attaining this goal. Not only does the analysis of the simulation data based on the concentration variations of biological compounds yields information about systemic state changes, but it is also very helpful for obtaining information about the dynamics of signal propagation. RESULTS: This article introduces a new method for analyzing the dynamics of signal propagation in signaling pathways using Petri net theory. The method is demonstrated with the Ca(2+)/calmodulin-dependent protein kinase II (CaMKII) regulation network. The results constitute temporal information about signal propagation in the network, a simplified graphical representation of the network and of the signal propagation dynamics and a characterization of some signaling routes as regulation motifs.     

Interplay between Graph Topology and Correlations of Third Order in Spiking Neuronal Networks

The study of processes evolving on networks has recently become a very popular research field, not only because of the rich mathematical theory that underpins it, but also because of its many possible applications, a number of them in the field of biology. Indeed, molecular signaling pathways, gene regulation, predator-prey interactions and the communication between neurons in the brain can be seen as examples of networks with complex dynamics. The properties of such dynamics depend largely on the topology of the underlying network graph. In this work, we want to answer the following question: Knowing network connectivity, what can be said about the level of third-order correlations that will characterize the network dynamics? We consider a linear point process as a model for pulse-coded, or spiking activity in a neuronal network. Using recent results from theory of such processes, we study third-order correlations between spike trains in such a system and explain which features of the network graph (i.e. which topological motifs) are responsible for their emergence. Comparing two different models of network topology—random networks of Erdős-Rényi type and networks with highly interconnected hubs—we find that, in random networks, the average measure of third-order correlations does not depend on the local connectivity properties, but rather on global parameters, such as the connection probability. This, however, ceases to be the case in networks with a geometric out-degree distribution, where topological specificities have a strong impact on average correlations.