An algebraic-combinatorial model for the identification and mapping of biochemical pathways

We develop the mathematical machinery for the construction of an algebraic-combinatorial model using Petri nets to construct an oriented matroid representation of biochemical pathways. For demonstration purposes, we use a model metabolic pathway example from the literature to derive a general biochemical reaction network model. The biomolecular networks define a connectivity matrix that identifies a linear representation of a Petri net. The sub-circuits that span a reaction network are subject to flux conservation laws. The conservation laws correspond to algebraic-combinatorial dual invariants, that are called S-(state) and T-(transition) invariants. Each invariant has an associated minimum support. We show that every minimum support of a Petri net invariant defines a unique signed sub-circuit representation. We prove that the family of signed sub-circuits has an implicit order that defines an oriented matroid. The oriented matroid is then used to identify the feasible sub-circuit pathways that span the biochemical network as the positive cycles in a hyper-digraph.     

Identifying All Moiety Conservation Laws in Genome-Scale Metabolic Networks

The stoichiometry of a metabolic network gives rise to a set of conservation laws for the aggregate level of specific pools of metabolites, which, on one hand, pose dynamical constraints that cross-link the variations of metabolite concentrations and, on the other, provide key insight into a cell''s metabolic production capabilities. When the conserved quantity identifies with a chemical moiety, extracting all such conservation laws from the stoichiometry amounts to finding all non-negative integer solutions of a linear system, a programming problem known to be NP-hard. We present an efficient strategy to compute the complete set of integer conservation laws of a genome-scale stoichiometric matrix, also providing a certificate for correctness and maximality of the solution. Our method is deployed for the analysis of moiety conservation relationships in two large-scale reconstructions of the metabolism of the bacterium E. coli, in six tissue-specific human metabolic networks, and, finally, in the human reactome as a whole, revealing that bacterial metabolism could be evolutionarily designed to cover broader production spectra than human metabolism. Convergence to the full set of moiety conservation laws in each case is achieved in extremely reduced computing times. In addition, we uncover a scaling relation that links the size of the independent pool basis to the number of metabolites, for which we present an analytical explanation.     

Energy balance for analysis of complex metabolic networks

Predicting behavior of large-scale biochemical networks represents one of the greatest challenges of bioinformatics and computational biology. Computational tools for predicting fluxes in biochemical networks are applied in the fields of integrated and systems biology, bioinformatics, and genomics, and to aid in drug discovery and identification of potential drug targets. Approaches, such as flux balance analysis (FBA), that account for the known stoichiometry of the reaction network while avoiding implementation of detailed reaction kinetics are promising tools for the analysis of large complex networks. Here we introduce energy balance analysis (EBA)--the theory and methodology for enforcing the laws of thermodynamics in such simulations--making the results more physically realistic and revealing greater insight into the regulatory and control mechanisms operating in complex large-scale systems. We show that EBA eliminates thermodynamically infeasible results associated with FBA.     

Conservation analysis in biochemical networks: computational issues for software writers

Large scale genomic studies are generating significant amounts of data on the structure of cellular networks. This is in contrast to kinetic data, which is frequently absent, unreliable or fragmentary. There is, therefore, a desire by many in the community to investigate the potential rewards of analyzing the more readily available topological data. This brief review is concerned with a particular property of biological networks, namely structural conservations (e.g. moiety conserved cycles). There has been much discussion in the literature on these cycles but a review on the computational issues related to conserved cycles has been missing. This review is concerned with the detection and characterization of conservation relations in arbitrary networks and related issues, which impinge on simulation simulation software writers. This review will not address flux balance constraints or small-world type analyses in any significant detail.     

Construction of simple pathways and simple cycles in ecosystems

We present software tools for overcoming the problem of combinatoricsin the enumeration of simple pathways and simple cycles in afirst flow-through analysis of carbon transfer in large ecosystems.Rather than search through the very large number of potentialroutes in a reasonably sized ecosystem for the relatively smallnumber of actual routes, our main algorithm performs an efficientrule-based construction of the actual routes. The enumerationof the unique pathways becomes tractable in terms of CPU time,which increases linearly with ecosystem size and connectedness.Networks of up to 80 entities can be evaluated using our software.     

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.     

