Graph-theoretic methods for the analysis of chemical and biochemical networks. I. Multistability and oscillations in ordinary differential equation models

A chemical mechanism is a model of a chemical reaction network consisting of a set of elementary reactions that express how molecules react with each other. In classical mass-action kinetics, a mechanism implies a set of ordinary differential equations (ODEs) which govern the time evolution of the concentrations. In this article, ODE models of chemical kinetics that have the potential for multiple positive equilibria or oscillations are studied. We begin by considering some methods of stability analysis based on the digraph of the Jacobian matrix. We then prove two theorems originally given by A. N. Ivanova which correlate the bifurcation structure of a mass-action model to the properties of a bipartite graph with nodes representing chemical species and reactions. We provide several examples of the application of these theorems.     

From minimal signed circuits to the dynamics of Boolean regulatory networks

It is acknowledged that the presence of positive or negative circuits in regulatory networks such as genetic networks is linked to the emergence of significant dynamical properties such as multistability (involved in differentiation) and periodic oscillations (involved in homeostasis). Rules proposed by the biologist R. Thomas assert that these circuits are necessary for such dynamical properties. These rules have been studied by several authors. Their obvious interest is that they relate the rather simple information contained in the structure of the network (signed circuits) to its much more complex dynamical behaviour. We prove in this article a nontrivial converse of these rules, namely that certain positive or negative circuits in a regulatory graph are actually sufficient for the observation of a restricted form of the corresponding dynamical property, differentiation or homeostasis. More precisely, the crucial property that we require is that the circuit be globally minimal. We then apply these results to the vertebrate immune system, and show that the two minimal functional positive circuits of the model indeed behave as modules which combine to explain the presence of the three stable states corresponding to the Th0, Th1 and Th2 cells. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.     

Genetic regulation networks: circuits,regulons and attractors

We deal in this paper with the concept of genetic regulation network. The genes expression observed through the bio-array imaging allows the geneticist to obtain the intergenic interaction matrix W of the network. The interaction graph G associated to W presents in general interesting features like connected components, gardens of Eden, positive and negative circuits (or loops), and minimal components having 1 positive and 1 negative loop called regulons. Depending on parameters values like the connectivity coefficient K(W) and the mean inhibition weight I(W), the genetic regulation network can present several dynamical behaviours (fixed configuration, limit cycle of configurations) called attractors, when the observation time increases. We give some examples of such genetic regulation networks and analyse their dynamical properties and their biological consequences.     

Antagonism and bistability in protein interaction networks

A protein interaction network (PIN) is a set of proteins that modulate one another's activities by regulated synthesis and degradation, by reversible binding to form complexes, and by catalytic reactions (e.g., phosphorylation and dephosphorylation). Most PINs are so complex that their dynamical characteristics cannot be deduced accurately by intuitive reasoning alone. To predict the properties of such networks, many research groups have turned to mathematical models (differential equations based on standard biochemical rate laws, e.g., mass-action, Michaelis-Menten, Hill). When using Michaelis-Menten rate expressions to model PINs, care must be exercised to avoid making inconsistent assumptions about enzyme-substrate complexes. We show that an appealingly simple model of a PIN that functions as a bistable switch is compromised by neglecting enzyme-substrate intermediates. When the neglected intermediates are put back into the model, bistability of the switch is lost. The theory of chemical reaction networks predicts that bistability can be recovered by adding specific reaction channels to the molecular mechanism. We explore two very different routes to recover bistability. In both cases, we show how to convert the original 'phenomenological' model into a consistent set of mass-action rate laws that retains the desired bistability properties. Once an equivalent model is formulated in terms of elementary chemical reactions, it can be simulated accurately either by deterministic differential equations or by Gillespie's stochastic simulation algorithm.     

Computing weakly reversible linearly conjugate chemical reaction networks with minimal deficiency

