1
|
Mahout M, Carlson RP, Simon L, Peres S. Logic programming-based Minimal Cut Sets reveal consortium-level therapeutic targets for chronic wound infections. NPJ Syst Biol Appl 2024; 10:34. [PMID: 38565568 PMCID: PMC10987626 DOI: 10.1038/s41540-024-00360-6] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/29/2023] [Accepted: 03/13/2024] [Indexed: 04/04/2024] Open
Abstract
Minimal Cut Sets (MCSs) identify sets of reactions which, when removed from a metabolic network, disable certain cellular functions. The traditional search for MCSs within genome-scale metabolic models (GSMMs) targets cellular growth, identifies reaction sets resulting in a lethal phenotype if disrupted, and retrieves a list of corresponding gene, mRNA, or enzyme targets. Using the dual link between MCSs and Elementary Flux Modes (EFMs), our logic programming-based tool aspefm was able to compute MCSs of any size from GSMMs in acceptable run times. The tool demonstrated better performance when computing large-sized MCSs than the mixed-integer linear programming methods. We applied the new MCSs methodology to a medically-relevant consortium model of two cross-feeding bacteria, Staphylococcus aureus and Pseudomonas aeruginosa. aspefm constraints were used to bias the computation of MCSs toward exchanged metabolites that could complement lethal phenotypes in individual species. We found that interspecies metabolite exchanges could play an essential role in rescuing single-species growth, for instance inosine could complement lethal reaction knock-outs in the purine synthesis, glycolysis, and pentose phosphate pathways of both bacteria. Finally, MCSs were used to derive a list of promising enzyme targets for consortium-level therapeutic applications that cannot be circumvented via interspecies metabolite exchange.
Collapse
Affiliation(s)
- Maxime Mahout
- Université Paris-Saclay, CNRS, Laboratoire Interdisciplinaire des Sciences du Numérique, 91405, Orsay, France
| | - Ross P Carlson
- Department of Chemical and Biological Engineering, Center for Biofilm Engineering, Microbiology and Immunology, Montana State University, Bozeman, MT, 59717, USA
| | - Laurent Simon
- Bordeaux-INP, Université Bordeaux, LaBRI, 33405, Talence Cedex, France
| | - Sabine Peres
- UMR CNRS 5558, Laboratoire de Biométrie et de Biologie Évolutive, Université Claude Bernard Lyon 1, 69100, Villeurbanne, France.
- INRIA Lyon Centre, 69100, Villeurbanne, France.
| |
Collapse
|
2
|
Guil F, Hidalgo JF, García JM. On the representativeness and stability of a set of EFMs. BIOINFORMATICS (OXFORD, ENGLAND) 2023; 39:btad356. [PMID: 37252834 PMCID: PMC10264373 DOI: 10.1093/bioinformatics/btad356] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/15/2022] [Revised: 04/18/2023] [Accepted: 05/30/2023] [Indexed: 06/01/2023]
Abstract
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.
Collapse
Affiliation(s)
- Francisco Guil
- Grupo de Arquitectura y Computación Paralela, Departamento de Ingeniería y Tecnología de Computadores, Facultad de Informática, Universidad de Murcia, Campus de Espinardo, Murcia 30100, Spain
| | - José F Hidalgo
- Grupo de Arquitectura y Computación Paralela, Departamento de Ingeniería y Tecnología de Computadores, Facultad de Informática, Universidad de Murcia, Campus de Espinardo, Murcia 30100, Spain
| | - José M García
- Grupo de Arquitectura y Computación Paralela, Departamento de Ingeniería y Tecnología de Computadores, Facultad de Informática, Universidad de Murcia, Campus de Espinardo, Murcia 30100, Spain
| |
Collapse
|
3
|
Elementary vectors and autocatalytic sets for resource allocation in next-generation models of cellular growth. PLoS Comput Biol 2022; 18:e1009843. [PMID: 35104290 PMCID: PMC8853647 DOI: 10.1371/journal.pcbi.1009843] [Citation(s) in RCA: 3] [Impact Index Per Article: 1.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/24/2021] [Revised: 02/17/2022] [Accepted: 01/18/2022] [Indexed: 11/19/2022] Open
Abstract
Traditional (genome-scale) metabolic models of cellular growth involve an approximate biomass “reaction”, which specifies biomass composition in terms of precursor metabolites (such as amino acids and nucleotides). On the one hand, biomass composition is often not known exactly and may vary drastically between conditions and strains. On the other hand, the predictions of computational models crucially depend on biomass. Also elementary flux modes (EFMs), which generate the flux cone, depend on the biomass reaction. To better understand cellular phenotypes across growth conditions, we introduce and analyze new classes of elementary vectors for comprehensive (next-generation) metabolic models, involving explicit synthesis reactions for all macromolecules. Elementary growth modes (EGMs) are given by stoichiometry and generate the growth cone. Unlike EFMs, they are not support-minimal, in general, but cannot be decomposed “without cancellations”. In models with additional (capacity) constraints, elementary growth vectors (EGVs) generate a growth polyhedron and depend also on growth rate. However, EGMs/EGVs do not depend on the biomass composition. In fact, they cover all possible biomass compositions and can be seen as unbiased versions of elementary flux modes/vectors (EFMs/EFVs) used in traditional models. To relate the new concepts to other branches of theory, we consider autocatalytic sets of reactions. Further, we illustrate our results in a small model of a self-fabricating cell, involving glucose and ammonium uptake, amino acid and lipid synthesis, and the expression of all enzymes and the ribosome itself. In particular, we study the variation of biomass composition as a function of growth rate. In agreement with experimental data, low nitrogen uptake correlates with high carbon (lipid) storage. Next-generation, genome-scale metabolic models allow to study the reallocation of cellular resources upon changing environmental conditions, by not only modeling flux distributions, but also expression profiles of the catalyzing proteome. In particular, they do no longer assume a fixed biomass composition. Methods to identify optimal solutions in such comprehensive models exist, however, an unbiased understanding of all feasible allocations is missing so far. Here we develop new concepts, called elementary growth modes and vectors, that provide a generalized definition of minimal pathways, thereby extending classical elementary flux modes (used in traditional models with a fixed biomass composition). The new concepts provide an understanding of all possible flux distributions and of all possible biomass compositions. In other words, elementary growth modes and vectors are the unique functional units in any comprehensive model of cellular growth. As an example, we show that lipid accumulation upon nitrogen starvation is a consequence of resource allocation and does not require active regulation. Our work puts current approaches on a theoretical basis and allows to seamlessly transfer existing workflows (e.g. for the design of cell factories) to next-generation metabolic models.
Collapse
|
4
|
Clement TJ, Baalhuis EB, Teusink B, Bruggeman FJ, Planqué R, de Groot DH. Unlocking Elementary Conversion Modes: ecmtool Unveils All Capabilities of Metabolic Networks. PATTERNS 2020; 2:100177. [PMID: 33511367 PMCID: PMC7815953 DOI: 10.1016/j.patter.2020.100177] [Citation(s) in RCA: 6] [Impact Index Per Article: 1.5] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 08/04/2020] [Revised: 10/07/2020] [Accepted: 12/04/2020] [Indexed: 01/23/2023]
Abstract
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.
Collapse
Affiliation(s)
- Tom J Clement
- Systems Biology Lab, Amsterdam Institute of Molecular and Life Sciences, Vrije Universiteit Amsterdam, De Boelelaan 1087, 1081 HV Amsterdam, the Netherlands
| | - Erik B Baalhuis
- Department of Mathematics, Vrije Universiteit Amsterdam, De Boelelaan 1081a, 1081 HV Amsterdam, the Netherlands
| | - Bas Teusink
- Systems Biology Lab, Amsterdam Institute of Molecular and Life Sciences, Vrije Universiteit Amsterdam, De Boelelaan 1087, 1081 HV Amsterdam, the Netherlands
| | - Frank J Bruggeman
- Systems Biology Lab, Amsterdam Institute of Molecular and Life Sciences, Vrije Universiteit Amsterdam, De Boelelaan 1087, 1081 HV Amsterdam, the Netherlands
| | - Robert Planqué
- Systems Biology Lab, Amsterdam Institute of Molecular and Life Sciences, Vrije Universiteit Amsterdam, De Boelelaan 1087, 1081 HV Amsterdam, the Netherlands.,Department of Mathematics, Vrije Universiteit Amsterdam, De Boelelaan 1081a, 1081 HV Amsterdam, the Netherlands
| | - Daan H de Groot
- Systems Biology Lab, Amsterdam Institute of Molecular and Life Sciences, Vrije Universiteit Amsterdam, De Boelelaan 1087, 1081 HV Amsterdam, the Netherlands
| |
Collapse
|
5
|
Answer Set Programming for Computing Constraints-Based Elementary Flux Modes: Application to Escherichia coli Core Metabolism. Processes (Basel) 2020. [DOI: 10.3390/pr8121649] [Citation(s) in RCA: 4] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 01/05/2023] Open
Abstract
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.
Collapse
|
6
|
Guil F, Hidalgo JF, García JM. Flux Coupling and the Objective Functions' Length in EFMs. Metabolites 2020; 10:E489. [PMID: 33260526 PMCID: PMC7759806 DOI: 10.3390/metabo10120489] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/02/2020] [Revised: 11/18/2020] [Accepted: 11/24/2020] [Indexed: 11/24/2022] Open
Abstract
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.
Collapse
Affiliation(s)
| | - José F. Hidalgo
- Grupo de Arquitectura y Computación Paralela, Universidad de Murcia, 30080 Murcia, Spain; (F.G.); (J.M.G.)
| | | |
Collapse
|
7
|
Guil F, Hidalgo JF, García JM. Boosting the extraction of elementary flux modes in genome-scale metabolic networks using the linear programming approach. Bioinformatics 2020; 36:4163-4170. [PMID: 32348455 PMCID: PMC7390993 DOI: 10.1093/bioinformatics/btaa280] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/19/2019] [Revised: 04/16/2020] [Accepted: 04/22/2020] [Indexed: 11/14/2022] Open
Abstract
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.
Collapse
Affiliation(s)
- Francisco Guil
- Departamento de Ingeniería y Tecnología de Computadores, Universidad de Murcia, Murcia 30080, Spain
| | - José F Hidalgo
- Departamento de Ingeniería y Tecnología de Computadores, Universidad de Murcia, Murcia 30080, Spain
| | - José M García
- Departamento de Ingeniería y Tecnología de Computadores, Universidad de Murcia, Murcia 30080, Spain
| |
Collapse
|
8
|
Ullah E, Yosafshahi M, Hassoun S. Towards scaling elementary flux mode computation. Brief Bioinform 2019; 21:1875-1885. [PMID: 31745550 DOI: 10.1093/bib/bbz094] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/04/2019] [Revised: 07/04/2019] [Accepted: 07/05/2019] [Indexed: 01/05/2023] Open
Abstract
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.
Collapse
Affiliation(s)
- Ehsan Ullah
- Qatar Computing Research Institute, Hamad Bin Khalifa University, Doha, Qatar
| | - Mona Yosafshahi
- Qatar Computing Research Institute, Hamad Bin Khalifa University, Doha, Qatar
| | - Soha Hassoun
- Department of Computer Science, Tufts University, Medford MA 02155, USA
| |
Collapse
|
9
|
Bhadra S, Blomberg P, Castillo S, Rousu J. Principal metabolic flux mode analysis. Bioinformatics 2019; 34:2409-2417. [PMID: 29420676 PMCID: PMC6041797 DOI: 10.1093/bioinformatics/bty049] [Citation(s) in RCA: 9] [Impact Index Per Article: 1.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/07/2017] [Accepted: 02/06/2018] [Indexed: 01/01/2023] Open
Abstract
Motivation In the analysis of metabolism, two distinct and complementary approaches are frequently used: Principal component analysis (PCA) and stoichiometric flux analysis. PCA is able to capture the main modes of variability in a set of experiments and does not make many prior assumptions about the data, but does not inherently take into account the flux mode structure of metabolism. Stoichiometric flux analysis methods, such as Flux Balance Analysis (FBA) and Elementary Mode Analysis, on the other hand, are able to capture the metabolic flux modes, however, they are primarily designed for the analysis of single samples at a time, and not best suited for exploratory analysis on a large sets of samples. Results We propose a new methodology for the analysis of metabolism, called Principal Metabolic Flux Mode Analysis (PMFA), which marries the PCA and stoichiometric flux analysis approaches in an elegant regularized optimization framework. In short, the method incorporates a variance maximization objective form PCA coupled with a stoichiometric regularizer, which penalizes projections that are far from any flux modes of the network. For interpretability, we also introduce a sparse variant of PMFA that favours flux modes that contain a small number of reactions. Our experiments demonstrate the versatility and capabilities of our methodology. The proposed method can be applied to genome-scale metabolic network in efficient way as PMFA does not enumerate elementary modes. In addition, the method is more robust on out-of-steady steady-state experimental data than competing flux mode analysis approaches. Availability and implementation Matlab software for PMFA and SPMFA and dataset used for experiments are available in https://github.com/aalto-ics-kepaco/PMFA. Supplementary information Supplementary data are available at Bioinformatics online.
Collapse
Affiliation(s)
- Sahely Bhadra
- Helsinki Institute for Information Technology HIIT, Department of Computer Science, Aalto University, Espoo, Finland.,Computer Science and Engineering, Indian Institute of Technology, Palakkad, India
| | - Peter Blomberg
- VTT Technical Research Centre of Finland Ltd, Espoo, Finland
| | - Sandra Castillo
- VTT Technical Research Centre of Finland Ltd, Espoo, Finland
| | - Juho Rousu
- Helsinki Institute for Information Technology HIIT, Department of Computer Science, Aalto University, Espoo, Finland
| |
Collapse
|
10
|
Röhl A, Bockmayr A. Finding MEMo: minimum sets of elementary flux modes. J Math Biol 2019; 79:1749-1777. [PMID: 31388689 DOI: 10.1007/s00285-019-01409-5] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/18/2018] [Revised: 07/15/2019] [Indexed: 10/26/2022]
Abstract
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.
Collapse
Affiliation(s)
- Annika Röhl
- Department of Mathematics and Computer Science, Freie Universität Berlin, Arnimallee 6, 14195, Berlin, Germany.
| | - Alexander Bockmayr
- Department of Mathematics and Computer Science, Freie Universität Berlin, Arnimallee 6, 14195, Berlin, Germany
| |
Collapse
|
11
|
Dynamic metabolic network modeling of mammalian Chinese hamster ovary (CHO) cell cultures with continuous phase kinetics transitions. Biochem Eng J 2019. [DOI: 10.1016/j.bej.2018.11.015] [Citation(s) in RCA: 8] [Impact Index Per Article: 1.6] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/23/2022]
|
12
|
Hidalgo JF, Egea JA, Guil F, García JM. Improving the EFMs quality by augmenting their representativeness in LP methods. BMC SYSTEMS BIOLOGY 2018; 12:101. [PMID: 30458791 PMCID: PMC6245596 DOI: 10.1186/s12918-018-0619-1] [Citation(s) in RCA: 5] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Indexed: 01/09/2023]
Abstract
Background Although cellular metabolism has been widely studied, its fully comprehension is still a challenge. A main tool for this study is the analysis of meaningful pieces of knowledge called modes and, in particular, specially interesting classes of modes such as pathways and Elementary Flux Modes (EFMs). Its study often has to deal with issues such as the appearance of infeasibilities or the difficulty of finding representative enough sets of modes that are free of repetitions. Mode extraction methods usually incorporate strategies devoted to mitigate this phenomena but they still get a high ratio of repetitions in the set of solutions. Results This paper presents a proposal to improve the representativeness of the full set of metabolic reactions in the set of computed modes by penalizing the eventual high frequency of occurrence of some reactions during the extraction. This strategy can be applied to any linear programming based extraction existent method. Conclusions Our strategy enhances the quality of a set of extracted EFMs favouring the presence of every reaction in it and improving the efficiency by mitigating the occurrence of repeated solutions. The new proposed strategy can complement other EFMs extraction methods based on linear programming. The obtained solutions are more likely to be diverse using less computing effort and improving the efficiency of the extraction.
Collapse
Affiliation(s)
- José F Hidalgo
- Grupo de Arquitectura y Computación Paralela, Universidad de Murcia, Murcia, Spain.
| | - Jose A Egea
- Dpto. de Matemática Aplicada y Estadística Universidad Politécnica de Cartagena, Cartagena, Spain
| | - Francisco Guil
- Grupo de Arquitectura y Computación Paralela, Universidad de Murcia, Murcia, Spain
| | - José M García
- Grupo de Arquitectura y Computación Paralela, Universidad de Murcia, Murcia, Spain
| |
Collapse
|
13
|
Song HS, Goldberg N, Mahajan A, Ramkrishna D. Sequential computation of elementary modes and minimal cut sets in genome-scale metabolic networks using alternate integer linear programming. Bioinformatics 2018; 33:2345-2353. [PMID: 28369193 DOI: 10.1093/bioinformatics/btx171] [Citation(s) in RCA: 23] [Impact Index Per Article: 3.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/05/2016] [Accepted: 03/23/2017] [Indexed: 01/22/2023] Open
Abstract
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.
Collapse
Affiliation(s)
- Hyun-Seob Song
- Biological Sciences Division, Pacific Northwest National Laboratory, Richland, WA 99352, USA
| | - Noam Goldberg
- Department of Management, Bar-Ilan University, Ramat Gan 52900, Israel
| | - Ashutosh Mahajan
- Industrial Engineering and Operations Research, IIT Bombay, Powai, Mumbai 400076, India
| | | |
Collapse
|
14
|
Klamt S, Regensburger G, Gerstl MP, Jungreuthmayer C, Schuster S, Mahadevan R, Zanghellini J, Müller S. From elementary flux modes to elementary flux vectors: Metabolic pathway analysis with arbitrary linear flux constraints. PLoS Comput Biol 2017; 13:e1005409. [PMID: 28406903 PMCID: PMC5390976 DOI: 10.1371/journal.pcbi.1005409] [Citation(s) in RCA: 37] [Impact Index Per Article: 5.3] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 01/05/2023] Open
Abstract
Elementary flux modes (EFMs) emerged as a formal concept to describe metabolic pathways and have become an established tool for constraint-based modeling and metabolic network analysis. EFMs are characteristic (support-minimal) vectors of the flux cone that contains all feasible steady-state flux vectors of a given metabolic network. EFMs account for (homogeneous) linear constraints arising from reaction irreversibilities and the assumption of steady state; however, other (inhomogeneous) linear constraints, such as minimal and maximal reaction rates frequently used by other constraint-based techniques (such as flux balance analysis [FBA]), cannot be directly integrated. These additional constraints further restrict the space of feasible flux vectors and turn the flux cone into a general flux polyhedron in which the concept of EFMs is not directly applicable anymore. For this reason, there has been a conceptual gap between EFM-based (pathway) analysis methods and linear optimization (FBA) techniques, as they operate on different geometric objects. One approach to overcome these limitations was proposed ten years ago and is based on the concept of elementary flux vectors (EFVs). Only recently has the community started to recognize the potential of EFVs for metabolic network analysis. In fact, EFVs exactly represent the conceptual development required to generalize the idea of EFMs from flux cones to flux polyhedra. This work aims to present a concise theoretical and practical introduction to EFVs that is accessible to a broad audience. We highlight the close relationship between EFMs and EFVs and demonstrate that almost all applications of EFMs (in flux cones) are possible for EFVs (in flux polyhedra) as well. In fact, certain properties can only be studied with EFVs. Thus, we conclude that EFVs provide a powerful and unifying framework for constraint-based modeling of metabolic networks.
Collapse
Affiliation(s)
- Steffen Klamt
- Max Planck Institute for Dynamics of Complex Technical Systems, Magdeburg, Germany
| | - Georg Regensburger
- Institute for Algebra, Johannes Kepler University Linz (JKU), Linz, Austria
| | - Matthias P. Gerstl
- Department of Biotechnology, University of Natural Resources and Life Sciences, Vienna, Austria
- Austrian Centre of Biotechnology, Vienna, Austria
| | - Christian Jungreuthmayer
- Austrian Centre of Biotechnology, Vienna, Austria
- TGM - Technologisches Gewerbemuseum, Vienna, Austria
| | - Stefan Schuster
- Department of Bioinformatics, Faculty of Biology and Pharmacy, Friedrich Schiller University Jena, Jena, Germany
| | - Radhakrishnan Mahadevan
- Department of Chemical Engineering & Applied Chemistry, Institute of Biomaterials and Biomedical Engineering, University of Toronto, Toronto, Ontario, Canada
| | - Jürgen Zanghellini
- Department of Biotechnology, University of Natural Resources and Life Sciences, Vienna, Austria
- Austrian Centre of Biotechnology, Vienna, Austria
| | - Stefan Müller
- Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Linz, Austria
| |
Collapse
|
15
|
Zanghellini J, Gerstl MP, Hanscho M, Nair G, Regensburger G, Müller S, Jungreuthmayer C. Toward Genome-Scale Metabolic Pathway Analysis. Ind Biotechnol (New Rochelle N Y) 2016. [DOI: 10.1002/9783527807796.ch3] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 01/04/2023] Open
Affiliation(s)
- Jürgen Zanghellini
- Department of Biotechnology; University of Natural Resources and Life Sciences; Vienna, Muthgasse 18 A1190 Vienna Austria EU
- Austrian Centre of Industrial Biotechnology (ACIB); Muthgasse 11 A1190 Vienna Austria EU
| | - Matthias P. Gerstl
- Austrian Centre of Industrial Biotechnology (ACIB); Muthgasse 11 A1190 Vienna Austria EU
| | - Michael Hanscho
- Austrian Centre of Industrial Biotechnology (ACIB); Muthgasse 11 A1190 Vienna Austria EU
| | - Govind Nair
- Department of Biotechnology; University of Natural Resources and Life Sciences; Vienna, Muthgasse 18 A1190 Vienna Austria EU
- Austrian Centre of Industrial Biotechnology (ACIB); Muthgasse 11 A1190 Vienna Austria EU
| | - Georg Regensburger
- Institute for Algebra; Johannes Kepler University Linz; Altenberger Straβe 69 A-4040 Linz Austria EU
| | - Stefan Müller
- Johann Radon Institute for Computational and Applied Mathematics; Austrian Academy of Sciences; Altenberger Straβe 69 A-4040 Linz Austria EU
| | - Christian Jungreuthmayer
- Austrian Centre of Industrial Biotechnology (ACIB); Muthgasse 11 A1190 Vienna Austria EU
- TGM - Technologisches Gewerbemuseum; Wexstraβe 19-23 A1200 Vienna Austria EU
| |
Collapse
|
16
|
Gerstl MP, Jungreuthmayer C, Müller S, Zanghellini J. Which sets of elementary flux modes form thermodynamically feasible flux distributions? FEBS J 2016; 283:1782-94. [PMID: 26940826 PMCID: PMC4949704 DOI: 10.1111/febs.13702] [Citation(s) in RCA: 11] [Impact Index Per Article: 1.4] [Reference Citation Analysis] [Abstract] [Key Words] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/06/2015] [Revised: 12/24/2015] [Accepted: 02/29/2016] [Indexed: 01/10/2023]
Abstract
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.
Collapse
Affiliation(s)
- Matthias P Gerstl
- Department of Biotechnology, University of Natural Resources and Life Sciences, Vienna, Austria.,Austrian Centre of Industrial Biotechnology, Vienna, Austria
| | - Christian Jungreuthmayer
- Department of Biotechnology, University of Natural Resources and Life Sciences, Vienna, Austria.,Austrian Centre of Industrial Biotechnology, Vienna, Austria
| | - Stefan Müller
- Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Linz, Austria
| | - Jürgen Zanghellini
- Department of Biotechnology, University of Natural Resources and Life Sciences, Vienna, Austria.,Austrian Centre of Industrial Biotechnology, Vienna, Austria
| |
Collapse
|
17
|
Tobalina L, Pey J, Planes FJ. Direct calculation of minimal cut sets involving a specific reaction knock-out. Bioinformatics 2016; 32:2001-7. [PMID: 27153694 DOI: 10.1093/bioinformatics/btw072] [Citation(s) in RCA: 9] [Impact Index Per Article: 1.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/23/2015] [Accepted: 02/02/2016] [Indexed: 12/12/2022] Open
Abstract
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.
Collapse
Affiliation(s)
- Luis Tobalina
- CEIT and Tecnun, University of Navarra, San Sebastián 20018, Spain
| | - Jon Pey
- CEIT and Tecnun, University of Navarra, San Sebastián 20018, Spain
| | | |
Collapse
|
18
|
On the feasibility of growth-coupled product synthesis in microbial strains. Metab Eng 2015; 30:166-178. [PMID: 26112955 DOI: 10.1016/j.ymben.2015.05.006] [Citation(s) in RCA: 64] [Impact Index Per Article: 7.1] [Reference Citation Analysis] [Abstract] [Key Words] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/09/2014] [Revised: 03/11/2015] [Accepted: 05/08/2015] [Indexed: 11/22/2022]
Abstract
Enforcing obligate coupling of growth with synthesis of a desired product has become a key principle for metabolic engineering of microbial production strains. Various methods from stoichiometric and constraint-based modeling have been developed to calculate intervention strategies by which a given microorganism can only grow if it synthesizes a desired compound as a mandatory by-product. However, growth-coupled synthesis is not necessarily feasible for every compound of a metabolic network and no rigorous criterion is currently known to test feasibility of coupled product and biomass formation (before searching for suitable intervention strategies). In this work, we show which properties a network must fulfill such that strain designs guaranteeing coupled biomass and product synthesis can exist at all. In networks without flux bounds, coupling is feasible if and only if an elementary mode exists that leads to formation of both biomass and product. Setting flux boundaries leads to more complicated inhomogeneous problems. Making use of the concept of elementary (flux) vectors, a generalization of elementary modes, a criterion for feasibility can also be derived for this situation. We applied our criteria to a metabolic model of Escherichia coli and determined for each metabolite, whether its net production can be coupled with biomass synthesis and calculated the maximal (guaranteed) coupling yield. The somewhat surprising result is that, under aerobic conditions, coupling is indeed possible for each carbon metabolite of the central metabolism. This also holds true for most metabolites under anaerobic conditions but consideration of ATP maintenance requirements implies infeasibility of coupling for certain compounds. On the other hand, ATP maintenance may also increase the maximal coupling yield for some metabolites. Overall, our work provides important insights and novel tools for a central problem of computational strain design.
Collapse
|
19
|
Jungreuthmayer C, Ruckerbauer DE, Gerstl MP, Hanscho M, Zanghellini J. Avoiding the Enumeration of Infeasible Elementary Flux Modes by Including Transcriptional Regulatory Rules in the Enumeration Process Saves Computational Costs. PLoS One 2015; 10:e0129840. [PMID: 26091045 PMCID: PMC4475075 DOI: 10.1371/journal.pone.0129840] [Citation(s) in RCA: 14] [Impact Index Per Article: 1.6] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/04/2014] [Accepted: 05/13/2015] [Indexed: 01/12/2023] Open
Abstract
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.
Collapse
Affiliation(s)
- Christian Jungreuthmayer
- Austrian Centre of Industrial Biotechnology, Vienna, Austria, EU
- Department of Biotechnology, University of Natural Resources and Life Sciences, Vienna, Austria, EU
- * E-mail: (CJ); (JZ)
| | - David E. Ruckerbauer
- Austrian Centre of Industrial Biotechnology, Vienna, Austria, EU
- Department of Biotechnology, University of Natural Resources and Life Sciences, Vienna, Austria, EU
| | - Matthias P. Gerstl
- Austrian Centre of Industrial Biotechnology, Vienna, Austria, EU
- Department of Biotechnology, University of Natural Resources and Life Sciences, Vienna, Austria, EU
| | - Michael Hanscho
- Austrian Centre of Industrial Biotechnology, Vienna, Austria, EU
- Department of Biotechnology, University of Natural Resources and Life Sciences, Vienna, Austria, EU
| | - Jürgen Zanghellini
- Austrian Centre of Industrial Biotechnology, Vienna, Austria, EU
- Department of Biotechnology, University of Natural Resources and Life Sciences, Vienna, Austria, EU
- * E-mail: (CJ); (JZ)
| |
Collapse
|
20
|
Ruckerbauer DE, Jungreuthmayer C, Zanghellini J. Predicting genetic engineering targets with Elementary Flux Mode Analysis: a review of four current methods. N Biotechnol 2015; 32:534-46. [PMID: 25917465 DOI: 10.1016/j.nbt.2015.03.017] [Citation(s) in RCA: 7] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/06/2014] [Revised: 03/21/2015] [Accepted: 03/30/2015] [Indexed: 01/14/2023]
Abstract
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.
Collapse
Affiliation(s)
- David E Ruckerbauer
- Austrian Centre of Industrial Biotechnology, Muthgasse 11, A1190 Vienna, Austria; Department of Biotechnology, University of Natural Resources and Life Sciences, Vienna, Austria
| | - Christian Jungreuthmayer
- Austrian Centre of Industrial Biotechnology, Muthgasse 11, A1190 Vienna, Austria; Department of Biotechnology, University of Natural Resources and Life Sciences, Vienna, Austria
| | - Jürgen Zanghellini
- Austrian Centre of Industrial Biotechnology, Muthgasse 11, A1190 Vienna, Austria; Department of Biotechnology, University of Natural Resources and Life Sciences, Vienna, Austria.
| |
Collapse
|
21
|
Metabolomics integrated elementary flux mode analysis in large metabolic networks. Sci Rep 2015; 5:8930. [PMID: 25754258 PMCID: PMC4354105 DOI: 10.1038/srep08930] [Citation(s) in RCA: 45] [Impact Index Per Article: 5.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/27/2014] [Accepted: 02/11/2015] [Indexed: 12/01/2022] Open
Abstract
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.
Collapse
|
22
|
Pey J, Villar JA, Tobalina L, Rezola A, García JM, Beasley JE, Planes FJ. TreeEFM: calculating elementary flux modes using linear optimization in a tree-based algorithm. ACTA ACUST UNITED AC 2014; 31:897-904. [PMID: 25380956 DOI: 10.1093/bioinformatics/btu733] [Citation(s) in RCA: 25] [Impact Index Per Article: 2.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/14/2022]
Abstract
MOTIVATION Elementary flux modes (EFMs) analysis constitutes a fundamental tool in systems biology. However, the efficient calculation of EFMs in genome-scale metabolic networks (GSMNs) is still a challenge. We present a novel algorithm that uses a linear programming-based tree search and efficiently enumerates a subset of EFMs in GSMNs. RESULTS Our approach is compared with the EFMEvolver approach, demonstrating a significant improvement in computation time. We also validate the usefulness of our new approach by studying the acetate overflow metabolism in the Escherichia coli bacteria. To do so, we computed 1 million EFMs for each energetic amino acid and then analysed the relevance of each energetic amino acid based on gene/protein expression data and the obtained EFMs. We found good agreement between previous experiments and the conclusions reached using EFMs. Finally, we also analysed the performance of our approach when applied to large GSMNs. AVAILABILITY AND IMPLEMENTATION The stand-alone software TreeEFM is implemented in C++ and interacts with the open-source linear solver COIN-OR Linear program Solver (CLP).
Collapse
Affiliation(s)
- Jon Pey
- CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK
| | - Juan A Villar
- CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK
| | - Luis Tobalina
- CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK
| | - Alberto Rezola
- CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK
| | - José Manuel García
- CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK
| | - John E Beasley
- CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK
| | - Francisco J Planes
- CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK
| |
Collapse
|
23
|
Chan SHJ, Solem C, Jensen PR, Ji P. Estimating biological elementary flux modes that decompose a flux distribution by the minimal branching property. ACTA ACUST UNITED AC 2014; 30:3232-9. [PMID: 25100687 DOI: 10.1093/bioinformatics/btu529] [Citation(s) in RCA: 16] [Impact Index Per Article: 1.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 01/02/2023]
Abstract
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.
Collapse
Affiliation(s)
- Siu Hung Joshua Chan
- Systems Biotechnology and Biorefining, National Food Institute, Technical University of Denmark, 2800 Kgs. Lyngby, Denmark and Department of Industrial and Systems Engineering, The Hong Kong Polytechnic University, Hung Hom, Hong Kong
| | - Christian Solem
- Systems Biotechnology and Biorefining, National Food Institute, Technical University of Denmark, 2800 Kgs. Lyngby, Denmark and Department of Industrial and Systems Engineering, The Hong Kong Polytechnic University, Hung Hom, Hong Kong
| | - Peter Ruhdal Jensen
- Systems Biotechnology and Biorefining, National Food Institute, Technical University of Denmark, 2800 Kgs. Lyngby, Denmark and Department of Industrial and Systems Engineering, The Hong Kong Polytechnic University, Hung Hom, Hong Kong
| | - Ping Ji
- Systems Biotechnology and Biorefining, National Food Institute, Technical University of Denmark, 2800 Kgs. Lyngby, Denmark and Department of Industrial and Systems Engineering, The Hong Kong Polytechnic University, Hung Hom, Hong Kong
| |
Collapse
|