Algorithmic approaches for computing elementary modes in large biochemical reaction networks

On the representativeness and stability of a set of EFMs

MOTIVATION

Elementary flux modes are a well-known tool for analyzing metabolic networks. The whole set of elementary flux modes (EFMs) cannot be computed in most genome-scale networks due to their large cardinality. Therefore, different methods have been proposed to compute a smaller subset of EFMs that can be used for studying the structure of the network. These latter methods pose the problem of studying the representativeness of the calculated subset. In this article, we present a methodology to tackle this problem.

RESULTS

We have introduced the concept of stability for a particular network parameter and its relation to the representativeness of the EFM extraction method studied. We have also defined several metrics to study and compare the EFM biases. We have applied these techniques to compare the relative behavior of previously proposed methods in two case studies. Furthermore, we have presented a new method for the EFM computation (PiEFM), which is more stable (less biased) than previous ones, has suitable representativeness measures, and exhibits better variability in the extracted EFMs.

AVAILABILITY AND IMPLEMENTATION

Software and additional material are freely available at https://github.com/biogacop/PiEFM.

Answer Set Programming for Computing Constraints-Based Elementary Flux Modes: Application to Escherichia coli Core Metabolism

Elementary Flux Modes (EFMs) provide a rigorous basis to systematically characterize the steady state, cellular phenotypes, as well as metabolic network robustness and fragility. However, the number of EFMs typically grows exponentially with the size of the metabolic network, leading to excessive computational demands, and unfortunately, a large fraction of these EFMs are not biologically feasible due to system constraints. This combinatorial explosion often prevents the complete analysis of genome-scale metabolic models. Traditionally, EFMs are computed by the double description method, an efficient algorithm based on matrix calculation; however, only a few constraints can be integrated into this computation. They must be monotonic with regard to the set inclusion of the supports; otherwise, they must be treated in post-processing and thus do not save computational time. We present aspefm, a hybrid computational tool based on Answer Set Programming (ASP) and Linear Programming (LP) that permits the computation of EFMs while implementing many different types of constraints. We apply our methodology to the Escherichia coli core model, which contains 226×106 EFMs. In considering transcriptional and environmental regulation, thermodynamic constraints, and resource usage considerations, the solution space is reduced to 1118 EFMs that can be computed directly with aspefm. The solution set, for E. coli growth on O2 gradients spanning fully aerobic to anaerobic, can be further reduced to four optimal EFMs using post-processing and Pareto front analysis.

Flux Coupling and the Objective Functions' Length in EFMs

Structural analysis of constraint-based metabolic network models attempts to find the network's properties by searching for subsets of suitable modes or Elementary Flux Modes (EFMs). One useful approach is based on Linear Program (LP) techniques, which introduce an objective function to convert the stoichiometric and thermodynamic constraints into a linear program (LP), using additional constraints to generate different nontrivial modes. This work introduces FLFS-FC (Fixed Length Function Sampling with Flux Coupling), a new approach to increase the efficiency of generation of large sets of different EFMs for the network. FLFS-FC is based on the importance of the length of the objective functions used in the associated LP problem and the imposition of additional negative constraints. Our proposal overrides some of the known drawbacks associated with the EFM extraction, such as the appearance of unfeasible problems or multiple repeated solutions arising from different LP problems.

Boosting the extraction of elementary flux modes in genome-scale metabolic networks using the linear programming approach

MOTIVATION

Elementary flux modes (EFMs) are a key tool for analyzing genome-scale metabolic networks, and several methods have been proposed to compute them. Among them, those based on solving linear programming (LP) problems are known to be very efficient if the main interest lies in computing large enough sets of EFMs.

RESULTS

Here, we propose a new method called EFM-Ta that boosts the efficiency rate by analyzing the information provided by the LP solver. We base our method on a further study of the final tableau of the simplex method. By performing additional elementary steps and avoiding trivial solutions consisting of two cycles, we obtain many more EFMs for each LP problem posed, improving the efficiency rate of previously proposed methods by more than one order of magnitude.

AVAILABILITY AND IMPLEMENTATION

Software is freely available at https://github.com/biogacop/Boost_LP_EFM.

CONTACT

fguil@um.es.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Towards scaling elementary flux mode computation

While elementary flux mode (EFM) analysis is now recognized as a cornerstone computational technique for cellular pathway analysis and engineering, EFM application to genome-scale models remains computationally prohibitive. This article provides a review of aspects of EFM computation that elucidates bottlenecks in scaling EFM computation. First, algorithms for computing EFMs are reviewed. Next, the impact of redundant constraints, sensitivity to constraint ordering and network compression are evaluated. Then, the advantages and limitations of recent parallelization and GPU-based efforts are highlighted. The article then reviews alternative pathway analysis approaches that aim to reduce the EFM solution space. Despite advances in EFM computation, our review concludes that continued scaling of EFM computation is necessary to apply EFM to genome-scale models. Further, our review concludes that pathway analysis methods that target specific pathway properties can provide powerful alternatives to EFM analysis.

Inhibition of C298S mutant of human aldose reductase for antidiabetic applications: Evidence from in silico elementary mode analysis of biological network model

Human aldose reductase (hAR) is the key enzyme in sorbitol pathway of glucose utilization and is implicated in the etiology of secondary complications of diabetes, such as, cardiovascular complications, neuropathy, nephropathy, retinopathy, and cataract genesis. It reduces glucose to sorbitol in the presence of NADPH and the major cause of diabetes complications could be the change in the osmotic pressure due to the accumulation of sorbitol. An activated form of hAR (activated hAR or ahAR) poses a potential obstacle in the development of diabetes drugs as hAR-inhibitors are ineffective against ahAR. The therapeutic efficacy of such drugs is compromised when a large fraction of the enzyme (hAR) undergoes conversion to the activated ahAR form as has been observed in the diabetic tissues. In the present study, attempts have been made to employ systems biology strategies to identify the elementary nodes of human polyol metabolic pathway, responsible for normal metabolic states, followed by the identification of natural potent inhibitors of the activated form of hAR represented by the mutant C298S for possible antidiabetic applications. Quantum Mechanical Molecular Mechanical docking strategy was used to determine the probable inhibitors of ahAR. Rosmarinic acid was found as the most potent natural ahAR inhibitor and warrants for experimental validation in the near future.

