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

Minimizing enzyme mass to decompose flux distribution for identifying biologically relevant elementary flux modes

The flux distribution in metabolic network can be decomposed as non-negative linear combinations of elementary flux modes (EFMs). Identifying biologically relevant EFM combination by decomposing flux distribution in metabolic network is a useful method to study metabolisms in systems biology. However, the occurrence of biologically irrelevant EFMs hinders the application of such methods. In this paper, we introduce a novel method for identifying EFM combination by minimizing enzyme mass. Our proposed method, called EMMD (Enzyme Mass Minimization Decomposition), takes into consideration both thermodynamic and enzymatic constraints in stoichiometry metabolic models. By implementing EMMD, we can decompose the flux distributions in metabolic network to detect biologically relevant EFM combinations. We demonstrate the effectiveness of our method by applying it to the core Escherichia coli metabolic network and show that the optimal EFM combinations identified by EMMD are unique. Moreover, the optimal EFM combination identified by EMMD not only aligns more closely with experimental values in terms of estimated growth rate, but it also demonstrates more favorable thermodynamics. Finally, we investigated the growth of the core Escherichia coli metabolic network in Luria-Bertani medium containing different carbon sources, revealing the impact of various carbon sources on the growth rate of flux distribution. EMMD thus could be a promising complement to the existing flux decomposition tools.

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.

OptDesign: Identifying Optimum Design Strategies in Strain Engineering for Biochemical Production

Computational tools have been widely adopted for strain optimization in metabolic engineering, contributing to numerous success stories of producing industrially relevant biochemicals. However, most of these tools focus on single metabolic intervention strategies (either gene/reaction knockout or amplification alone) and rely on hypothetical optimality principles (e.g., maximization of growth) and precise gene expression (e.g., fold changes) for phenotype prediction. This paper introduces OptDesign, a new two-step strain design strategy. In the first step, OptDesign selects regulation candidates that have a noticeable flux difference between the wild type and production strains. In the second step, it computes optimal design strategies with limited manipulations (combining regulation and knockout), leading to high biochemical production. The usefulness and capabilities of OptDesign are demonstrated for the production of three biochemicals in Escherichia coli using the latest genome-scale metabolic model iML1515, showing highly consistent results with previous studies while suggesting new manipulations to boost strain performance. The source code is available at https://github.com/chang88ye/OptDesign.

How to Tackle Underdeterminacy in Metabolic Flux Analysis? A Tutorial and Critical Review

Metabolic flux analysis is often (not to say almost always) faced with system underdeterminacy. Indeed, the linear algebraic system formed by the steady-state mass balance equations around the intracellular metabolites and the equality constraints related to the measurements of extracellular fluxes do not define a unique solution for the distribution of intracellular fluxes, but instead a set of solutions belonging to a convex polytope. Various methods have been proposed to tackle this underdeterminacy, including flux pathway analysis, flux balance analysis, flux variability analysis and sampling. These approaches are reviewed in this article and a toy example supports the discussion with illustrative numerical results.

Unlocking Elementary Conversion Modes: ecmtool Unveils All Capabilities of Metabolic Networks

The metabolic capabilities of cells determine their biotechnological potential, fitness in ecosystems, pathogenic threat levels, and function in multicellular organisms. Their comprehensive experimental characterization is generally not feasible, particularly for unculturable organisms. In principle, the full range of metabolic capabilities can be computed from an organism's annotated genome using metabolic network reconstruction. However, current computational methods cannot deal with genome-scale metabolic networks. Part of the problem is that these methods aim to enumerate all metabolic pathways, while computation of all (elementally balanced) conversions between nutrients and products would suffice. Indeed, the elementary conversion modes (ECMs, defined by Urbanczik and Wagner) capture the full metabolic capabilities of a network, but the use of ECMs has not been accessible until now. We explain and extend the theory of ECMs, implement their enumeration in ecmtool, and illustrate their applicability. This work contributes to the elucidation of the full metabolic footprint of any cell.

•

Elementary conversion modes (ECMs) specify all metabolic capabilities of any organism

•

Ecmtool computes all ECMs from a reconstructed metabolic network

•

ECM enumeration enables metabolic characterization of larger networks than ever

•

Focusing on ECMs between relevant metabolites even enables genome-scale enumeration

Understanding the metabolic capabilities of cells is of profound importance. Microbial metabolism shapes global cycles of elements and cleans polluted soils. Human and pathogen metabolism affects our health. Recent advances allow for automatic reconstruction of reaction networks for any organism, which is already used in synthetic biology, (food) microbiology, and agriculture to compute optimal yields from resources to products. However, computational tools are limited to optimal states or subnetworks, leaving many capabilities of organisms hidden. Our program, ecmtool, creates a blueprint of any organism's metabolic functionalities, drastically improving insights obtained from genome sequences. Ecmtool may become essential in exploratory research, especially for studying cells that are not culturable in laboratory conditions. Ideally, elementary conversion mode enumeration will someday be a standard step after metabolic network reconstruction, achieving the metabolic characterization of all known organisms.

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.

