Analysis of complex metabolic behavior through pathway decomposition

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.

Finding MEMo: minimum sets of elementary flux modes

Metabolic network reconstructions are widely used in computational systems biology for in silico studies of cellular metabolism. A common approach to analyse these models are elementary flux modes (EFMs), which correspond to minimal functional units in the network. Already for medium-sized networks, it is often impossible to compute the set of all EFMs, due to their huge number. From a practical point of view, this might also not be necessary because a subset of EFMs may already be sufficient to answer relevant biological questions. In this article, we study MEMos or minimum sets of EFMs that can generate all possible steady-state behaviours of a metabolic network. The number of EFMs in a MEMo may be by several orders of magnitude smaller than the total number of EFMs. Using MEMos, we can compute generating sets of EFMs in metabolic networks where the whole set of EFMs is too large to be enumerated.

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.

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.

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.

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.

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.

Constraining the metabolic genotype-phenotype relationship using a phylogeny of in silico methods

Reconstructed microbial metabolic networks facilitate a mechanistic description of the genotype-phenotype relationship through the deployment of constraint-based reconstruction and analysis (COBRA) methods. As reconstructed networks leverage genomic data for insight and phenotype prediction, the development of COBRA methods has accelerated following the advent of whole-genome sequencing. Here, we describe a phylogeny of COBRA methods that has rapidly evolved from the few early methods, such as flux balance analysis and elementary flux mode analysis, into a repertoire of more than 100 methods. These methods have enabled genome-scale analysis of microbial metabolism for numerous basic and applied uses, including antibiotic discovery, metabolic engineering and modelling of microbial community behaviour.

Maximizing output and recognizing autocatalysis in chemical reaction networks is NP-complete

Background

A classical problem in metabolic design is to maximize the production of a desired compound in a given chemical reaction network by appropriately directing the mass flow through the network. Computationally, this problem is addressed as a linear optimization problem over the flux cone. The prior construction of the flux cone is computationally expensive and no polynomial-time algorithms are known.

Results

Here we show that the output maximization problem in chemical reaction networks is NP-complete. This statement remains true even if all reactions are monomolecular or bi-molecular and if only a single molecular species is used as influx. As a corollary we show, furthermore, that the detection of autocatalytic species, i.e., types that can only be produced from the influx material when they are present in the initial reaction mixture, is an NP-complete computational problem.

Conclusions

Hardness results on combinatorial problems and optimization problems are important to guide the development of computational tools for the analysis of metabolic networks in particular and chemical reaction networks in general. Our results indicate that efficient heuristics and approximate algorithms need to be employed for the analysis of large chemical networks since even conceptually simple flow problems are provably intractable.