Mass-action kinetics is frequently used in systems biology to model the behavior of interacting chemical species. Many important dynamical properties are known to hold for such systems if their underlying networks are weakly reversible and have a low deficiency. In particular, the Deficiency Zero and Deficiency One Theorems guarantee strong regularity with regards to the number and stability of positive equilibrium states. It is also known that chemical reaction networks with distinct reaction structure can admit mass-action systems with the same qualitative dynamics. The theory of linear conjugacy encapsulates the cases where this relationship is captured by a linear transformation. In this paper, we propose a mixed-integer linear programming algorithm capable of determining the minimal deficiency weakly reversible reaction network which admits a mass-action system which is linearly conjugate to a given reaction network.     

Positive and negative feedback: striking a balance between necessary antagonists

Most biological regulation systems comprise feedback circuits as crucial components. Negative feedback circuits have been well understood for a very long time; indeed, their understanding has been the basis for the engineering of cybernetic machines exhibiting stable behaviour. The importance of positive feedback circuits, considered as "vicious circles", has however been underestimated. In this article, we give a demonstration based on degree theory for vector fields of the conjecture, made by René Thomas, that the presence of positive feedback circuits is a necessary condition for autonomous differential systems, covering a wide class of biologically relevant systems, to possess multiple steady states. We also show ways to derive constraints on the weights of positive and negative feedback circuits. These qualitative and quantitative results provide, respectively, structural constraints (i.e. related to the interaction graph) and numerical constraints (i.e. related to the magnitudes of the interactions) on systems exhibiting complex behaviours, and should make it easier to reverse-engineer the interaction networks animating those systems on the basis of partial, sometimes unreliable, experimental data. We illustrate these concepts on a model multistable switch, in the context of cellular differentiation, showing a requirement for sufficient cooperativity. Further developments are expected in the discovery and modelling of regulatory networks in general, and in the interpretation of bio-array hybridization and proteomics experiments in particular.     

Autocatalysis in Reaction Networks

The persistence conjecture is a long-standing open problem in chemical reaction network theory. It concerns the behavior of solutions to coupled ODE systems that arise from applying mass-action kinetics to a network of chemical reactions. The idea is that if all reactions are reversible in a weak sense, then no species can go extinct. A notion that has been found useful in thinking about persistence is that of “critical siphon.” We explore the combinatorics of critical siphons, with a view toward the persistence conjecture. We introduce the notions of “drainable” and “self-replicable” (or autocatalytic) siphons. We show that: Every minimal critical siphon is either drainable or self-replicable; reaction networks without drainable siphons are persistent; and nonautocatalytic weakly reversible networks are persistent. Our results clarify that the difficulties in proving the persistence conjecture are essentially due to competition between drainable and self-replicable siphons.     

Pairwise alignment of protein interaction networks.

With an ever-increasing amount of available data on protein-protein interaction (PPI) networks and research revealing that these networks evolve at a modular level, discovery of conserved patterns in these networks becomes an important problem. Although available data on protein-protein interactions is currently limited, recently developed algorithms have been shown to convey novel biological insights through employment of elegant mathematical models. The main challenge in aligning PPI networks is to define a graph theoretical measure of similarity between graph structures that captures underlying biological phenomena accurately. In this respect, modeling of conservation and divergence of interactions, as well as the interpretation of resulting alignments, are important design parameters. In this paper, we develop a framework for comprehensive alignment of PPI networks, which is inspired by duplication/divergence models that focus on understanding the evolution of protein interactions. We propose a mathematical model that extends the concepts of match, mismatch, and gap in sequence alignment to that of match, mismatch, and duplication in network alignment and evaluates similarity between graph structures through a scoring function that accounts for evolutionary events. By relying on evolutionary models, the proposed framework facilitates interpretation of resulting alignments in terms of not only conservation but also divergence of modularity in PPI networks. Furthermore, as in the case of sequence alignment, our model allows flexibility in adjusting parameters to quantify underlying evolutionary relationships. Based on the proposed model, we formulate PPI network alignment as an optimization problem and present fast algorithms to solve this problem. Detailed experimental results from an implementation of the proposed framework show that our algorithm is able to discover conserved interaction patterns very effectively, in terms of both accuracies and computational cost.     

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.     