A system architecture for parallel analysis of flux-balanced metabolic pathways

Elementary flux mode (EFM) analysis is a well-studied method in constraint-based modeling of metabolic networks. In EFM analysis, a network is decomposed into minimal functional pathways based on the assumption of balanced metabolic fluxes. In this paper, a system architecture is proposed that approximately models the functionality of metabolic networks. The AND/OR graph model is used to represent the metabolic network and each processing element in the system emulates the functionality of a metabolite. The system is implemented on a graphics processing unit (GPU) as the hardware platform using CUDA environment. The proposed architecture takes advantage of the inherent parallelism in the network structure in terms of both pathway and metabolite traversal. The function of each element is defined such that it can find flux-balanced pathways. Pathways in both small and large metabolic networks are applied to the proposed architecture and the results are discussed.

EFMviz: A COBRA Toolbox extension to visualize Elementary Flux Modes in Genome-Scale Metabolic Models

Elementary Flux Modes (EFMs) are a tool for constraint-based modeling and metabolic network analysis. However, systematic and automated visualization of EFMs, capable of integrating various data types is still a challenge. In this study, we developed an extension for the widely adopted COBRA Toolbox, EFMviz, for analysis and graphical visualization of EFMs as networks of reactions, metabolites and genes. The analysis workflow offers a platform for EFM visualization to improve EFM interpretability by connecting COBRA toolbox with the network analysis and visualization software Cytoscape. The biological applicability of EFMviz is demonstrated in two use cases on medium (Escherichia coli, iAF1260) and large (human, Recon 2.2) genome-scale metabolic models. EFMviz is open-source and integrated into COBRA Toolbox. The analysis workflows used for the two use cases are detailed in the two tutorials provided with EFMviz along with the data used in this study.

Comparison of pathway analysis and constraint-based methods for cell factory design

BACKGROUND

Computational strain optimisation methods (CSOMs) have been successfully used to exploit genome-scale metabolic models, yielding strategies useful for allowing compound overproduction in metabolic cell factories. Minimal cut sets are particularly interesting since their definition allows searching for intervention strategies that impose strong growth-coupling phenotypes, and are not subject to optimality bias when compared with simulation-based CSOMs. However, since both types of methods have different underlying principles, they also imply different ways to formulate metabolic engineering problems, posing an obstacle when comparing their outputs.

RESULTS

In this work, we perform an in-depth analysis of potential strategies that can be obtained with both methods, providing a critical comparison of performance, robustness, predicted phenotypes as well as strategy structure and size. To this end, we devised a pipeline including enumeration of strategies from evolutionary algorithms (EA) and minimal cut sets (MCS), filtering and flux analysis of predicted mutants to optimize the production of succinic acid in Saccharomyces cerevisiae. We additionally attempt to generalize problem formulations for MCS enumeration within the context of growth-coupled product synthesis. Strategies from evolutionary algorithms show the best compromise between acceptable growth rates and compound overproduction. However, constrained MCSs lead to a larger variety of phenotypes with several degrees of growth-coupling with production flux. The latter have proven useful in revealing the importance, in silico, of the gamma-aminobutyric acid shunt and manipulation of cofactor pools in growth-coupled designs for succinate production, mechanisms which have also been touted as potentially useful for metabolic engineering.

CONCLUSIONS

The two main groups of CSOMs are valuable for finding growth-coupled mutants. Despite the limitations in maximum growth rates and large strategy sizes, MCSs help uncover novel mechanisms for compound overproduction and thus, analyzing outputs from both methods provides a richer overview on strategies that can be potentially carried over in vivo.

Novel column generation-based optimization approach for poly-pathway kinetic model applied to CHO cell culture

Mathematical modelling can provide precious tools for bioprocess simulation, prediction, control and optimization of mammalian cell-based cultures. In this paper we present a novel method to generate kinetic models of such cultures, rendering complex metabolic networks in a poly-pathway kinetic model. The model is based on subsets of elementary flux modes (EFMs) to generate macro-reactions. Thanks to our column generation-based optimization algorithm, the experimental data are used to identify the EFMs, which are relevant to the data. Here the systematic enumeration of all the EFMs is eliminated and a network including a large number of reactions can be considered. In particular, the poly-pathway model can simulate multiple metabolic behaviors in response to changes in the culture conditions.

