{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T11:00:36Z","timestamp":1769166036044,"version":"3.49.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>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.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>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 <jats:italic>Escherichia coli<\/jats:italic> 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.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>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.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-14-114","type":"journal-article","created":{"date-parts":[[2013,3,27]],"date-time":"2013-03-27T23:13:53Z","timestamp":1364426033000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Computing minimal nutrient sets from metabolic networks via linear constraint solving"],"prefix":"10.1186","volume":"14","author":[{"given":"Steven","family":"Eker","sequence":"first","affiliation":[]},{"given":"Markus","family":"Krummenacker","sequence":"additional","affiliation":[]},{"given":"Alexander G","family":"Shearer","sequence":"additional","affiliation":[]},{"given":"Ashish","family":"Tiwari","sequence":"additional","affiliation":[]},{"given":"Ingrid M","family":"Keseler","sequence":"additional","affiliation":[]},{"given":"Carolyn","family":"Talcott","sequence":"additional","affiliation":[]},{"given":"Peter D","family":"Karp","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,3,27]]},"reference":[{"key":"5853_CR1","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1128\/MMBR.68.4.686-691.2004","volume":"68","author":"PD Schloss","year":"2004","unstructured":"Schloss PD, Handelsman J: Status of the microbial census. Microbiol MolBiol Rev. 2004, 68: 686-691. 10.1128\/MMBR.68.4.686-691.2004.","journal-title":"Microbiol MolBiol Rev"},{"key":"5853_CR2","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1128\/AEM.71.2.826-834.2005","volume":"71","author":"KE Davis","year":"2005","unstructured":"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. 10.1128\/AEM.71.2.826-834.2005.","journal-title":"Appl Environ Microbiol"},{"key":"5853_CR3","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1186\/1471-2105-11-15","volume":"11","author":"JM Dale","year":"2010","unstructured":"Dale JM, Popescu L, Karp PD: Machine learning methods for metabolic pathway prediction. BMC Bioinformatics. 2010, 11: 15-10.1186\/1471-2105-11-15.","journal-title":"BMC Bioinformatics"},{"key":"5853_CR4","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1093\/bioinformatics\/18.5.715","volume":"18","author":"S Paley","year":"2002","unstructured":"Paley S, Karp PD: Evaluation of computational metabolic-pathway predictions for Helicobacter pylori. Bioinformatics. 2002, 18: 715-724. 10.1093\/bioinformatics\/18.5.715.","journal-title":"Bioinformatics"},{"key":"5853_CR5","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1093\/bib\/bbp043","volume":"11","author":"P Karp","year":"2010","unstructured":"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. 10.1093\/bib\/bbp043.","journal-title":"Brief Bioinform"},{"key":"5853_CR6","first-page":"471","volume-title":"Proc Pacific Symposium on Biocomputing","author":"P Romero","year":"2001","unstructured":"Romero P, Karp P: Nutrient-related analysis of pathway\/genome databases. Proc Pacific Symposium on Biocomputing. Edited by: Altman R, Klein T. 2001, Singapore: World Scientific, 471-482."},{"key":"5853_CR7","volume-title":"Annales Des Sciences Naturelles","author":"FV Raspail","year":"1825,","unstructured":"Raspail FV: D\u00e9veloppement de la f\u00e9cule dans les organes de la fructification des c\u00e9r\u00e9ales, et analyse microscopique de la f\u00e9cule, suivies d\u2019exp\u00e9riences propres \u00e0 en expliquer la conversion en gomme. Annales Des Sciences Naturelles. 1825,, 6: p.224 (part 1), p.384 (part 2)"},{"key":"5853_CR8","doi-asserted-by":"publisher","first-page":"D583","DOI":"10.1093\/nar\/gkq1143","volume":"39","author":"IM Keseler","year":"2011","unstructured":"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. 10.1093\/nar\/gkq1143.","journal-title":"Nuc Acids Res"},{"key":"5853_CR9","doi-asserted-by":"publisher","first-page":"937","DOI":"10.1145\/1217856.1217859","volume":"53","author":"R Nieuwenhuis","year":"2006","unstructured":"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.1145\/1217856.1217859.","journal-title":"J ACM"},{"key":"5853_CR10","first-page":"81","volume-title":"Computer-Aided Verification (CAV\u20192006). Volume 4144 of Lecture Notes in Computer Science","author":"B Dutertre","year":"2006","unstructured":"Dutertre B, de Moura L: A fast linear-arithmetic solver for DPLL(T). Computer-Aided Verification (CAV\u20192006). Volume 4144 of Lecture Notes in Computer Science. 2006, Berlin: Springer Verlag, 81-94."},{"key":"5853_CR11","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/S0166-218X(99)00099-2","volume":"96-97","author":"V Gurvich","year":"1999","unstructured":"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.","journal-title":"Discrete Appl Math"},{"key":"5853_CR12","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"35","author":"RE Bryant","year":"1986","unstructured":"Bryant RE: Graph-based algorithms for boolean function manipulation. IEEE Trans Comput. 1986, 35: 677-691.","journal-title":"IEEE Trans Comput"},{"key":"5853_CR13","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1145\/136035.136043","volume":"24","author":"RE Bryant","year":"1992","unstructured":"Bryant RE: Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Comput Surv. 1992, 24: 293-318. 10.1145\/136035.136043.","journal-title":"ACM Comput Surv"},{"key":"5853_CR14","unstructured":"BuDDy: A binary decision diagram package. http:\/\/vlsicad.eecs.umich.edu\/BK\/Slots\/cache\/www.itu.dk\/research\/buddy\/index.html,"},{"key":"5853_CR15","unstructured":"CUDD: CU Decision Diagram Package. http:\/\/vlsi.colorado.edu\/\u00e2\u02c6\u00bcfabio\/CUDD\/,"},{"key":"5853_CR16","doi-asserted-by":"publisher","first-page":"1246","DOI":"10.1101\/gr.186501","volume":"11","author":"BR Bochner","year":"2001","unstructured":"Bochner BR, Gadzinski P, Panomitros E: Phenotype microarrays for high-throughput phenotypic testing and assay of gene function. Genome Res. 2001, 11: 1246-1255. 10.1101\/gr.186501.","journal-title":"Genome Res"},{"key":"5853_CR17","doi-asserted-by":"publisher","first-page":"4889","DOI":"10.1128\/AEM.00393-08","volume":"74","author":"D Nichols","year":"2008","unstructured":"Nichols D: Short peptide induces an \u2018Uncultivable\u2019 microorganism to grow in vitro. Appl Env Microbiol. 2008, 74: 4889-4897. 10.1128\/AEM.00393-08.","journal-title":"Appl Env Microbiol"},{"key":"5853_CR18","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1016\/j.jtbi.2007.10.036","volume":"252","author":"T Handorf","year":"2008","unstructured":"Handorf T: An environmental perspective on metabolism. J Theor Biol. 2008, 252: 530-537. 10.1016\/j.jtbi.2007.10.036.","journal-title":"J Theor Biol"},{"key":"5853_CR19","first-page":"233","volume-title":"Proc. WABI. volume 5251 of LNBI","author":"L Cottret","year":"2008","unstructured":"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."},{"key":"5853_CR20","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1016\/S0968-0004(03)00064-1","volume":"28","author":"JA Papin","year":"2003","unstructured":"Papin JA: Metabolic pathways in the post-genome era. Trends Biochem Sci. 2003, 28: 250-258. 10.1016\/S0968-0004(03)00064-1.","journal-title":"Trends Biochem Sci"},{"key":"5853_CR21","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1038\/msb4100155","volume":"3","author":"A Feist","year":"2007","unstructured":"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.","journal-title":"Mol Syst Biol"},{"key":"5853_CR22","unstructured":"Yices: An SMT Solver. http:\/\/yices.csl.sri.com\/,"},{"key":"5853_CR23","unstructured":"Z3: An Efficient SMT Solver. http:\/\/research.microsoft.com\/projects\/z3\/,"},{"key":"5853_CR24","first-page":"195","volume-title":"CADE. volume 2392 of LNCS","author":"G Audemard","year":"2002","unstructured":"Audemard G: A SAT-based approach for solving formulas over boolean and linear mathematical propositions. CADE. volume 2392 of LNCS. 2002, Berlin, Germany: Springer, 195-210."},{"key":"5853_CR25","first-page":"23","volume-title":"Proc. 12th Intl. Conf. Logic for Prog., AI, and Reasoning, LPAR volume 3835 of LNCS","author":"R Nieuwenhuis","year":"2005","unstructured":"Nieuwenhuis R, Oliveras A: Decision procedures for SAT, SAT modulo theories and beyond. The BarcelogicTools. Proc. 12th Intl. Conf. Logic for Prog., AI, and Reasoning, LPAR volume 3835 of LNCS. 2005, Berlin, Germany: Springer, 23-46."},{"key":"5853_CR26","doi-asserted-by":"publisher","first-page":"29480","DOI":"10.1074\/jbc.M109.005868","volume":"284","author":"M AbuOun","year":"2009","unstructured":"AbuOun M: Genome-scale reconstruction of a salmonella metabolic model. J Biol Chem. 2009, 284: 29480-29488. 10.1074\/jbc.M109.005868.","journal-title":"J Biol Chem"},{"key":"5853_CR27","doi-asserted-by":"publisher","first-page":"2790","DOI":"10.1128\/JB.01583-07","volume":"190","author":"M Oberhardt","year":"2008","unstructured":"Oberhardt M: Genome-scale metabolic network analysis of the opportunistic pathogen Pseudomonas aeruginosa PAO1. J Bacteriol. 2008, 190: 2790-2803. 10.1128\/JB.01583-07.","journal-title":"J Bacteriol"},{"key":"5853_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2180-5-8","volume":"5","author":"S Becker","year":"2005","unstructured":"Becker S, Palsson B: Genome-scale reconstruction of the metabolic network in Staphylococcus aureus N315. BMC Microbiol. 2005, 5: 1-8. 10.1186\/1471-2180-5-1.","journal-title":"BMC Microbiol"},{"key":"5853_CR29","doi-asserted-by":"publisher","first-page":"4582","DOI":"10.1128\/JB.184.16.4582-4593.2002","volume":"184","author":"C Schilling","year":"2002","unstructured":"Schilling C: Genome-scale metabolic model of Helicobacter pylori. J Bacteriol. 2002, 184: 4582-4593. 10.1128\/JB.184.16.4582-4593.2002.","journal-title":"J Bacteriol"},{"key":"5853_CR30","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1006\/jtbi.2000.1088","volume":"203","author":"C Schilling","year":"2000","unstructured":"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. 10.1006\/jtbi.2000.1088.","journal-title":"J Theor Biol"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-14-114.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T23:47:14Z","timestamp":1630540034000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-14-114"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,27]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["5853"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-14-114","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3,27]]},"assertion":[{"value":"25 July 2012","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 December 2012","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 March 2013","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"114"}}