Computing minimal nutrient sets from metabolic networks via linear constraint solving

BMC Bioinformatics

Steven Eker²  Markus Krummenacker¹  Alexander G Shearer¹  Ashish Tiwari²  Ingrid M Keseler¹  Carolyn Talcott²  Peter D Karp¹ 

[1] Bioinformatics Research Group, SRI International, Menlo Park, CA 94025, USA

[2] Computer Science Laboratory, SRI International, Menlo Park, CA 94025, USA

关键词: Cellular metabolism;    Metabolic and regulatory networks;    SMT solvers;    Minimal nutrient sets;    Linear constraint solving;    Computational biology;    Binary decision diagrams;   

Others  :  1087921
DOI  :  10.1186/1471-2105-14-114

 received in 2012-07-25, accepted in 2012-12-18,  发布年份 2013

【 摘 要 】

Background

As more complete genome sequences become available, bioinformatics challenges arise in how to exploit genome sequences to make phenotypic predictions. One type of phenotypic prediction is to determine sets of compounds that will support the growth of a bacterium from the metabolic network inferred from the genome sequence of that organism.

Results

We present a method for computationally determining alternative growth media for an organism based on its metabolic network and transporter complement. Our method predicted 787 alternative anaerobic minimal nutrient sets for Escherichia coli K–12 MG1655 from the EcoCyc database. The program automatically partitioned the nutrients within these sets into 21 equivalence classes, most of which correspond to compounds serving as sources of carbon, nitrogen, phosphorous, and sulfur, or combinations of these essential elements. The nutrient sets were predicted with 72.5% accuracy as evaluated by comparison with 91 growth experiments. Novel aspects of our approach include (a) exhaustive consideration of all combinations of nutrients rather than assuming that all element sources can substitute for one another(an assumption that can be invalid in general) (b) leveraging the notion of a machinery-duplicating constraint, namely, that all intermediate metabolites used in active reactions must be produced in increasing concentrations to prevent successive dilution from cell division, (c) the use of Satisfiability Modulo Theory solvers rather than Linear Programming solvers, because our approach cannot be formulated as linear programming, (d) the use of Binary Decision Diagrams to produce an efficient implementation.

Conclusions

Our method for generating minimal nutrient sets from the metabolic network and transporters of an organism combines linear constraint solving with binary decision diagrams to efficiently produce solution sets to provided growth problems.

【 授权许可】

   
2013 Eker et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

【 参考文献 】