We apply the method to a network of 126 metabolic reactions describing cultures of antibody-producing Chinese hamster ovary cells, and generate a poly-pathway model that simulates multiple experimental conditions obtained in response to variations in amino acid availability. A good fit between simulated and experimental data is obtained, rendering the variations in the growth, product, and metabolite uptake/secretion rates. The intracellular reaction fluxes simulated by the model are explored, linking variations in metabolic behavior to adaptations of the intracellular metabolism.

•

Novel method to model multiple states by a poly-pathway kinetic model.

•

EFMs relevant to data identified by column generation (CG)-based optimization.

•

CG optimization enables use of networks much larger than systematic enumeration.

•

A kinetic model simulates changes in metabolic rates linked to available amino acids.

•

The flux distribution of each metabolic state is visualized in the original network.

Sequential computation of elementary modes and minimal cut sets in genome-scale metabolic networks using alternate integer linear programming

Motivation

Elementary (flux) modes (EMs) have served as a valuable tool for investigating structural and functional properties of metabolic networks. Identification of the full set of EMs in genome-scale networks remains challenging due to combinatorial explosion of EMs in complex networks. It is often, however, that only a small subset of relevant EMs needs to be known, for which optimization-based sequential computation is a useful alternative. Most of the currently available methods along this line are based on the iterative use of mixed integer linear programming (MILP), the effectiveness of which significantly deteriorates as the number of iterations builds up. To alleviate the computational burden associated with the MILP implementation, we here present a novel optimization algorithm termed alternate integer linear programming (AILP).

Results

Our algorithm was designed to iteratively solve a pair of integer programming (IP) and linear programming (LP) to compute EMs in a sequential manner. In each step, the IP identifies a minimal subset of reactions, the deletion of which disables all previously identified EMs. Thus, a subsequent LP solution subject to this reaction deletion constraint becomes a distinct EM. In cases where no feasible LP solution is available, IP-derived reaction deletion sets represent minimal cut sets (MCSs). Despite the additional computation of MCSs, AILP achieved significant time reduction in computing EMs by orders of magnitude. The proposed AILP algorithm not only offers a computational advantage in the EM analysis of genome-scale networks, but also improves the understanding of the linkage between EMs and MCSs.

Availability and Implementation

The software is implemented in Matlab, and is provided as supplementary information .

Contact

hyunseob.song@pnnl.gov.

Supplementary information

Supplementary data are available at Bioinformatics online.

EColiCore2: a reference network model of the central metabolism of Escherichia coli and relationships to its genome-scale parent model

Genome-scale metabolic modeling has become an invaluable tool to analyze properties and capabilities of metabolic networks and has been particularly successful for the model organism Escherichia coli. However, for several applications, smaller metabolic (core) models are needed. Using a recently introduced reduction algorithm and the latest E. coli genome-scale reconstruction iJO1366, we derived EColiCore2, a model of the central metabolism of E. coli. EColiCore2 is a subnetwork of iJO1366 and preserves predefined phenotypes including optimal growth on different substrates. The network comprises 486 metabolites and 499 reactions, is accessible for elementary-modes analysis and can, if required, be further compressed to a network with 82 reactions and 54 metabolites having an identical solution space as EColiCore2. A systematic comparison of EColiCore2 with its genome-scale parent model iJO1366 reveals that several key properties (flux ranges, reaction essentialities, production envelopes) of the central metabolism are preserved in EColiCore2 while it neglects redundancies along biosynthetic routes. We also compare calculated metabolic engineering strategies in both models and demonstrate, as a general result, how intervention strategies found in a core model allow the identification of valid strategies in a genome-scale model. Overall, EColiCore2 holds promise to become a reference model of E. coli's central metabolism.

Stoichiometric Representation of Gene-Protein-Reaction Associations Leverages Constraint-Based Analysis from Reaction to Gene-Level Phenotype Prediction

Genome-scale metabolic reconstructions are currently available for hundreds of organisms. Constraint-based modeling enables the analysis of the phenotypic landscape of these organisms, predicting the response to genetic and environmental perturbations. However, since constraint-based models can only describe the metabolic phenotype at the reaction level, understanding the mechanistic link between genotype and phenotype is still hampered by the complexity of gene-protein-reaction associations. We implement a model transformation that enables constraint-based methods to be applied at the gene level by explicitly accounting for the individual fluxes of enzymes (and subunits) encoded by each gene. We show how this can be applied to different kinds of constraint-based analysis: flux distribution prediction, gene essentiality analysis, random flux sampling, elementary mode analysis, transcriptomics data integration, and rational strain design. In each case we demonstrate how this approach can lead to improved phenotype predictions and a deeper understanding of the genotype-to-phenotype link. In particular, we show that a large fraction of reaction-based designs obtained by current strain design methods are not actually feasible, and show how our approach allows using the same methods to obtain feasible gene-based designs. We also show, by extensive comparison with experimental 13C-flux data, how simple reformulations of different simulation methods with gene-wise objective functions result in improved prediction accuracy. The model transformation proposed in this work enables existing constraint-based methods to be used at the gene level without modification. This automatically leverages phenotype analysis from reaction to gene level, improving the biological insight that can be obtained from genome-scale models.