Reconstruction of gene networks using Bayesian learning and manipulation experiments

MOTIVATION: The analysis of high-throughput experimental data, for example from microarray experiments, is currently seen as a promising way of finding regulatory relationships between genes. Bayesian networks have been suggested for learning gene regulatory networks from observational data. Not all causal relationships can be inferred from correlation data alone. Often several equivalent but different directed graphs explain the data equally well. Intervention experiments where genes are manipulated can help to narrow down the range of possible networks. RESULTS: We describe an active learning algorithm that suggests an optimized sequence of intervention experiments. Simulation experiments show that our selection scheme is better than an unguided choice of interventions in learning the correct network and compares favorably in running time and results with methods based on value of information calculations.     

A Parallel Implementation of the Network Identification by Multiple Regression (NIR) Algorithm to Reverse-Engineer Regulatory Gene Networks

The reverse engineering of gene regulatory networks using gene expression profile data has become crucial to gain novel biological knowledge. Large amounts of data that need to be analyzed are currently being produced due to advances in microarray technologies. Using current reverse engineering algorithms to analyze large data sets can be very computational-intensive. These emerging computational requirements can be met using parallel computing techniques. It has been shown that the Network Identification by multiple Regression (NIR) algorithm performs better than the other ready-to-use reverse engineering software. However it cannot be used with large networks with thousands of nodes - as is the case in biological networks - due to the high time and space complexity. In this work we overcome this limitation by designing and developing a parallel version of the NIR algorithm. The new implementation of the algorithm reaches a very good accuracy even for large gene networks, improving our understanding of the gene regulatory networks that is crucial for a wide range of biomedical applications.     

Approximations and their consequences for dynamic modelling of signal transduction pathways

Signal transduction is the process by which the cell converts one kind of signal or stimulus into another. This involves a sequence of biochemical reactions, carried out by proteins. The dynamic response of complex cell signalling networks can be modelled and simulated in the framework of chemical kinetics. The mathematical formulation of chemical kinetics results in a system of coupled differential equations. Simplifications can arise through assumptions and approximations. The paper provides a critical discussion of frequently employed approximations in dynamic modelling of signal transduction pathways. We discuss the requirements for conservation laws, steady state approximations, and the neglect of components. We show how these approximations simplify the mathematical treatment of biochemical networks but we also demonstrate differences between the complete system and its approximations with respect to the transient and steady state behavior.     

Elucidation and structural analysis of conserved pools for genome-scale metabolic reconstructions

In this article, we introduce metabolite concentration coupling analysis (MCCA) to study conservation relationships for metabolite concentrations in genome-scale metabolic networks. The analysis allows the global identification of subsets of metabolites whose concentrations are always coupled within common conserved pools. Also, the minimal conserved pool identification (MCPI) procedure is developed for elucidating conserved pools for targeted metabolites without computing the entire basis conservation relationships. The approaches are demonstrated on genome-scale metabolic reconstructions of Helicobacter pylori, Escherichia coli, and Saccharomyces cerevisiae. Despite significant differences in the size and complexity of the examined organism's models, we find that the concentrations of nearly all metabolites are coupled within a relatively small number of subsets. These correspond to the overall exchange of carbon molecules into and out of the networks, interconversion of energy and redox cofactors, and the transfer of nitrogen, sulfur, phosphate, coenzyme A, and acyl carrier protein moieties among metabolites. The presence of large conserved pools can be viewed as global biophysical barriers protecting cellular systems from stresses, maintaining coordinated interconversions between key metabolites, and providing an additional mode of global metabolic regulation. The developed approaches thus provide novel and versatile tools for elucidating coupling relationships between metabolite concentrations with implications in biotechnological and medical applications.     

The River Network Toolkit – RivTool