Mathematical modelling of clostridial acetone-butanol-ethanol fermentation

Clostridial acetone-butanol-ethanol (ABE) fermentation features a remarkable shift in the cellular metabolic activity from acid formation, acidogenesis, to the production of industrial-relevant solvents, solventogensis. In recent decades, mathematical models have been employed to elucidate the complex interlinked regulation and conditions that determine these two distinct metabolic states and govern the transition between them. In this review, we discuss these models with a focus on the mechanisms controlling intra- and extracellular changes between acidogenesis and solventogenesis. In particular, we critically evaluate underlying model assumptions and predictions in the light of current experimental knowledge. Towards this end, we briefly introduce key ideas and assumptions applied in the discussed modelling approaches, but waive a comprehensive mathematical presentation. We distinguish between structural and dynamical models, which will be discussed in their chronological order to illustrate how new biological information facilitates the ‘evolution’ of mathematical models. Mathematical models and their analysis have significantly contributed to our knowledge of ABE fermentation and the underlying regulatory network which spans all levels of biological organization. However, the ties between the different levels of cellular regulation are not well understood. Furthermore, contradictory experimental and theoretical results challenge our current notion of ABE metabolic network structure. Thus, clostridial ABE fermentation still poses theoretical as well as experimental challenges which are best approached in close collaboration between modellers and experimentalists.

Interplay between constraints, objectives, and optimality for genome-scale stoichiometric models

High-throughput data generation and genome-scale stoichiometric models have greatly facilitated the comprehensive study of metabolic networks. The computation of all feasible metabolic routes with these models, given stoichiometric, thermodynamic, and steady-state constraints, provides important insights into the metabolic capacities of a cell. How the feasible metabolic routes emerge from the interplay between flux constraints, optimality objectives, and the entire metabolic network of a cell is, however, only partially understood. We show how optimal metabolic routes, resulting from flux balance analysis computations, arise out of elementary flux modes, constraints, and optimization objectives. We illustrate our findings with a genome-scale stoichiometric model of Escherichia coli metabolism. In the case of one flux constraint, all feasible optimal flux routes can be derived from elementary flux modes alone. We found up to 120 million of such optimal elementary flux modes. We introduce a new computational method to compute the corner points of the optimal solution space fast and efficiently. Optimal flux routes no longer depend exclusively on elementary flux modes when we impose additional constraints; new optimal metabolic routes arise out of combinations of elementary flux modes. The solution space of feasible metabolic routes shrinks enormously when additional objectives---e.g. those related to pathway expression costs or pathway length---are introduced. In many cases, only a single metabolic route remains that is both feasible and optimal. This paper contributes to reaching a complete topological understanding of the metabolic capacity of organisms in terms of metabolic flux routes, one that is most natural to biochemists and biotechnologists studying and engineering metabolism.

A depth-first search algorithm to compute elementary flux modes by linear programming

Background

The decomposition of complex metabolic networks into elementary flux modes (EFMs) provides a useful framework for exploring reaction interactions systematically. Generating a complete set of EFMs for large-scale models, however, is near impossible. Even for moderately-sized models (<400 reactions), existing approaches based on the Double Description method must iterate through a large number of combinatorial candidates, thus imposing an immense processor and memory demand.

Results

Based on an alternative elementarity test, we developed a depth-first search algorithm using linear programming (LP) to enumerate EFMs in an exhaustive fashion. Constraints can be introduced to directly generate a subset of EFMs satisfying the set of constraints. The depth-first search algorithm has a constant memory overhead. Using flux constraints, a large LP problem can be massively divided and parallelized into independent sub-jobs for deployment into computing clusters. Since the sub-jobs do not overlap, the approach scales to utilize all available computing nodes with minimal coordination overhead or memory limitations.

Conclusions

The speed of the algorithm was comparable to efmtool, a mainstream Double Description method, when enumerating all EFMs; the attrition power gained from performing flux feasibility tests offsets the increased computational demand of running an LP solver. Unlike the Double Description method, the algorithm enables accelerated enumeration of all EFMs satisfying a set of constraints.

Complete enumeration of elementary flux modes through scalable demand-based subnetwork definition

MOTIVATION

Elementary flux mode analysis (EFMA) decomposes complex metabolic network models into tractable biochemical pathways, which have been used for rational design and analysis of metabolic and regulatory networks. However, application of EFMA has often been limited to targeted or simplified metabolic network representations due to computational demands of the method.

RESULTS

Division of biological networks into subnetworks enables the complete enumeration of elementary flux modes (EFMs) for metabolic models of a broad range of complexities, including genome-scale. Here, subnetworks are defined using serial dichotomous suppression and enforcement of flux through model reactions. Rules for selecting appropriate reactions to generate subnetworks are proposed and tested; three test cases, including both prokaryotic and eukaryotic network models, verify the efficacy of these rules and demonstrate completeness and reproducibility of EFM enumeration. Division of models into subnetworks is demand-based and automated; computationally intractable subnetworks are further divided until the entire solution space is enumerated. To demonstrate the strategy's scalability, the splitting algorithm was implemented using an EFMA software package (EFMTool) and Windows PowerShell on a 50 node Microsoft high performance computing cluster. Enumeration of the EFMs in a genome-scale metabolic model of a diatom, Phaeodactylum tricornutum, identified ∼2 billion EFMs. The output represents an order of magnitude increase in EFMs computed compared with other published algorithms and demonstrates a scalable framework for EFMA of most systems.

Elementary flux modes in a nutshell: properties, calculation and applications

Elementary flux mode (EFM) analysis allows the unbiased decomposition of a metabolic network into minimal functional units, making it a powerful tool for metabolic engineering. While the use of EFM analysis (EFMA) is still limited by the size of the models it can handle, EFMA has been successfully applied to solve real-world metabolic engineering problems. Here we provide a user-oriented introduction to EFMA, provide examples of recent applications, analyze current research strategies to overcome the computational restrictions and give an overview over current approaches, which aim to identify and calculate only biologically relevant EFMs.