Constructing kinetic models of metabolism at genome-scales: A review

Constraint-based modeling of biological networks (metabolism, transcription and signal transduction), although used successfully in many applications, suffer from specific limitations such as the lack of representation of metabolite concentrations and enzymatic regulation, which are necessary for a complete physiologically relevant model. Kinetic models conversely overcome these shortcomings and enable dynamic analysis of biological systems for enhanced in silico hypothesis generation. Nonetheless, kinetic models also have limitations for modeling at genome-scales chiefly due to: (i) model non-linearity; (ii) computational tractability; (iii) parameter identifiability; (iv) estimability; and (v) uncertainty. In order to support further development of kinetic models as viable alternatives to constraint-based models, this review presents a brief description of the existing obstacles towards building genome-scale kinetic models. Specific kinetic modeling frameworks capable of overcoming these obstacles are covered in this review. The tractability and physiological feasibility of these models are discussed with the objective of using available in vivo experimental observations to define the model parameter space. Among the different methods discussed, Monte Carlo kinetic models of metabolism stand out as potentially tractable methods to model genome scale networks while also addressing in vivo parameter uncertainty.

Which sets of elementary flux modes form thermodynamically feasible flux distributions?

Elementary flux modes (EFMs) are non-decomposable steady-state fluxes through metabolic networks. Every possible flux through a network can be described as a superposition of EFMs. The definition of EFMs is based on the stoichiometry of the network, and it has been shown previously that not all EFMs are thermodynamically feasible. These infeasible EFMs cannot contribute to a biologically meaningful flux distribution. In this work, we show that a set of thermodynamically feasible EFMs need not be thermodynamically consistent. We use first principles of thermodynamics to define the feasibility of a flux distribution and present a method to compute the largest thermodynamically consistent sets (LTCSs) of EFMs. An LTCS contains the maximum number of EFMs that can be combined to form a thermodynamically feasible flux distribution. As a case study we analyze all LTCSs found in Escherichia coli when grown on glucose and show that only one LTCS shows the required phenotypical properties. Using our method, we find that in our E. coli model < 10% of all EFMs are thermodynamically relevant.

Direct calculation of minimal cut sets involving a specific reaction knock-out

MOTIVATION

The concept of Minimal Cut Sets (MCSs) is used in metabolic network modeling to describe minimal groups of reactions or genes whose simultaneous deletion eliminates the capability of the network to perform a specific task. Previous work showed that MCSs where closely related to Elementary Flux Modes (EFMs) in a particular dual problem, opening up the possibility to use the tools developed for computing EFMs to compute MCSs. Until recently, however, there existed no method to compute an EFM with some specific characteristic, meaning that, in the case of MCSs, the only strategy to obtain them was to enumerate them using, for example, the standard K-shortest EFMs algorithm.

RESULTS

In this work, we adapt the recently developed theory to compute EFMs satisfying several constraints to the calculation of MCSs involving a specific reaction knock-out. Importantly, we emphasize that not all the EFMs in the dual problem correspond to real MCSs, and propose a new formulation capable of correctly identifying the MCS wanted. Furthermore, this formulation brings interesting insights about the relationship between the primal and the dual problem of the MCS computation.

AVAILABILITY AND IMPLEMENTATION

A Matlab-Cplex implementation of the proposed algorithm is available as a supplementary material

CONTACT

fplanes@ceit.es

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Characterizing the optimal flux space of genome-scale metabolic reconstructions through modified latin-hypercube sampling

Sampling of the optimal flux space using modified LHS gives a more uniform coverage than Monte-Carlo Sampling. Analysis of the flux data shows that majority of variation in the flux distribution pattern within the space arises due to the presence of few alternate pathways.

gEFM: An Algorithm for Computing Elementary Flux Modes Using Graph Traversal

Computational methods to engineer cellular metabolism promise to play a critical role in producing pharmaceutical, repairing defective genes, destroying cancer cells, and generating biofuels. Elementary Flux Mode (EFM) analysis is one such powerful technique that has elucidated cell growth and regulation, predicted product yield, and analyzed network robustness. EFM analysis, however, is a computationally daunting task because it requires the enumeration of all independent and stoichiometrically balanced pathways within a cellular network. We present in this paper an EFM enumeration algorithm, termed graphical EFM or gEFM. The algorithm is based on graph traversal, an approach previously assumed unsuitable for enumerating EFMs. The approach is derived from a pathway synthesis method proposed by Mavrovouniotis et al. The algorithm is described and proved correct. We apply gEFM to several networks and report runtimes in comparison with other EFM computation tools. We show how gEFM benefits from network compression. Like other EFM computational techniques, gEFM is sensitive to constraint ordering; however, we are able to demonstrate that knowledge of the underlying network structure leads to better constraint ordering. gEFM is shown to be competitive with state-of-the-art EFM computational techniques for several networks, but less so for networks with a larger number of EFMs.