Freshwater ecosystems are some of the most endangered environments in the world, being affected at multiple scales by the surrounding landscape and human activities therein. Effective research, conservation and management of these ecosystems requires integrating environmental and landscape data with hierarchic river networks by means of summarisation and synthesis of information for large and comprehensive areas at different scales (e.g. basin, sub‐basin, upstream drainage area). The dendritic nature of river networks, the need to tackle multiple scales and the ever‐growing sources of digital information (e.g. temperature or land use data grids) have increasingly led to hardly manageable processing time and stringent hardware requirements when integrating and working with this information. Here we present the River Network Toolkit (RivTool), a software that uses only tabular data to derive and calculate new information at multiple scales for riverine landscapes. It uses data from linear hierarchical river networks and the environmental/landscape data from their respective drainage areas. The software allows the acquisition of: 1) information that characterises river networks based on its topographic nature; 2) data obtained via mathematical calculations that account for the hierarchical and network nature of these systems; and 3) output information using different spatial data sources (e.g. climatic, land use, topologic) that result from up and downstream summarisations. This user‐friendly software considers two units of analysis (segment and sub‐basin) and is time effective even with large datasets. RivTool facilitates and reduces the time required for extracting information for freshwater ecosystems, and may thus contribute to increase scientific productivity, efficiency and accurateness when generating new or improving existing knowledge on large‐scale patterns and processes in river networks.     

Thermodynamic Constraints in Kinetic Modeling: Thermodynamic‐Kinetic Modeling in Comparison to Other Approaches

Kinetic models of reaction networks may easily violate the laws of thermodynamics and the principle of detailed balance. In large network models, the constraints that are imposed by these laws are particularly difficult to address. This hinders modeling of biochemical reaction networks. Thermodynamic‐kinetic modeling is a method that provides a thermodynamically sound and formally appealing way for deriving dynamic model equations of reaction systems. State variables of this approach are thermokinetic potentials that describe the ability of compounds to drive a reaction. A compound has a parameter called capacity, which is the ratio of its concentration and thermokinetic potential. A reaction is described by its resistance which is the ratio of the thermokinetic driving force and flux. In these aspects, the formalism is similar to the modeling formalism for electrical networks and an analogous graphical representation is possible. The thermodynamic‐kinetic modeling formalism is equivalent to the traditional kinetic modeling formalism with the exception that it is not possible to build thermodynamically infeasible models. Here, the thermodynamic‐kinetic modeling formalism is reviewed, compared to other approaches, and some of its advantages are worked out. In contrast to other approaches, thermodynamic‐kinetic modeling does not rely on an explicit enumeration of stoichiometric cycles. It is capable of describing rate laws far from equilibrium. Further, the parameterization by capacities and resistances is particularly intuitive and powerful.     

Filtering of ineffective siRNAs and improved siRNA design tool

MOTIVATION: Short interfering RNAs (siRNAs) can be used to suppress gene expression and possess many potential applications in therapy, but how to design an effective siRNA is still not clear. Based on the MPI (Max-Planck-Institute) basic principles, a number of siRNA design tools have been developed recently. The set of candidates reported by these tools is usually large and often contains ineffective siRNAs. In view of this, we initiate the study of filtering ineffective siRNAs. RESULTS: The contribution of this paper is 2-fold. First, we propose a fair scheme to compare existing design tools based on real data in the literature. Second, we attempt to improve the MPI principles and existing tools by an algorithm that can filter ineffective siRNAs. The algorithm is based on some new observations on the secondary structure, which we have verified by AI techniques (decision trees and support vector machines). We have tested our algorithm together with the MPI principles and the existing tools. The results show that our filtering algorithm is effective. AVAILABILITY: The siRNA design software tool can be found in the website http://www.cs.hku.hk/~sirna/ CONTACT: smyiu@cs.hku.hk     

Genome-Scale Co-Expression Network Comparison across Escherichia coli and Salmonella enterica Serovar Typhimurium Reveals Significant Conservation at the Regulon Level of Local Regulators Despite Their Dissimilar Lifestyles

