Identifying all irreducible conserved metabolite pools in genome-scale metabolic networks: a general method and the case of Escherichia coli

Abstract

The stoichiometry of metabolic networks usually gives rise to a family of conservation laws for the aggregate concentration of specific pools of metabolites, which not only constrain the dynamics of the network, but also provide key insight into a cell's production capabilities. When the conserved quantity identifies with a chemical moiety, extracting all such conservation laws from the stoichiometry amounts to finding all integer solutions to an NP-hard programming problem. Here we propose a novel and efficient computational strategy that combines Monte Carlo, message passing, and relaxation algorithms to compute the complete set of irreducible integer conservation laws of a given stoichiometric matrix, also providing a certificate for correctness and maximality of the solution. The method is deployed for the analysis of the complete set of irreducible integer pools of two large-scale reconstructions of the metabolism of the bacterium Escherichia coli in different growth media. In addition, we uncover a scaling relation that links the size of the irreducible pool basis to the number of metabolites, for which we present an analytical explanation.

10 pages, 4 tables, one figure

References in corpus (6)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Efficient supervised learning in networks with binary synapses
• Identifying essential genes in E. coli from a metabolic optimization principle
• A scalable algorithm to explore the Gibbs energy landscape of genome-scale metabolic networks
• On the Clausius formulation of the second law in stationary chemical networks through the theorems of the alternative
• Von Neumann's expanding model on random graphs