In Silico Constraint-Based Strain Optimization Methods: the Quest for Optimal Cell Factories

Shifting from chemical to biotechnological processes is one of the cornerstones of 21st century industry. The production of a great range of chemicals via biotechnological means is a key challenge on the way toward a bio-based economy. However, this shift is occurring at a pace slower than initially expected. The development of efficient cell factories that allow for competitive production yields is of paramount importance for this leap to happen. Constraint-based models of metabolism, together with in silico strain design algorithms, promise to reveal insights into the best genetic design strategies, a step further toward achieving that goal. In this work, a thorough analysis of the main in silico constraint-based strain design strategies and algorithms is presented, their application in real-world case studies is analyzed, and a path for the future is discussed.

Designing overall stoichiometric conversions and intervening metabolic reactions

Existing computational tools for de novo metabolic pathway assembly, either based on mixed integer linear programming techniques or graph-search applications, generally only find linear pathways connecting the source to the target metabolite. The overall stoichiometry of conversion along with alternate co-reactant (or co-product) combinations is not part of the pathway design. Therefore, global carbon and energy efficiency is in essence fixed with no opportunities to identify more efficient routes for recycling carbon flux closer to the thermodynamic limit. Here, we introduce a two-stage computational procedure that both identifies the optimum overall stoichiometry (i.e., optStoic) and selects for (non-)native reactions (i.e., minRxn/minFlux) that maximize carbon, energy or price efficiency while satisfying thermodynamic feasibility requirements. Implementation for recent pathway design studies identified non-intuitive designs with improved efficiencies. Specifically, multiple alternatives for non-oxidative glycolysis are generated and non-intuitive ways of co-utilizing carbon dioxide with methanol are revealed for the production of C₂₊ metabolites with higher carbon efficiency.

Rational design of efficient modular cells

The modular cell design principle is formulated to devise modular (chassis) cells. These cells can be assembled with exchangeable production modules in a plug-and-play fashion to build microbial cell factories for efficient combinatorial biosynthesis of novel molecules, requiring minimal iterative strain optimization steps. A modular cell is designed to be auxotrophic, containing core metabolic pathways that are necessary but insufficient to support cell growth and maintenance. To be functional, it must tightly couple with an exchangeable production module containing auxiliary metabolic pathways that not only complement cell growth but also enhance production of targeted molecules. We developed a MODCELL (modular cell) framework based on metabolic pathway analysis to implement the modular cell design principle. MODCELL identifies genetic modifications and requirements to construct modular cell candidates and their associated exchangeable production modules. By defining the degree of similarity and coupling metrics, MODCELL can evaluate which exchangeable production module(s) can be tightly coupled with a modular cell candidate. We first demonstrated how MODCELL works in a step-by-step manner for example metabolic networks, and then applied it to design modular Escherichia coli cells for efficient combinatorial biosynthesis of five alcohols (ethanol, propanol, isopropanol, butanol and isobutanol) and five butyrate esters (ethyl butyrate, propyl butyrate, isopropyl butyrate, butyl butyrate and isobutyl butyrate) from pentose sugars (arabinose and xylose) and hexose sugars (glucose, mannose, and galactose) under anaerobic conditions. We identified three modular cells, MODCELL1, MODCELL2 and MODCELL3, that can couple well with Group 1 of modules (ethanol, isobutanol, butanol, ethyl butyrate, isobutyl butyrate, butyl butyrate), Group 2 (isopropanol, isopropyl butyrate), and Group 3 (propanol, isopropanol), respectively. We validated the design of MODCELL1 for anaerobic production of ethanol, butanol, and ethyl butyrate using experimental data available in literature.

Obstructions to Sampling Qualitative Properties

Background

Sampling methods have proven to be a very efficient and intuitive method to understand properties of complicated spaces that cannot easily be computed using deterministic methods. Therefore, sampling methods became a popular tool in the applied sciences.

Results

Here, we show that sampling methods are not an appropriate tool to analyze qualitative properties of complicated spaces unless RP = NP. We illustrate these results on the example of the thermodynamically feasible flux space of genome-scale metabolic networks and show that with artificial centering hit and run (ACHR) not all reactions that can have variable flux rates are sampled with variables flux rates. In particular a uniform sample of the flux space would not sample the flux variabilities completely.

Conclusion

We conclude that unless theoretical convergence results exist, qualitative results obtained from sampling methods should be considered with caution and if possible double checked using a deterministic method.