• [1]Schloss PD, Handelsman J: Status of the microbial census. Microbiol MolBiol Rev 2004, 68:686-691.
• [2]Davis KE, Joseph SJ, Janssen PH: Effects of growth medium, inoculum size, and incubation time on culturability and isolation of soil bacteria. Appl Environ Microbiol 2005, 71:826-834.
• [3]Dale JM, Popescu L, Karp PD: Machine learning methods for metabolic pathway prediction. BMC Bioinformatics 2010, 11:15. BioMed Central Full Text
• [4]Paley S, Karp PD: Evaluation of computational metabolic-pathway predictions for Helicobacter pylori. Bioinformatics 2002, 18:715-724.
• [5]Karp P, Paley S, Krummenacker M, Latendresse M: Pathway tools version 13.0: integrated software for pathway/genome informatics and systems biology. Brief Bioinform 2010, 11:40-79.
• [6]Romero P, Karp P: Nutrient-related analysis of pathway/genome databases. In Proc Pacific Symposium on Biocomputing. Edited by Altman R, Klein T. Singapore: World Scientific; 2001:471-482.
• [7]Raspail FV: Développement de la fécule dans les organes de la fructification des céréales, et analyse microscopique de la fécule, suivies d’expériences propres à en expliquer la conversion en gomme. Annales Des Sciences Naturelles 1825,., 6p.224 (part 1), p.384 (part 2)
• [8]Keseler IM, Collado-Vides J, Santos-Zavaleta A, Peralta-Gil M: EcoCyc: a Comprehensive Database of Escherichia coli Biology. Nuc Acids Res 2011, 39:D583-D590.
• [9]Nieuwenhuis R, Oliveras A, Tinelli C: Solving SAT and SAT modulo theories: From an abstract Davis–Putnam–Logemann–Loveland procedure to DPLL(T). J ACM 2006, 53:937-977.
• [10]Dutertre B, de Moura L: A fast linear-arithmetic solver for DPLL(T). In Computer-Aided Verification (CAV’2006). Volume 4144 of Lecture Notes in Computer Science. Berlin: Springer Verlag; 2006:81-94.
• [11]Gurvich V, Khachiyan L: On Generating the irredundant conjunctive and disjunctive normal forms of monotone boolean functions. Discrete Appl Math 1999, 96–97:363-373.
• [12]Bryant RE: Graph-based algorithms for boolean function manipulation. IEEE Trans Comput 1986, 35:677-691.
• [13]Bryant RE: Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Comput Surv 1992, 24:293-318.
• [14]BuDDy: A binary decision diagram package. http://vlsicad.eecs.umich.edu/BK/Slots/cache/www.itu.dk/research/buddy/index.html webcite
• [15]CUDD: CU Decision Diagram Package. http://vlsi.colorado.edu/∼fabio/CUDD/ webcite
• [16]Bochner BR, Gadzinski P, Panomitros E: Phenotype microarrays for high-throughput phenotypic testing and assay of gene function. Genome Res 2001, 11:1246-1255.
• [17]Nichols D: Short peptide induces an ‘Uncultivable’ microorganism to grow in vitro. Appl Env Microbiol 2008, 74:4889-4897.
• [18]Handorf T: An environmental perspective on metabolism. J Theor Biol 2008, 252:530-537.
• [19]Cottret L, Milreu P, Acuna V, Marchetti-Spaccamela A: Enumerating precursor sets of target metabolites in a metabolic network. Proc. WABI. volume 5251 of LNBI 2008, 233-244.
• [20]Papin JA: Metabolic pathways in the post-genome era. Trends Biochem Sci 2003, 28:250-258.
• [21]Feist A, Henry C, Reed J, Krummenacker M, Joyce A: A genome-scale metabolic reconstruction for Escherichia coli K–12 MG1655 that accounts for 1260 ORFs and thermodynamic information. Mol Syst Biol 2007, 3:121-138.
• [22]Yices: An SMT Solver. http://yices.csl.sri.com/ webcite
• [23]Z3: An Efficient SMT Solver. http://research.microsoft.com/projects/z3/ webcite
• [24]Audemard G: A SAT-based approach for solving formulas over boolean and linear mathematical propositions. In CADE. volume 2392 of LNCS. Berlin, Germany: Springer; 2002:195-210.
• [25]Nieuwenhuis R, Oliveras A: Decision procedures for SAT, SAT modulo theories and beyond. The BarcelogicTools. In Proc. 12th Intl. Conf. Logic for Prog., AI, and Reasoning, LPAR volume 3835 of LNCS.. Berlin, Germany: Springer; 2005:23-46.
• [26]AbuOun M: Genome-scale reconstruction of a salmonella metabolic model. J Biol Chem 2009, 284:29480-29488.
• [27]Oberhardt M: Genome-scale metabolic network analysis of the opportunistic pathogen Pseudomonas aeruginosa PAO1. J Bacteriol 2008, 190:2790-2803.
• [28]Becker S, Palsson B: Genome-scale reconstruction of the metabolic network in Staphylococcus aureus N315. BMC Microbiol 2005, 5:1-8. BioMed Central Full Text
• [29]Schilling C: Genome-scale metabolic model of Helicobacter pylori. J Bacteriol 2002, 184:4582-4593.
• [30]Schilling C, Palsson B: Assessment of the metabolic capabilities of Haemophilus influenzae Rd through a genome-scale pathway analysis. J Theor Biol 2000, 203:249-283.