Random sampling of elementary flux modes in large-scale metabolic networks

MOTIVATION

The description of a metabolic network in terms of elementary (flux) modes (EMs) provides an important framework for metabolic pathway analysis. However, their application to large networks has been hampered by the combinatorial explosion in the number of modes. In this work, we develop a method for generating random samples of EMs without computing the whole set.

RESULTS

Our algorithm is an adaptation of the canonical basis approach, where we add an additional filtering step which, at each iteration, selects a random subset of the new combinations of modes. In order to obtain an unbiased sample, all candidates are assigned the same probability of getting selected. This approach avoids the exponential growth of the number of modes during computation, thus generating a random sample of the complete set of EMs within reasonable time. We generated samples of different sizes for a metabolic network of Escherichia coli, and observed that they preserve several properties of the full EM set. It is also shown that EM sampling can be used for rational strain design. A well distributed sample, that is representative of the complete set of EMs, should be suitable to most EM-based methods for analysis and optimization of metabolic networks.

AVAILABILITY

Source code for a cross-platform implementation in Python is freely available at http://code.google.com/p/emsampler.

CONTACT

dmachado@deb.uminho.pt

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Analysis of metabolic subnetworks by flux cone projection

Background

Analysis of elementary modes (EMs) is proven to be a powerful constraint-based method in the study of metabolic networks. However, enumeration of EMs is a hard computational task. Additionally, due to their large number, EMs cannot be simply used as an input for subsequent analysis. One possibility is to limit the analysis to a subset of interesting reactions. However, analysing an isolated subnetwork can result in finding incorrect EMs which are not part of any steady-state flux distribution of the original network. The ideal set to describe the reaction activity in a subnetwork would be the set of all EMs projected to the reactions of interest. Recently, the concept of "elementary flux patterns" (EFPs) has been proposed. Each EFP is a subset of the support (i.e., non-zero elements) of at least one EM.

Results

We introduce the concept of ProCEMs (Projected Cone Elementary Modes). The ProCEM set can be computed by projecting the flux cone onto a lower-dimensional subspace and enumerating the extreme rays of the projected cone. In contrast to EFPs, ProCEMs are not merely a set of reactions, but projected EMs. We additionally prove that the set of EFPs is included in the set of ProCEM supports. Finally, ProCEMs and EFPs are compared for studying substructures of biological networks.

Conclusions

We introduce the concept of ProCEMs and recommend its use for the analysis of substructures of metabolic networks for which the set of EMs cannot be computed.

Whole cell biosynthesis of a functional oligosaccharide, 2'-fucosyllactose, using engineered Escherichia coli

Background

2'-Fucosyllactose (2-FL) is a functional oligosaccharide present in human milk which protects against the infection of enteric pathogens. Because 2-FL can be synthesized through the enzymatic fucosylation of lactose with guanosine 5′-diphosphate (GDP)-l-fucose by α-1,2-fucosyltransferase (FucT2), an 2-FL producing Escherichia coli can be constructed through overexpressing genes coding for endogenous GDP- l-fucose biosynthetic enzymes and heterologous fucosyltransferase.

Results

The gene for FucT2 from Helicobacter pylori was introduced to the GDP- l-fucose producing recombinant E. coli BL21 star(DE3) strain. However, only small amount of 2-FL was produced in a batch fermentation because the E. coli BL21star(DE3) strain assimilated lactose instead of converting to 2-FL. As an alternative host, the E. coli JM109(DE3) strain which is incapable of assimilating lactose was chosen as a 2-FL producer. Whole cell biosynthesis of 2-FL from lactose was investigated in a series of batch fermentations using various concentrations of lactose. The results of batch fermentations showed that lactose was slowly assimilated by the engineered E. coli JM109(DE3) strain and 2-FL was synthesized without supplementation of another auxiliary sugar for cell growth. A maximum 2-FL concentration of 1.23 g/l was obtained from a batch fermentation with 14.5 g/l lactose. The experimentally obtained yield (g 2-FL/g lactose) corresponded to 20% of the theoretical maximum yield estimated by the elementary flux mode (EFM) analysis.

Conclusions

The experimental 2-FL yield in this study corresponded to about 20% of the theoretical maximum yield, which suggests further modifications via metabolic engineering of a host strain or optimization of fermentation processes might be carried out for improving 2-FL yield. Improvement of microbial production of 2-FL from lactose by engineered E. coli would increase the feasibility of utilizing 2-FL as a prebiotic in various foods.

System-level insights into yeast metabolism by thermodynamic analysis of elementary flux modes

One of the most obvious phenotypes of a cell is its metabolic activity, which is defined by the fluxes in the metabolic network. Although experimental methods to determine intracellular fluxes are well established, only a limited number of fluxes can be resolved. Especially in eukaryotes such as yeast, compartmentalization and the existence of many parallel routes render exact flux analysis impossible using current methods. To gain more insight into the metabolic operation of S. cerevisiae we developed a new computational approach where we characterize the flux solution space by determining elementary flux modes (EFMs) that are subsequently classified as thermodynamically feasible or infeasible on the basis of experimental metabolome data. This allows us to provably rule out the contribution of certain EFMs to the in vivo flux distribution. From the 71 million EFMs in a medium size metabolic network of S. cerevisiae, we classified 54% as thermodynamically feasible. By comparing the thermodynamically feasible and infeasible EFMs, we could identify reaction combinations that span the cytosol and mitochondrion and, as a system, cannot operate under the investigated glucose batch conditions. Besides conclusions on single reactions, we found that thermodynamic constraints prevent the import of redox cofactor equivalents into the mitochondrion due to limits on compartmental cofactor concentrations. Our novel approach of incorporating quantitative metabolite concentrations into the analysis of the space of all stoichiometrically feasible flux distributions allows generating new insights into the system-level operation of the intracellular fluxes without making assumptions on metabolic objectives of the cell.