Avoiding the Enumeration of Infeasible Elementary Flux Modes by Including Transcriptional Regulatory Rules in the Enumeration Process Saves Computational Costs

Despite the significant progress made in recent years, the computation of the complete set of elementary flux modes of large or even genome-scale metabolic networks is still impossible. We introduce a novel approach to speed up the calculation of elementary flux modes by including transcriptional regulatory information into the analysis of metabolic networks. Taking into account gene regulation dramatically reduces the solution space and allows the presented algorithm to constantly eliminate biologically infeasible modes at an early stage of the computation procedure. Thereby, computational costs, such as runtime, memory usage, and disk space, are extremely reduced. Moreover, we show that the application of transcriptional rules identifies non-trivial system-wide effects on metabolism. Using the presented algorithm pushes the size of metabolic networks that can be studied by elementary flux modes to new and much higher limits without the loss of predictive quality. This makes unbiased, system-wide predictions in large scale metabolic networks possible without resorting to any optimization principle.

Co-evolution of strain design methods based on flux balance and elementary mode analysis

More than a decade ago, the first genome-scale metabolic models for two of the most relevant microbes for biotechnology applications, Escherichia coli and Saccaromyces cerevisiae, were published. Shortly after followed the publication of OptKnock, the first strain design method using bilevel optimization to couple cellular growth with the production of a target product. This initiated the development of a family of strain design methods based on the concept of flux balance analysis. Another family of strain design methods, based on the concept of elementary mode analysis, has also been growing. Although the computation of elementary modes is hindered by computational complexity, recent breakthroughs have allowed applying elementary mode analysis at the genome scale. Here we review and compare strain design methods and look back at the last 10 years of in silico strain design with constraint-based models. We highlight some features of the different approaches and discuss the utilization of these methods in successful in vivo metabolic engineering applications.

•

Computational strain design methods are divided into two main families.

•

We trace the evolutionary history of these two families.

•

Surveyed successful cases of model-guided strain design for industrial applications.

•

Most proposed methods have not yet been tested in real applications.

•

Agreement between in silico and in vivo results shows potential of tested methods.

Predicting genetic engineering targets with Elementary Flux Mode Analysis: a review of four current methods

Elementary flux modes (EFMs) are a well-established tool in metabolic modeling. EFMs are minimal, feasible, steady state pathways through a metabolic network. They are used in various approaches to predict targets for genetic interventions in order to increase production of a molecule of interest via a host cell. Here we give an introduction to the concept of EFMs, present an overview of four methods which use EFMs in order to predict engineering targets and lastly use a toy model and a small-scale metabolic model to demonstrate and compare the capabilities of these methods.

Metabolomics integrated elementary flux mode analysis in large metabolic networks

Elementary flux modes (EFMs) are non-decomposable steady-state pathways in metabolic networks. They characterize phenotypes, quantify robustness or identify engineering targets. An EFM analysis (EFMA) is currently restricted to medium-scale models, as the number of EFMs explodes with the network's size. However, many topologically feasible EFMs are biologically irrelevant. We present thermodynamic EFMA (tEFMA), which calculates only the small(er) subset of thermodynamically feasible EFMs. We integrate network embedded thermodynamics into EFMA and show that we can use the metabolome to identify and remove thermodynamically infeasible EFMs during an EFMA without losing biologically relevant EFMs. Calculating only the thermodynamically feasible EFMs strongly reduces memory consumption and program runtime, allowing the analysis of larger networks. We apply tEFMA to study the central carbon metabolism of E. coli and find that up to 80% of its EFMs are thermodynamically infeasible. Moreover, we identify glutamate dehydrogenase as a bottleneck, when E. coli is grown on glucose and explain its inactivity as a consequence of network embedded thermodynamics. We implemented tEFMA as a Java package which is available for download at https://github.com/mpgerstl/tEFMA.

tEFMA: computing thermodynamically feasible elementary flux modes in metabolic networks

: Elementary flux modes (EFMs) are important structural tools for the analysis of metabolic networks. It is known that many topologically feasible EFMs are biologically irrelevant. Therefore, tools are needed to find the relevant ones. We present thermodynamic tEFM analysis (tEFMA) which uses the cellular metabolome to avoid the enumeration of thermodynamically infeasible EFMs. Specifically, given a metabolic network and a not necessarily complete metabolome, tEFMA efficiently returns the full set of thermodynamically feasible EFMs consistent with the metabolome. Compared with standard approaches, tEFMA strongly reduces the memory consumption and the overall runtime. Thus tEFMA provides a new way to analyze unbiasedly hitherto inaccessible large-scale metabolic networks.

AVAILABILITY AND IMPLEMENTATION

https://github.com/mpgerstl/tEFMA CONTACT: : christian.jungreuthmayer@boku.ac.at or juergen.zanghellini@boku.ac.at

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Development and application of efficient pathway enumeration algorithms for metabolic engineering applications