Availability of genome-wide gene expression datasets provides the opportunity to study gene expression across different organisms under a plethora of experimental conditions. In our previous work, we developed an algorithm called COMODO (COnserved MODules across Organisms) that identifies conserved expression modules between two species. In the present study, we expanded COMODO to detect the co-expression conservation across three organisms by adapting the statistics behind it. We applied COMODO to study expression conservation/divergence between Escherichia coli, Salmonella enterica, and Bacillus subtilis. We observed that some parts of the regulatory interaction networks were conserved between E. coli and S. enterica especially in the regulon of local regulators. However, such conservation was not observed between the regulatory interaction networks of B. subtilis and the two other species. We found co-expression conservation on a number of genes involved in quorum sensing, but almost no conservation for genes involved in pathogenicity across E. coli and S. enterica which could partially explain their different lifestyles. We concluded that despite their different lifestyles, no significant rewiring have occurred at the level of local regulons involved for instance, and notable conservation can be detected in signaling pathways and stress sensing in the phylogenetically close species S. enterica and E. coli. Moreover, conservation of local regulons seems to depend on the evolutionary time of divergence across species disappearing at larger distances as shown by the comparison with B. subtilis. Global regulons follow a different trend and show major rewiring even at the limited evolutionary distance that separates E. coli and S. enterica.     

Programming biological models in Python using PySB

Mathematical equations are fundamental to modeling biological networks, but as networks get large and revisions frequent, it becomes difficult to manage equations directly or to combine previously developed models. Multiple simultaneous efforts to create graphical standards, rule‐based languages, and integrated software workbenches aim to simplify biological modeling but none fully meets the need for transparent, extensible, and reusable models. In this paper we describe PySB, an approach in which models are not only created using programs, they are programs. PySB draws on programmatic modeling concepts from little b and ProMot, the rule‐based languages BioNetGen and Kappa and the growing library of Python numerical tools. Central to PySB is a library of macros encoding familiar biochemical actions such as binding, catalysis, and polymerization, making it possible to use a high‐level, action‐oriented vocabulary to construct detailed models. As Python programs, PySB models leverage tools and practices from the open‐source software community, substantially advancing our ability to distribute and manage the work of testing biochemical hypotheses. We illustrate these ideas using new and previously published models of apoptosis.     

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.     

RNAMotifScanX: a graph alignment approach for RNA structural motif identification

RNA structural motifs are recurrent three-dimensional (3D) components found in the RNA architecture. These RNA structural motifs play important structural or functional roles and usually exhibit highly conserved 3D geometries and base-interaction patterns. Analysis of the RNA 3D structures and elucidation of their molecular functions heavily rely on efficient and accurate identification of these motifs. However, efficient RNA structural motif search tools are lacking due to the high complexity of these motifs. In this work, we present RNAMotifScanX, a motif search tool based on a base-interaction graph alignment algorithm. This novel algorithm enables automatic identification of both partially and fully matched motif instances. RNAMotifScanX considers noncanonical base-pairing interactions, base-stacking interactions, and sequence conservation of the motifs, which leads to significantly improved sensitivity and specificity as compared with other state-of-the-art search tools. RNAMotifScanX also adopts a carefully designed branch-and-bound technique, which enables ultra-fast search of large kink-turn motifs against a 23S rRNA. The software package RNAMotifScanX is implemented using GNU C++, and is freely available from http://genome.ucf.edu/RNAMotifScanX.     

Subnetwork hierarchies of biochemical pathways

MOTIVATION: The vastness and complexity of the biochemical networks that have been mapped out by modern genomics calls for decomposition into subnetworks. Such networks can have inherent non-local features that require the global structure to be taken into account in the decomposition procedure. Furthermore, basic questions such as to what extent the network (graph theoretically) can be said to be built by distinct subnetworks are little studied. RESULTS: We present a method to decompose biochemical networks into subnetworks based on the global geometry of the network. This method enables us to analyze the full hierarchical organization of biochemical networks and is applied to 43 organisms from the WIT database. Two types of biochemical networks are considered: metabolic networks and whole-cellular networks (also including for example information processes). Conceptual and quantitative ways of describing the hierarchical ordering are discussed. The general picture of the metabolic networks arising from our study is that of a few core-clusters centred around the most highly connected substances enclosed by other substances in outer shells, and a few other well-defined subnetworks. AVAILABILITY: An implementation of our algorithm and other programs for analyzing the data is available from http://www.tp.umu.se/forskning/networks/meta/ SUPPLEMENTARY INFORMATION: Supplementary material is available at http://www.tp.umu.se/forskning/networks/meta/