Fluxes in metabolic pathways are a highly informative aspect of an organism's phenotype. The experimental determination of such fluxes is well established and has proven very useful. To address some of the limitations of experimental flux analysis, such as when the cell is divided in multiple compartments, stoichiometric modeling provides a valuable addition. The approach that we take is based on stoichiometric modeling where we consider the thermodynamic feasibility of many different possible routes through the metabolic network of Saccharomyces cerevisiae using experimentally determined metabolite concentrations. We show that next to conclusions on single biochemical reactions in the metabolic network, we obtain system-level insights on thermodynamically infeasible flux patterns. We found that the compartmental concentrations of and NADH are the causes for the system-level infeasibilities. With the current advances in quantitative metabolomics and biochemical thermodynamics, we envision that the presented method will help gaining more insight into complex metabolic systems.

Kinetic modelling of plant metabolic pathways

This paper provides a review of kinetic modelling of plant metabolic pathways as a tool for analysing their control and regulation. An overview of different modelling strategies is presented, starting with those approaches that only require a knowledge of the network stoichiometry; these are referred to as structural. Flux-balance analysis, metabolic flux analysis using isotope labelling, and elementary mode analysis are briefly mentioned as three representative examples. The main focus of this paper, however, is a discussion of kinetic modelling, which requires, in addition to the stoichiometry, a knowledge of the kinetic properties of the constituent pathway enzymes. The different types of kinetic modelling analysis, namely time-course simulation, steady-state analysis, and metabolic control analysis, are explained in some detail. An overview is presented of strategies for obtaining model parameters, as well as software tools available for simulation of such models. The kinetic modelling approach is exemplified with discussion of three models from the general plant physiology literature. With the aid of kinetic modelling it is possible to perform a control analysis of a plant metabolic system, to identify potential targets for biotechnological manipulation, as well as to ascertain the regulatory importance of different enzymes (including isoforms of the same enzyme) in a pathway. Finally, a framework is presented for extending metabolic models to the whole-plant scale by linking biochemical reactions with diffusion and advective flow through the phloem. Future challenges include explicit modelling of subcellular compartments, as well as the integration of kinetic models on the different levels of the cellular and organizational hierarchy.

Enumerating metabolic pathways for the production of heterologous target chemicals in chassis organisms

Background

We consider the possibility of engineering metabolic pathways in a chassis organism in order to synthesize novel target compounds that are heterologous to the chassis. For this purpose, we model metabolic networks through hypergraphs where reactions are represented by hyperarcs. Each hyperarc represents an enzyme-catalyzed reaction that transforms set of substrates compounds into product compounds. We follow a retrosynthetic approach in order to search in the metabolic space (hypergraphs) for pathways (hyperpaths) linking the target compounds to a source set of compounds.

Results

To select the best pathways to engineer, we have developed an objective function that computes the cost of inserting a heterologous pathway in a given chassis organism. In order to find minimum-cost pathways, we propose in this paper two methods based on steady state analysis and network topology that are to the best of our knowledge, the first to enumerate all possible heterologous pathways linking a target compounds to a source set of compounds. In the context of metabolic engineering, the source set is composed of all naturally produced chassis compounds (endogenuous chassis metabolites) and the target set can be any compound of the chemical space. We also provide an algorithm for identifying precursors which can be supplied to the growth media in order to increase the number of ways to synthesize specific target compounds.

Conclusions

We find the topological approach to be faster by several orders of magnitude than the steady state approach. Yet both methods are generally scalable in time with the number of pathways in the metabolic network. Therefore this work provides a powerful tool for pathway enumeration with direct application to biosynthetic pathway design.

A new metabolomics analysis technique: steady-state metabolic network dynamics analysis

With the recent advances in experimental technologies, such as gas chromatography and mass spectrometry, the number of metabolites that can be measured in biofluids of individuals has markedly increased. Given a set of such measurements, a very common task encountered by biologists is to identify the metabolic mechanisms that lead to changes in the concentrations of given metabolites and interpret the metabolic consequences of the observed changes in terms of physiological problems, nutritional deficiencies, or diseases. In this paper, we present the steady-state metabolic network dynamics analysis (SMDA) approach in detail, together with its application in a cystic fibrosis study. We also present a computational performance evaluation of the SMDA tool against a mammalian metabolic network database. The query output space of the SMDA tool is exponentially large in the number of reactions of the network. However, (i) larger numbers of observations exponentially reduce the output size, and (ii) exploratory search and browsing of the query output space is provided to allow users to search for what they are looking for.

Systems analysis of microbial adaptations to simultaneous stresses

Microbes live in multi-factorial environments and have evolved under a variety of concurrent stresses including resource scarcity. Their metabolic organization is a reflection of their evolutionary histories and, in spite of decades of research, there is still a need for improved theoretical tools to explain fundamental aspects of microbial physiology. Using ecological and economic concepts, this chapter explores a resource-ratio based theory to elucidate microbial strategies for extracting and channeling mass and energy. The theory assumes cellular fitness is maximized by allocating scarce resources in appropriate proportions to multiple stress responses. Presented case studies deconstruct metabolic networks into a complete set of minimal biochemical pathways known as elementary flux modes. An economic analysis of the elementary flux modes tabulates enzyme atomic synthesis requirements from amino acid sequences and pathway operating costs from catabolic efficiencies, permitting characterization of inherent tradeoffs between resource investment and phenotype. A set of elementary flux modes with competitive tradeoffs properties can be mathematically projected onto experimental fluxomics datasets to decompose measured phenotypes into metabolic adaptations, interpreted as cellular responses proportional to the experienced culturing stresses. The resource-ratio based method describes the experimental phenotypes with greater accuracy than other contemporary approaches and further analysis suggests the results are both statistically and biologically significant. The insight into metabolic network design principles including tradeoffs associated with concurrent stress adaptation provides a foundation for interpreting physiology as well as for rational control and engineering of medically, environmentally, and industrially relevant microbes.

Decomposing flux distributions into elementary flux modes in genome-scale metabolic networks

MOTIVATION

Elementary flux mode (EFM) is a fundamental concept as well as a useful tool in metabolic pathway analysis. One important role of EFMs is that every flux distribution can be decomposed into a set of EFMs and a number of methods to study flux distributions originated from it. Yet finding such decompositions requires the complete set of EFMs, which is intractable in genome-scale metabolic networks due to combinatorial explosion.