Metabolic Engineering (ME) aims to design microbial cell factories towards the production of valuable compounds. In this endeavor, one important task relates to the search for the most suitable heterologous pathway(s) to add to the selected host. Different algorithms have been developed in the past towards this goal, following distinct approaches spanning constraint-based modeling, graph-based methods and knowledge-based systems based on chemical rules. While some of these methods search for pathways optimizing specific objective functions, here the focus will be on methods that address the enumeration of pathways that are able to convert a set of source compounds into desired targets and their posterior evaluation according to different criteria. Two pathway enumeration algorithms based on (hyper)graph-based representations are selected as the most promising ones and are analyzed in more detail: the Solution Structure Generation and the Find Path algorithms. Their capabilities and limitations are evaluated when designing novel heterologous pathways, by applying these methods on three case studies of synthetic ME related to the production of non-native compounds in E. coli and S. cerevisiae: 1-butanol, curcumin and vanillin. Some targeted improvements are implemented, extending both methods to address limitations identified that impair their scalability, improving their ability to extract potential pathways over large-scale databases. In all case-studies, the algorithms were able to find already described pathways for the production of the target compounds, but also alternative pathways that can represent novel ME solutions after further evaluation.

Estimating biological elementary flux modes that decompose a flux distribution by the minimal branching property

MOTIVATION

Elementary flux mode (EFM) is a useful tool in constraint-based modeling of metabolic networks. The property that every flux distribution can be decomposed as a weighted sum of EFMs allows certain applications of EFMs to studying flux distributions. The existence of biologically infeasible EFMs and the non-uniqueness of the decomposition, however, undermine the applicability of such methods. Efforts have been made to find biologically feasible EFMs by incorporating information from transcriptional regulation and thermodynamics. Yet, no attempt has been made to distinguish biologically feasible EFMs by considering their graphical properties. A previous study on the transcriptional regulation of metabolic genes found that distinct branches at a branch point metabolite usually belong to distinct metabolic pathways. This suggests an intuitive property of biologically feasible EFMs, i.e. minimal branching.

RESULTS

We developed the concept of minimal branching EFM and derived the minimal branching decomposition (MBD) to decompose flux distributions. Testing in the core Escherichia coli metabolic network indicated that MBD can distinguish branches at branch points and greatly reduced the solution space in which the decomposition is often unique. An experimental flux distribution from a previous study on mouse cardiomyocyte was decomposed using MBD. Comparison with decomposition by a minimum number of EFMs showed that MBD found EFMs more consistent with established biological knowledge, which facilitates interpretation. Comparison of the methods applied to a complex flux distribution in Lactococcus lactis similarly showed the advantages of MBD. The minimal branching EFM concept underlying MBD should be useful in other applications.

CONTACT

sinhu@bio.dtu.dk or p.ji@polyu.edu.hk

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

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.

Finding elementary flux modes in metabolic networks based on flux balance analysis and flux coupling analysis: application to the analysis of Escherichia coli metabolism

Elementary modes (EMs) are steady-state metabolic flux vectors with minimal set of active reactions. Each EM corresponds to a metabolic pathway. Therefore, studying EMs is helpful for analyzing the production of biotechnologically important metabolites. However, memory requirements for computing EMs may hamper their applicability as, in most genome-scale metabolic models, no EM can be computed due to running out of memory. In this study, we present a method for computing randomly sampled EMs. In this approach, a network reduction algorithm is used for EM computation, which is based on flux balance-based methods. We show that this approach can be used to recover the EMs in the medium- and genome-scale metabolic network models, while the EMs are sampled in an unbiased way. The applicability of such results is shown by computing “estimated” control-effective flux values in Escherichia coli metabolic network.

Direct calculation of elementary flux modes satisfying several biological constraints in genome-scale metabolic networks

MOTIVATION

The concept of Elementary Flux Mode (EFM) has been widely used for the past 20 years. However, its application to genome-scale metabolic networks (GSMNs) is still under development because of methodological limitations. Therefore, novel approaches are demanded to extend the application of EFMs. A novel family of methods based on optimization is emerging that provides us with a subset of EFMs. Because the calculation of the whole set of EFMs goes beyond our capacity, performing a selective search is a proper strategy.

RESULTS

Here, we present a novel mathematical approach calculating EFMs fulfilling additional linear constraints. We validated our approach based on two metabolic networks in which all the EFMs can be obtained. Finally, we analyzed the performance of our methodology in the GSMN of the yeast Saccharomyces cerevisiae by calculating EFMs producing ethanol with a given minimum carbon yield. Overall, this new approach opens new avenues for the calculation of EFMs in GSMNs.

AVAILABILITY AND IMPLEMENTATION

