Identifying All Moiety Conservation Laws in Genome-Scale Metabolic Networks

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

• Publication year

  2014

• Venue

  PLoS ONE

• Publication date

  2014-07-02

• Fields of study

  Biology, Medicine, Computer Science

• Identifiers
  DOI 10.1371/journal.pone.0100750PMID 24988199PMCID 4079565
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Thermodynamics of biochemical networks and duality theorems.

  2013cited by this paper
• A community-driven global reconstruction of human metabolism

  2013influential reference
• Detecting structural invariants in biological reaction networks.

  2012cited by this paper
• A Scalable Algorithm to Explore the Gibbs Energy Landscape of Genome-Scale Metabolic Networks

  2012cited by this paper
• Petri Nets – A Mathematical Formalism to Analyze Chemical Reaction Networks

  2010cited by this paper
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms

  2009cited by this paper
• Identifying essential genes in Escherichia coli from a metabolic optimization principle

  2009cited by this paper
• Predicting gene essentiality using genome-scale in silico models.

  2008cited by this paper
• Detection of stoichiometric inconsistencies in biomolecular models

  2008cited by this paper
• Quantitative prediction of cellular metabolism with constraint-based models: the COBRA Toolbox v2.0

  2007cited by this paper
• A genome-scale metabolic reconstruction for Escherichia coli K-12 MG1655 that accounts for 1260 ORFs and thermodynamic information

  2007cited by this paper
• Estimating the size of the solution space of metabolic networks

  2007cited by this paper
• Estimation of the number of extreme pathways for metabolic networks

  2007cited by this paper
• Von Neumann’s expanding model on random graphs

  2007cited by this paper
• Efficient supervised learning in networks with binary synapses

  2007cited by this paper
• Conservation analysis of large biochemical networks

  2006cited by this paper
• Systematic analysis of conservation relations in Escherichia coli genome-scale metabolic network reveals novel growth media.

  2006cited by this paper
• Carathéodory bounds for integer cones

  2006cited by this paper
• Systems Biology: Properties of Reconstructed Networks

  2006cited by this paper
• Candidate Metabolic Network States in Human Mitochondria

  2005cited by this paper
• Elucidation and structural analysis of conserved pools for genome-scale metabolic reconstructions.

  2005cited by this paper
• Investigating metabolite essentiality through genome-scale analysis of Escherichia coli production capabilities

  2005cited by this paper
• Structural comparison of metabolic networks in selected single cell organisms

  2005cited by this paper
• Global organization of metabolic fluxes in the bacterium Escherichia coli

  2004cited by this paper
• Monte Carlo sampling can be used to determine the size and shape of the steady-state flux space.

  2004cited by this paper
• Uniform sampling of steady-state flux spaces: means to design experiments and to interpret enzymopathies.

  2004cited by this paper
• Conservation analysis in biochemical networks: computational issues for software writers.

  2004cited by this paper
• An expanded genome-scale model of Escherichia coli K-12 (iJR904 GSM/GPR)

  2003cited by this paper
• The convex basis of the left null space of the stoichiometric matrix leads to the definition of metabolically meaningful pools.

  2003influential reference
• Analysis of optimality in natural and perturbed metabolic networks

  2002cited by this paper
• Analytic and Algorithmic Solution of Random Satisfiability Problems

  2002cited by this paper
• The genome-scale metabolic extreme pathway structure in Haemophilus influenzae shows significant network redundancy.

  2002cited by this paper
• Monte Carlo simulation in statistical physics: an introduction

  2002cited by this paper
• Analysis of optimality in natural and perturbed metabolic networks

  2002cited by this paper
• Coloring random graphs

  2002cited by this paper
• Survey propagation: An algorithm for satisfiability

  2002cited by this paper
• On computing Hilbert bases via the Elliot-MacMahon algorithm

  2001cited by this paper
• Factor graphs and the sum-product algorithm

  2001cited by this paper
• The small world of metabolism

  2000cited by this paper
• The large-scale organization of metabolic networks

  2000cited by this paper
• Generalized Belief Propagation

  2000cited by this paper
• What Controls Glycolysis in Bloodstream Form Trypanosoma brucei?*

  1999cited by this paper
• Detection of elementary flux modes in biochemical networks: a promising tool for pathway analysis and metabolic engineering.

  1999cited by this paper
• The height of minimal Hilbert bases

  1997cited by this paper
• Introduction To Monte Carlo Algorithms

  1996cited by this paper
• The Regulation of Cellular Systems

  1996cited by this paper
• On Hilbert bases of polyhedral cones

  1996influential reference
• Information, physics, and computation

  1996cited by this paper
• What Information about the Conserved-Moiety Structure of Chemical Reaction Systems Can be Derived from Their Stoichiometry?

  1995influential reference
• An Efficient Incremental Algorithm for Solving Systems of Linear Diophantine Equations

  1994cited by this paper
• Buchberger Algorithm and Integer Programming

  1991influential reference
• Determining all extreme semi-positive conservation relations in chemical reaction systems: a test criterion for conservativity

  1991influential reference
• Learning algorithms with optimal stability in neural networks

  1987cited by this paper
• The null space problem I. complexity

  1986cited by this paper
• Theory of linear and integer programming

  1986cited by this paper
• A Computational Model for Causal and Diagnostic Reasoning in Inference Systems

  1983cited by this paper
• Reverend Bayes on Inference Engines: A Distributed Hierarchical Approach

  1982cited by this paper
• Combinatorial Optimization: Algorithms and Complexity

  1981cited by this paper

• Transitions and thermodynamics on species graphs of chemical reaction networks.

  2024cites this paper
• A UHPLC-QE-MS-based metabolomics approach for the evaluation of fermented lipase by an engineered Escherichia coli

  2024cites this paper
• Benchmarking methods for computing local sensitivities in ordinary differential equation models at dynamic and steady states

  2024cites this paper
• PCA-based synthetic sensitivity coefficients for chemical reaction network in cancer

  2024cites this paper
• Exploration of methods for computing sensitivities in ODE models at dynamic and steady states

  2024cites this paper
• In-silico modelling of the mitogen-activated protein kinase (MAPK) pathway in colorectal cancer: mutations and targeted therapy

  2023cites this paper
• Thermodynamic and stoichiometric laws ruling the fates of growing systems

  2023cites this paper
• In-silico modelling of the mitogen-activated kinase (MAPK) pathway in colorectal cancer: mutations and targeted therapy

  2023cites this paper
• What makes a reaction network “chemical”?

  2022cites this paper
• Efficient computation of adjoint sensitivities at steady-state in ODE models of biochemical reaction networks

  2022cites this paper
• A novel strategy for D-psicose and lipase co-production using a co-culture system of engineered Bacillus subtilis and Escherichia coli and bioprocess analysis using metabolomics

  2021cites this paper
• Quantifying the propagation of parametric uncertainty on flux balance analysis

  2021cites this paper
• Computational quantification of global effects induced by mutations and drugs in signaling networks of colorectal cancer cells

  2020cites this paper
• Gain and loss of function mutations in biological chemical reaction networks: a mathematical model with application to colorectal cancer cells

  2020cites this paper
• Simulating single-cell metabolism using a stochastic flux-balance analysis algorithm

  2020cites this paper
• Stock-flow consistent macroeconomic model with nonuniform distributional constraint

  2017cites this paper
• Phase transitions in integer linear problems

  2017cites this paper
• Identification of Conserved Moieties in Metabolic Networks by Graph Theoretical Analysis of Atom Transition Networks

  2016cites this paper
• The dual of the space of interactions in neural network models

  2015cites this paper