RESULTS

In this article, we proposed an algorithm to decompose flux distributions into EFMs in genome-scale networks. It is an iterative scheme of a mixed integer linear program. Unlike previous optimization models to find pathways, any feasible solutions can become EFMs in our algorithm. This advantage enables the algorithm to approximate the EFM of largest contribution to an objective reaction in a flux distribution. Our algorithm is able to find EFMs of flux distributions with complex structures, closer to the realistic case in which a cell is subject to various constraints. A case of Escherichia coli growth in the Lysogeny broth (LB) medium containing various carbon sources was studied. Essential metabolites and their syntheses were located. Information on the contribution of each carbon source not obvious from the apparent flux distribution was also revealed. Our work further confirms the utility of finding EFMs by optimization models in genome-scale metabolic networks.

CONTACT

joshua.chan@connect.polyu.hk

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Cell functional enviromics: unravelling the function of environmental factors

Background

While functional genomics, focused on gene functions and gene-gene interactions, has become a very active field of research in molecular biology, equivalent methodologies embracing the environment and gene-environment interactions are relatively less developed. Understanding the function of environmental factors is, however, of paramount importance given the complex, interactive nature of environmental and genetic factors across multiple time scales.

Results

Here, we propose a systems biology framework, where the function of environmental factors is set at its core. We set forth a "reverse" functional analysis approach, whereby cellular functions are reconstructed from the analysis of dynamic envirome data. Our results show these data sets can be mapped to less than 20 core cellular functions in a typical mammalian cell culture, while explaining over 90% of flux data variance. A functional enviromics map can be created, which provides a template for manipulating the environmental factors to induce a desired phenotypic trait.

Conclusion

Our results support the feasibility of cellular function reconstruction guided by the analysis and manipulation of dynamic envirome data.

Parallelization of Nullspace Algorithm for the computation of metabolic pathways

Elementary mode analysis is a useful metabolic pathway analysis tool in understanding and analyzing cellular metabolism, since elementary modes can represent metabolic pathways with unique and minimal sets of enzyme-catalyzed reactions of a metabolic network under steady state conditions. However, computation of the elementary modes of a genome- scale metabolic network with 100-1000 reactions is very expensive and sometimes not feasible with the commonly used serial Nullspace Algorithm. In this work, we develop a distributed memory parallelization of the Nullspace Algorithm to handle efficiently the computation of the elementary modes of a large metabolic network. We give an implementation in C++ language with the support of MPI library functions for the parallel communication. Our proposed algorithm is accompanied with an analysis of the complexity and identification of major bottlenecks during computation of all possible pathways of a large metabolic network. The algorithm includes methods to achieve load balancing among the compute-nodes and specific communication patterns to reduce the communication overhead and improve efficiency.

Exploring metabolic pathways in genome-scale networks via generating flux modes

MOTIVATION

The reconstruction of metabolic networks at the genome scale has allowed the analysis of metabolic pathways at an unprecedented level of complexity. Elementary flux modes (EFMs) are an appropriate concept for such analysis. However, their number grows in a combinatorial fashion as the size of the metabolic network increases, which renders the application of EFMs approach to large metabolic networks difficult. Novel methods are expected to deal with such complexity.

RESULTS

In this article, we present a novel optimization-based method for determining a minimal generating set of EFMs, i.e. a convex basis. We show that a subset of elements of this convex basis can be effectively computed even in large metabolic networks. Our method was applied to examine the structure of pathways producing lysine in Escherichia coli. We obtained a more varied and informative set of pathways in comparison with existing methods. In addition, an alternative pathway to produce lysine was identified using a detour via propionyl-CoA, which shows the predictive power of our novel approach.

AVAILABILITY

The source code in C++ is available upon request.

On algebraic properties of extreme pathways in metabolic networks

We give a concise development of some of the major algebraic properties of extreme pathways (pathways that cannot be the result of combining other pathways) of metabolic networks, contrasting them to those of elementary flux modes (pathways involving a minimal set of reactions). In particular, we show that an extreme pathway can be recognized by a rank test as simple as the existing rank test for elementary flux modes, without computing all the modes. We make the observation that, unlike elementary flux modes, the property of being an extreme pathway depends on the presence or absence of reactions beyond those involved in the pathway itself. Hence, the property of being an extreme pathway is not a local property. As a consequence, we find that the set of all elementary flux modes for a network includes all the elementary flux modes for all its subnetworks, but that this property does not hold for the set of all extreme pathways.

Which metabolic pathways generate and characterize the flux space? A comparison among elementary modes, extreme pathways and minimal generators

Important efforts are being done to systematically identify the relevant pathways in a metabolic network. Unsurprisingly, there is not a unique set of network-based pathways to be tagged as relevant, and at least four related concepts have been proposed: extreme currents, elementary modes, extreme pathways, and minimal generators. Basically, there are two properties that these sets of pathways can hold: they can generate the flux space--if every feasible flux distribution can be represented as a nonnegative combination of flux through them--or they can comprise all the nondecomposable pathways in the network. The four concepts fulfill the first property, but only the elementary modes fulfill the second one. This subtle difference has been a source of errors and misunderstandings. This paper attempts to clarify the intricate relationship between the network-based pathways performing a comparison among them.

ON/OFF and beyond--a boolean model of apoptosis

Apoptosis is regulated by several signaling pathways which are extensively linked by crosstalks. Boolean or logical modeling has become a promising approach to capture the qualitative behavior of such complex networks. Here we built a large-scale literature-based Boolean model of the central intrinsic and extrinsic apoptosis pathways as well as pathways connected with them. The model responds to several external stimuli such as Fas ligand, TNF-α, UV-B irradiation, interleukin-1β and insulin. Timescales and multi-value node logic were used and turned out to be indispensable to reproduce the behavior of the apoptotic network. The coherence of the model was experimentally validated. Thereby an UV-B dose-effect is shown for the first time in mouse hepatocytes. Analysis of the model revealed a tight regulation emerging from high connectivity and spanning crosstalks and a particular importance of feedback loops. An unexpected feedback from Smac release to RIP could further increase complex II formation. The introduced Boolean model provides a comprehensive and coherent description of the apoptosis network behavior. It gives new insights into the complex interplay of pro- and antiapoptotic factors and can be easily expanded to other signaling pathways.