The modularity of biological regulatory networks

A useful approach to complex regulatory networks consists of modeling their elements and interactions by Boolean equations. In this context, feedback circuits (i.e. circular sequences of interactions) have been shown to play key dynamical roles: whereas positive circuits are able to generate multistationarity, negative circuits may generate oscillatory behavior. In this paper, we principally focus on the case of gene networks. These are represented by fully connected Boolean networks where each element interacts with all elements including itself. Flexibility in network design is introduced by the use of Boolean parameters, one associated with each interaction or group of interactions affecting a given element. Within this formalism, a feedback circuit will generate its typical dynamical behavior (i.e. multistationarity or oscillations) only for appropriate values of some of the logical parameters. Whenever it does, we say that the circuit is 'functional'. More interestingly, this formalism allows the computation of the constraints on the logical parameters to have any feedback circuit functional in a network. Using this methodology, we found that the fraction of the total number of consistent combinations of parameter values that make a circuit functional decreases geometrically with the circuit length. From a biological point of view, this suggests that regulatory networks could be decomposed into small and relatively independent feedback circuits or 'regulatory modules'.     

Structural distance and evolutionary relationship of networks

Exploring common features and universal qualities shared by a particular class of networks in biological and other domains is one of the important aspects of evolutionary study. In an evolving system, evolutionary mechanism can cause functional changes that forces the system to adapt to new configurations of interaction pattern between the components of that system (e.g. gene duplication and mutation play a vital role for changing the connectivity structure in many biological networks. The evolutionary relation between two systems can be retraced by their structural differences). The eigenvalues of the normalized graph Laplacian not only capture the global properties of a network, but also local structures that are produced by graph evolutions (like motif duplication or joining). The spectrum of this operator carries many qualitative aspects of a graph. Given two networks of different sizes, we propose a method to quantify the topological distance between them based on the contrasting spectrum of normalized graph Laplacian. We find that network architectures are more similar within the same class compared to between classes. We also show that the evolutionary relationships can be retraced by the structural differences using our method. We analyze 43 metabolic networks from different species and mark the prominent separation of three groups: Bacteria, Archaea and Eukarya. This phenomenon is well captured in our findings that support the other cladistic results based on gene content and ribosomal RNA sequences. Our measure to quantify the structural distance between two networks is useful to elucidate evolutionary relationships.     

A Structural Classification of Candidate Oscillatory and Multistationary Biochemical Systems

Molecular systems are uncertain: The variability of reaction parameters and the presence of unknown interactions can weaken the predictive capacity of solid mathematical models. However, strong conclusions on the admissible dynamic behaviors of a model can often be achieved without detailed knowledge of its specific parameters. In systems with a sign-definite Jacobian, for instance, cycle-based criteria related to the famous Thomas’ conjectures have been largely used to characterize oscillatory and multistationary dynamic outcomes. We build on the rich literature focused on the identification of potential oscillatory and multistationary behaviors using parameter-free criteria. We propose a classification for sign-definite non-autocatalytic biochemical networks, which summarizes several existing results in the literature. We call weak (strong) candidate oscillators systems which can possibly (exclusively) transition to instability due to the presence of a complex pair of eigenvalues, while we call weak (strong) candidate multistationary systems those which can possibly (exclusively) transition to instability due to the presence of a real eigenvalue. For each category, we provide a characterization based on the exclusive or simultaneous presence of positive and negative cycles in the associated sign graph. Most realistic examples of biochemical networks fall in the gray area of systems in which both positive and negative cycles are present: Therefore, both oscillatory and bistable behaviors are in principle possible. However, many canonical example circuits exhibiting oscillations or bistability fall in the categories of strong candidate oscillators/multistationary systems, in agreement with our results.     

RNA Graph Partitioning for the Discovery of RNA Modularity: A Novel Application of Graph Partition Algorithm to Biology