Matlab code is provided in the supplementary online materials

CONTACT

fplanes@ceit.es.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Structural control of metabolic flux

Organisms have to continuously adapt to changing environmental conditions or undergo developmental transitions. To meet the accompanying change in metabolic demands, the molecular mechanisms of adaptation involve concerted interactions which ultimately induce a modification of the metabolic state, which is characterized by reaction fluxes and metabolite concentrations. These state transitions are the effect of simultaneously manipulating fluxes through several reactions. While metabolic control analysis has provided a powerful framework for elucidating the principles governing this orchestrated action to understand metabolic control, its applications are restricted by the limited availability of kinetic information. Here, we introduce structural metabolic control as a framework to examine individual reactions' potential to control metabolic functions, such as biomass production, based on structural modeling. The capability to carry out a metabolic function is determined using flux balance analysis (FBA). We examine structural metabolic control on the example of the central carbon metabolism of Escherichia coli by the recently introduced framework of functional centrality (FC). This framework is based on the Shapley value from cooperative game theory and FBA, and we demonstrate its superior ability to assign “share of control” to individual reactions with respect to metabolic functions and environmental conditions. A comparative analysis of various scenarios illustrates the usefulness of FC and its relations to other structural approaches pertaining to metabolic control. We propose a Monte Carlo algorithm to estimate FCs for large networks, based on the enumeration of elementary flux modes. We further give detailed biological interpretation of FCs for production of lactate and ATP under various respiratory conditions.

Insight into the functioning of metabolic control to meet changing demands is a first step in rational engineering of biological systems towards a desired behavior. Metabolic control analysis provides the means to examine the impact of change of reaction fluxes on a specific target flux based on kinetic modeling, but suffers from limitations of the kinetic approach. Here, we introduce and analyze structural metabolic control as a framework to overcome these limitations. We utilize functional centrality, a framework based on the Shapley value from cooperative game theory and flux balance analysis, to determine the contribution of individual reactions to the functions accomplished by a metabolic network. These contributions, in turn, depend on the control exerted on the remaining network. Functional centrality provides the mathematical means to gain further understanding of metabolic control. The potential applications range from facilitating strategies of rational strain design to drug target identification.

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.

Identification of metabolic engineering targets through analysis of optimal and sub-optimal routes

Identification of optimal genetic manipulation strategies for redirecting substrate uptake towards a desired product is a challenging task owing to the complexity of metabolic networks, esp. in terms of large number of routes leading to the desired product. Algorithms that can exploit the whole range of optimal and suboptimal routes for product formation while respecting the biological objective of the cell are therefore much needed. Towards addressing this need, we here introduce the notion of structural flux, which is derived from the enumeration of all pathways in the metabolic network in question and accounts for the contribution towards a given biological objective function. We show that the theoretically estimated structural fluxes are good predictors of experimentally measured intra-cellular fluxes in two model organisms, namely, Escherichia coli and Saccharomyces cerevisiae. For a small number of fluxes for which the predictions were poor, the corresponding enzyme-coding transcripts were also found to be distinctly regulated, showing the ability of structural fluxes in capturing the underlying regulatory principles. Exploiting the observed correspondence between in vivo fluxes and structural fluxes, we propose an in silico metabolic engineering approach, iStruF, which enables the identification of gene deletion strategies that couple the cellular biological objective with the product flux while considering optimal as well as sub-optimal routes and their efficiency.

Integration of time-resolved transcriptomics data with flux-based methods reveals stress-induced metabolic adaptation in Escherichia coli

Background

Changes in environmental conditions require temporal effectuation of different metabolic pathways in order to maintain the organisms’ viability but also to enable the settling into newly arising conditions. While analyses of robustness in biological systems have resulted in the characterization of reactions that facilitate homeostasis, temporal adaptation-related processes and the role of cellular pathways in the metabolic response to changing conditions remain elusive.

Results

Here we develop a flux-based approach that allows the integration of time-resolved transcriptomics data with genome-scale metabolic networks. Our framework uses bilevel optimization to extract temporal minimal operating networks from a given large-scale metabolic model. The minimality of the extracted networks enables the computation of elementary flux modes for each time point, which are in turn used to characterize the transitional behavior of the network as well as of individual reactions. Application of the approach to the metabolic network of Escherichia coli in conjunction with time-series gene expression data from cold and heat stress results in two distinct time-resolved modes for reaction utilization—constantly active and temporally (de)activated reactions. These patterns contrast the processes for the maintenance of basic cellular functioning and those required for adaptation. They also allow the prediction of reactions involved in time- and stress-specific metabolic response and are verified with respect to existing experimental studies.

Conclusions

Altogether, our findings pinpoint the inherent relation between the systemic properties of robustness and adaptability arising from the interplay of metabolic network structure and changing environment.