title: Computing minimal nutrient sets from metabolic networks via linear constraint solving.
abstract: 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.
authors.affiliation: Computer Science Laboratory, SRI International, Menlo Park, CA 94025, USA.
authors.forename: Steven
authors.initials: S
authors.lastname: Eker
authors.forename: Markus
authors.initials: M
authors.lastname: Krummenacker
authors.forename: Alexander G
authors.initials: AG
authors.lastname: Shearer
authors.forename: Ashish
authors.initials: A
authors.lastname: Tiwari
authors.forename: Ingrid M
authors.initials: IM
authors.lastname: Keseler
authors.forename: Carolyn
authors.initials: C
authors.lastname: Talcott
authors.forename: Peter D
authors.initials: PD
authors.lastname: Karp
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods; D003470:Culture Media; D048168:Escherichia coli K12 / Q000235:genetics / Q000254:growth & development / Q000378:metabolism; D029968:Escherichia coli Proteins / Q000378:metabolism; D023281:Genomics; D026901:Membrane Transport Proteins / Q000378:metabolism; D053858:Metabolic Networks and Pathways; D008954:Models, Biological
chemical_list: D003470:Culture Media; D029968:Escherichia coli Proteins; D026901:Membrane Transport Proteins
references.citation: J Biol Chem. 2009 Oct 23;284(43):29480-8
references.pmid: 19690172
references.citation: Appl Environ Microbiol. 2005 Feb;71(2):826-34
references.pmid: 15691937
references.citation: Trends Biochem Sci. 2003 May;28(5):250-8
references.pmid: 12765837
references.citation: Mol Syst Biol. 2007;3:121
references.pmid: 17593909
references.citation: BMC Microbiol. 2005 Mar 07;5:8
references.pmid: 15752426
references.citation: Nucleic Acids Res. 2011 Jan;39(Database issue):D583-90
references.pmid: 21097882
references.citation: Pac Symp Biocomput. 2001;:471-82
references.pmid: 11262965
references.citation: Appl Environ Microbiol. 2008 Aug;74(15):4889-97
references.pmid: 18515474
references.citation: Genome Res. 2001 Jul;11(7):1246-55
references.pmid: 11435407
references.citation: J Theor Biol. 2000 Apr 7;203(3):249-83
references.pmid: 10716908
references.citation: Bioinformatics. 2002 May;18(5):715-24
references.pmid: 12050068
references.citation: J Bacteriol. 2002 Aug;184(16):4582-93
references.pmid: 12142428
references.citation: Microbiol Mol Biol Rev. 2004 Dec;68(4):686-91
references.pmid: 15590780
references.citation: J Bacteriol. 2008 Apr;190(8):2790-803
references.pmid: 18192387
references.citation: BMC Bioinformatics. 2010 Jan 08;11:15
references.pmid: 20064214
references.citation: J Theor Biol. 2008 Jun 7;252(3):530-7
references.pmid: 18086477
references.citation: Brief Bioinform. 2010 Jan;11(1):40-79
references.pmid: 19955237