Apoptosis is one of the most investigated topics in the life sciences, especially as this kind of programmed cell death has been linked to several diseases. The strong desire to understand the function and regulation of apoptosis is unfortunately confronted with its complexity and its high degree of cross linking within the cell. Therefore we apply the so-called logical or Boolean mathematical modeling approach to comprehensively describe the numerous interactions in the apoptotic network. Classical Boolean modeling assumes that a certain cellular signal is either present (on) or absent (off). We use extensions of classical Boolean models, namely timescale constants and multi-value nodes, which allow the model to emulate typical apoptotic features. The mathematical model describes for the first time the numerous relevant interactions and signals that control apoptosis in a single and coherent framework. The logical model of apoptosis provides valuable information about the topology of the network including feedback loops and crosstalk effects. Proper investigation of the mutual interactions between species points towards hubs in the network with outstanding relevance. These species are of special interest concerning experimental intervention as well as drug target search. The model we present here is easy to use and freely available.

In silico approaches to study mass and energy flows in microbial consortia: a syntrophic case study

BACKGROUND

Three methods were developed for the application of stoichiometry-based network analysis approaches including elementary mode analysis to the study of mass and energy flows in microbial communities. Each has distinct advantages and disadvantages suitable for analyzing systems with different degrees of complexity and a priori knowledge. These approaches were tested and compared using data from the thermophilic, phototrophic mat communities from Octopus and Mushroom Springs in Yellowstone National Park (USA). The models were based on three distinct microbial guilds: oxygenic phototrophs, filamentous anoxygenic phototrophs, and sulfate-reducing bacteria. Two phases, day and night, were modeled to account for differences in the sources of mass and energy and the routes available for their exchange.

RESULTS

The in silico models were used to explore fundamental questions in ecology including the prediction of and explanation for measured relative abundances of primary producers in the mat, theoretical tradeoffs between overall productivity and the generation of toxic by-products, and the relative robustness of various guild interactions.

CONCLUSION

The three modeling approaches represent a flexible toolbox for creating cellular metabolic networks to study microbial communities on scales ranging from cells to ecosystems. A comparison of the three methods highlights considerations for selecting the one most appropriate for a given microbial system. For instance, communities represented only by metagenomic data can be modeled using the pooled method which analyzes a community's total metabolic potential without attempting to partition enzymes to different organisms. Systems with extensive a priori information on microbial guilds can be represented using the compartmentalized technique, employing distinct control volumes to separate guild-appropriate enzymes and metabolites. If the complexity of a compartmentalized network creates an unacceptable computational burden, the nested analysis approach permits greater scalability at the cost of more user intervention through multiple rounds of pathway analysis.

Inferring branching pathways in genome-scale metabolic networks

Background

A central problem in computational metabolic modelling is how to find biochemically plausible pathways between metabolites in a metabolic network. Two general, complementary frameworks have been utilized to find metabolic pathways: constraint-based modelling and graph-theoretical path finding approaches. In constraint-based modelling, one aims to find pathways where metabolites are balanced in a pseudo steady-state. Constraint-based methods, such as elementary flux mode analysis, have typically a high computational cost stemming from a large number of steady-state pathways in a typical metabolic network. On the other hand, graph-theoretical approaches avoid the computational complexity of constraint-based methods by solving a simpler problem of finding shortest paths. However, while scaling well with network size, graph-theoretic methods generally tend to return more false positive pathways than constraint-based methods.

Results

In this paper, we introduce a computational method, ReTrace, for finding biochemically relevant, branching metabolic pathways in an atom-level representation of metabolic networks. The method finds compact pathways which transfer a high fraction of atoms from source to target metabolites by considering combinations of linear shortest paths. In contrast to current steady-state pathway analysis methods, our method scales up well and is able to operate on genome-scale models. Further, we show that the pathways produced are biochemically meaningful by an example involving the biosynthesis of inosine 5'-monophosphate (IMP). In particular, the method is able to avoid typical problems associated with graph-theoretic approaches such as the need to define side metabolites or pathways not carrying any net carbon flux appearing in results. Finally, we discuss an application involving reconstruction of amino acid pathways of a recently sequenced organism demonstrating how measurement data can be easily incorporated into ReTrace analysis. ReTrace is licensed under GPL and is freely available for academic use at http://www.cs.helsinki.fi/group/sysfys/software/retrace/.

Conclusion

ReTrace is a useful method in metabolic path finding tasks, combining some of the best aspects in constraint-based and graph-theoretic methods. It finds use in a multitude of tasks ranging from metabolic engineering to metabolic reconstruction of recently sequenced organisms.

Computing the shortest elementary flux modes in genome-scale metabolic networks

MOTIVATION

Elementary flux modes (EFMs) represent a key concept to analyze metabolic networks from a pathway-oriented perspective. In spite of considerable work in this field, the computation of the full set of elementary flux modes in large-scale metabolic networks still constitutes a challenging issue due to its underlying combinatorial complexity.

RESULTS

In this article, we illustrate that the full set of EFMs can be enumerated in increasing order of number of reactions via integer linear programming. In this light, we present a novel procedure to efficiently determine the K-shortest EFMs in large-scale metabolic networks. Our method was applied to find the K-shortest EFMs that produce lysine in the genome-scale metabolic networks of Escherichia coli and Corynebacterium glutamicum. A detailed analysis of the biological significance of the K-shortest EFMs was conducted, finding that glucose catabolism, ammonium assimilation, lysine anabolism and cofactor balancing were correctly predicted. The work presented here represents an important step forward in the analysis and computation of EFMs for large-scale metabolic networks, where traditional methods fail for networks of even moderate size.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Can the whole be less than the sum of its parts? Pathway analysis in genome-scale metabolic networks using elementary flux patterns