Graph representations have been widely used to analyze and design various economic, social, military, political, and biological networks. In systems biology, networks of cells and organs are useful for understanding disease and medical treatments and, in structural biology, structures of molecules can be described, including RNA structures. In our RNA-As-Graphs (RAG) framework, we represent RNA structures as tree graphs by translating unpaired regions into vertices and helices into edges. Here we explore the modularity of RNA structures by applying graph partitioning known in graph theory to divide an RNA graph into subgraphs. To our knowledge, this is the first application of graph partitioning to biology, and the results suggest a systematic approach for modular design in general. The graph partitioning algorithms utilize mathematical properties of the Laplacian eigenvector (µ2) corresponding to the second eigenvalues (λ2) associated with the topology matrix defining the graph: λ2 describes the overall topology, and the sum of µ2′s components is zero. The three types of algorithms, termed median, sign, and gap cuts, divide a graph by determining nodes of cut by median, zero, and largest gap of µ2′s components, respectively. We apply these algorithms to 45 graphs corresponding to all solved RNA structures up through 11 vertices (∼220 nucleotides). While we observe that the median cut divides a graph into two similar-sized subgraphs, the sign and gap cuts partition a graph into two topologically-distinct subgraphs. We find that the gap cut produces the best biologically-relevant partitioning for RNA because it divides RNAs at less stable connections while maintaining junctions intact. The iterative gap cuts suggest basic modules and assembly protocols to design large RNA structures. Our graph substructuring thus suggests a systematic approach to explore the modularity of biological networks. In our applications to RNA structures, subgraphs also suggest design strategies for novel RNA motifs.     

Hierarchy of metabolic compounds based on their synthesising capacity

The concept of scopes is applied to analyse large metabolic networks. Scopes are defined as sets of metabolites that can be synthesised by a metabolic network when it is provided with given seeds (Sets of initial metabolic compounds). Thus, scopes represent synthesising capacities of the seeds in the network. A hierarchy is discussed in the sense that compounds, which are part of the scope of another compound, possess scopes themselves that are subsets of the former scope. This hierarchy is analysed by means of a directed acyclic graph. Using a simple chemical model, it is found that this hierarchy contains specific structures that can, to a large extent, be explained by the chemical composition of the participating compounds. In this way, it represents a new kind of map of metabolic networks, arranging the metabolic compounds according to their chemical capacity.     

SPiD: a subtilis protein interaction database.

MOTIVATION: Protein-protein interactions are a potential source of valuable clues in determining the functional role of as yet uncharacterized gene products in metabolic pathways. Graph-like structures emerging from the accumulation of interaction data make it difficult to maintain a consistent and global overview by hand. Bioinformatics tools are needed to perform this graph visualization while maintaining a link to the experimental data. RESULTS: "SPiD" is an online database for exploring networks of interacting proteins in Bacillus subtilis characterized by the two-hybrid system. Graphical displays of interaction networks are created dynamically as users interactively navigate through these networks. Third party applications can interface the database through a Common Object Request Broker Architecture (CORBA) tier. AVAILABILITY: SPiD is available through its web site at http://www-mig.versailles.inra.fr/bdsi/SPiD, and through an Interoperable Object Reference (IOR) and its associated Interface Definition Language (IDL). CONTACT: hoebeke@versailles.inra.fr     

Multiple equilibria in complex chemical reaction networks: extensions to entrapped species models

In two earlier papers, means were provided to decide the capacity of complex chemical reaction networks, taken with mass-action kinetics, to admit multiple equilibria in the context of the isothermal homogeneous continuous flow stirred tank reactor (CFSTR). In such a reactor, all species are deemed to be in the outflow, a fact which has an important bearing on the nature of the governing equations. In contrast, one can imagine CFSTR-like models of the cell in which certain large molecules (e.g., enzymes) remain entrapped within the cell, whereas smaller ones (e.g., metabolites) are free to diffuse through the cell boundary. Although such models bear a strong physical resemblance to the classical CFSTR picture, there are substantive differences in the corresponding mathematics. Without a presumption of mass-action kinetics, this research is intended to indicate a general way in which results about uniqueness of equilibria in the classical CFSTR context extend to entrapped species models.