Elementary modes represent a valuable concept in the analysis of metabolic reaction networks. However, they can only be computed in medium-size systems, preventing application to genome-scale metabolic models. In consequence, the analysis is usually constrained to a specific part of the known metabolism, and the remaining system is modeled using abstractions like exchange fluxes and external species. As we show by the analysis of a model of the central metabolism of Escherichia coli that has been previously analyzed using elementary modes, the choice of these abstractions heavily impacts the pathways that are detected, and the results are biased by the knowledge of the metabolic capabilities of the network by the user. In order to circumvent these problems, we introduce the concept of elementary flux patterns, which explicitly takes into account possible steady-state fluxes through a genome-scale metabolic network when analyzing pathways through a subsystem. By being similar to elementary mode analysis, our concept now allows for the application of many elementary-mode-based tools to genome-scale metabolic networks. We present an algorithm to compute elementary flux patterns and analyze a model of the tricarboxylic acid cycle and adjacent reactions in E. coli. Thus, we detect several pathways that can be used as alternative routes to some central metabolic pathways. Finally, we give an outlook on further applications like the computation of minimal media, the development of knockout strategies, and the analysis of combined genome-scale networks.

Computing paths and cycles in biological interaction graphs

BACKGROUND

Interaction graphs (signed directed graphs) provide an important qualitative modeling approach for Systems Biology. They enable the analysis of causal relationships in cellular networks and can even be useful for predicting qualitative aspects of systems dynamics. Fundamental issues in the analysis of interaction graphs are the enumeration of paths and cycles (feedback loops) and the calculation of shortest positive/negative paths. These computational problems have been discussed only to a minor extent in the context of Systems Biology and in particular the shortest signed paths problem requires algorithmic developments.

RESULTS

We first review algorithms for the enumeration of paths and cycles and show that these algorithms are superior to a recently proposed enumeration approach based on elementary-modes computation. The main part of this work deals with the computation of shortest positive/negative paths, an NP-complete problem for which only very few algorithms are described in the literature. We propose extensions and several new algorithm variants for computing either exact results or approximations. Benchmarks with various concrete biological networks show that exact results can sometimes be obtained in networks with several hundred nodes. A class of even larger graphs can still be treated exactly by a new algorithm combining exhaustive and simple search strategies. For graphs, where the computation of exact solutions becomes time-consuming or infeasible, we devised an approximative algorithm with polynomial complexity. Strikingly, in realistic networks (where a comparison with exact results was possible) this algorithm delivered results that are very close or equal to the exact values. This phenomenon can probably be attributed to the particular topology of cellular signaling and regulatory networks which contain a relatively low number of negative feedback loops.

CONCLUSION

The calculation of shortest positive/negative paths and cycles in interaction graphs is an important method for network analysis in Systems Biology. This contribution draws the attention of the community to this important computational problem and provides a number of new algorithms, partially specifically tailored for biological interaction graphs. All algorithms have been implemented in the CellNetAnalyzer framework which can be downloaded for academic use at http://www.mpi-magdeburg.mpg.de/projects/cna/cna.html.

Elementary mode analysis: a useful metabolic pathway analysis tool for characterizing cellular metabolism

Elementary mode analysis is a useful metabolic pathway analysis tool to identify the structure of a metabolic network that links the cellular phenotype to the corresponding genotype. The analysis can decompose the intricate metabolic network comprised of highly interconnected reactions into uniquely organized pathways. These pathways consisting of a minimal set of enzymes that can support steady state operation of cellular metabolism represent independent cellular physiological states. Such pathway definition provides a rigorous basis to systematically characterize cellular phenotypes, metabolic network regulation, robustness, and fragility that facilitate understanding of cell physiology and implementation of metabolic engineering strategies. This mini-review aims to overview the development and application of elementary mode analysis as a metabolic pathway analysis tool in studying cell physiology and as a basis of metabolic engineering.

Robust simplifications of multiscale biochemical networks

Background

Cellular processes such as metabolism, decision making in development and differentiation, signalling, etc., can be modeled as large networks of biochemical reactions. In order to understand the functioning of these systems, there is a strong need for general model reduction techniques allowing to simplify models without loosing their main properties. In systems biology we also need to compare models or to couple them as parts of larger models. In these situations reduction to a common level of complexity is needed.

Results

We propose a systematic treatment of model reduction of multiscale biochemical networks. First, we consider linear kinetic models, which appear as "pseudo-monomolecular" subsystems of multiscale nonlinear reaction networks. For such linear models, we propose a reduction algorithm which is based on a generalized theory of the limiting step that we have developed in [1]. Second, for non-linear systems we develop an algorithm based on dominant solutions of quasi-stationarity equations. For oscillating systems, quasi-stationarity and averaging are combined to eliminate time scales much faster and much slower than the period of the oscillations. In all cases, we obtain robust simplifications and also identify the critical parameters of the model. The methods are demonstrated for simple examples and for a more complex model of NF-κB pathway.

Conclusion

Our approach allows critical parameter identification and produces hierarchies of models. Hierarchical modeling is important in "middle-out" approaches when there is need to zoom in and out several levels of complexity. Critical parameter identification is an important issue in systems biology with potential applications to biological control and therapeutics. Our approach also deals naturally with the presence of multiple time scales, which is a general property of systems biology models.

Drug targets for tumorigenesis: insights from structural analysis of EGFR signaling network

Deciphering the complex network structure is crucial in drug target identification. This study presents a framework incorporating graph theoretic and network decomposition methods to analyze system-level properties of the comprehensive map of the epidermal growth factor receptor (EGFR) signaling, which is a good candidate model system to study the general mechanisms of signal transduction. The graph theoretic analysis of the EGFR network indicates that it has small-world characteristics with scale-free topology. The employment of network decomposition analysis enlightened the system-level properties, such as network cross-talk, specific molecules in each pathway and participation of molecules in the network. Participating in a significant fraction of the fundamental paths connecting the ligands to the phenotypes, cofactor GTP and complex Gbeta/Ggamma were identified as "housekeeping" molecules, through which all pathways of EGFR network are cross-talking. c-Src-Shc complex is identified as important due to its role in all fundamental paths through tumorigenesis and being specific to this phenotype. Inhibitors of this complex may be good anti-cancer agents having very little or no effect on other phenotypes.

Exhaustive identification of steady state cycles in large stoichiometric networks

BACKGROUND

Identifying cyclic pathways in chemical reaction networks is important, because such cycles may indicate in silico violation of energy conservation, or the existence of feedback in vivo. Unfortunately, our ability to identify cycles in stoichiometric networks, such as signal transduction and genome-scale metabolic networks, has been hampered by the computational complexity of the methods currently used.

RESULTS

We describe a new algorithm for the identification of cycles in stoichiometric networks, and we compare its performance to two others by exhaustively identifying the cycles contained in the genome-scale metabolic networks of H. pylori, M. barkeri, E. coli, and S. cerevisiae. Our algorithm can substantially decrease both the execution time and maximum memory usage in comparison to the two previous algorithms.

CONCLUSION

The algorithm we describe improves our ability to study large, real-world, biochemical reaction networks, although additional methodological improvements are desirable.

Identification of flux regulation coefficients from elementary flux modes: A systems biology tool for analysis of metabolic networks

Within a metabolic network, the elementary flux modes enables a unique description of different operations of the network. Thus, the metabolic fluxes can be specified as convex combinations of the elementary flux modes. Here, we describe an approach to identify the set of elementary flux modes that operates in a given metabolic network through the use of measurements of macroscopic fluxes, that is, fluxes in and out of the cell. Besides enabling estimation of the metabolic fluxes, the parameters of the linear combinations of the elementary flux modes provide valuable physiological information; we call these parameters flux regulation coefficients (FRCs). These coefficients indicate which enzyme subsets are important at different growth conditions. We demonstrate how FRCs can be used to map the operation of the metabolic network of the yeast Saccharomyces sp. under different growth conditions.

Structural and functional analysis of cellular networks with CellNetAnalyzer

Background

Mathematical modelling of cellular networks is an integral part of Systems Biology and requires appropriate software tools. An important class of methods in Systems Biology deals with structural or topological (parameter-free) analysis of cellular networks. So far, software tools providing such methods for both mass-flow (metabolic) as well as signal-flow (signalling and regulatory) networks are lacking.

Results

Herein we introduce CellNetAnalyzer, a toolbox for MATLAB facilitating, in an interactive and visual manner, a comprehensive structural analysis of metabolic, signalling and regulatory networks. The particular strengths of CellNetAnalyzer are methods for functional network analysis, i.e. for characterising functional states, for detecting functional dependencies, for identifying intervention strategies, or for giving qualitative predictions on the effects of perturbations. CellNetAnalyzer extends its predecessor FluxAnalyzer (originally developed for metabolic network and pathway analysis) by a new modelling framework for examining signal-flow networks. Two of the novel methods implemented in CellNetAnalyzer are discussed in more detail regarding algorithmic issues and applications: the computation and analysis (i) of shortest positive and shortest negative paths and circuits in interaction graphs and (ii) of minimal intervention sets in logical networks.

Conclusion

CellNetAnalyzer provides a single suite to perform structural and qualitative analysis of both mass-flow- and signal-flow-based cellular networks in a user-friendly environment. It provides a large toolbox with various, partially unique, functions and algorithms for functional network analysis.CellNetAnalyzer is freely available for academic use.

Metatool 5.0: fast and flexible elementary modes analysis

SUMMARY

Elementary modes analysis is a powerful tool in the constraint-based modeling of metabolic networks. In recent years, new approaches to calculating elementary modes in biochemical reaction networks have been developed. As a consequence, the program Metatool, which is one of the first programs dedicated to this purpose, has been reimplemented in order to make use of these new approaches. The performance of Metatool has been significantly increased and the new version 5.0 can now be run inside the GNU octave or Matlab environments to allow more flexible usage and integration with other tools.

AVAILABILITY

The script files and compiled shared libraries can be downloaded from the Metatool website at http://pinguin.biologie.uni-jena.de/bioinformatik/networks/index.html. Metatool consists of script files (m-files) for GNU octave as well as Matlab and shared libraries. The scripts are licensed under the GNU Public License and the use of the shared libraries is free for academic users and testing purposes. Commercial use of Metatool requires a special contract.

A methodology for the structural and functional analysis of signaling and regulatory networks

Background

Structural analysis of cellular interaction networks contributes to a deeper understanding of network-wide interdependencies, causal relationships, and basic functional capabilities. While the structural analysis of metabolic networks is a well-established field, similar methodologies have been scarcely developed and applied to signaling and regulatory networks.

Results

We propose formalisms and methods, relying on adapted and partially newly introduced approaches, which facilitate a structural analysis of signaling and regulatory networks with focus on functional aspects. We use two different formalisms to represent and analyze interaction networks: interaction graphs and (logical) interaction hypergraphs. We show that, in interaction graphs, the determination of feedback cycles and of all the signaling paths between any pair of species is equivalent to the computation of elementary modes known from metabolic networks. Knowledge on the set of signaling paths and feedback loops facilitates the computation of intervention strategies and the classification of compounds into activators, inhibitors, ambivalent factors, and non-affecting factors with respect to a certain species. In some cases, qualitative effects induced by perturbations can be unambiguously predicted from the network scheme. Interaction graphs however, are not able to capture AND relationships which do frequently occur in interaction networks. The consequent logical concatenation of all the arcs pointing into a species leads to Boolean networks. For a Boolean representation of cellular interaction networks we propose a formalism based on logical (or signed) interaction hypergraphs, which facilitates in particular a logical steady state analysis (LSSA). LSSA enables studies on the logical processing of signals and the identification of optimal intervention points (targets) in cellular networks. LSSA also reveals network regions whose parametrization and initial states are crucial for the dynamic behavior.

We have implemented these methods in our software tool CellNetAnalyzer (successor of FluxAnalyzer) and illustrate their applicability using a logical model of T-Cell receptor signaling providing non-intuitive results regarding feedback loops, essential elements, and (logical) signal processing upon different stimuli.

Conclusion

The methods and formalisms we propose herein are another step towards the comprehensive functional analysis of cellular interaction networks. Their potential, shown on a realistic T-cell signaling model, makes them a promising tool.