{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T22:52:16Z","timestamp":1770331936443,"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 Syst Biol"],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>We consider the possibility of engineering metabolic pathways in a chassis organism in order to synthesize novel target compounds that are heterologous to the chassis. For this purpose, we model metabolic networks through hypergraphs where reactions are represented by hyperarcs. Each hyperarc represents an enzyme-catalyzed reaction that transforms set of substrates compounds into product compounds. We follow a retrosynthetic approach in order to search in the metabolic space (hypergraphs) for pathways (hyperpaths) linking the target compounds to a source set of compounds.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>To select the best pathways to engineer, we have developed an objective function that computes the cost of inserting a heterologous pathway in a given chassis organism. In order to find minimum-cost pathways, we propose in this paper two methods based on steady state analysis and network topology that are to the best of our knowledge, the first to enumerate all possible heterologous pathways linking a target compounds to a source set of compounds. In the context of metabolic engineering, the source set is composed of all naturally produced chassis compounds (endogenuous chassis metabolites) and the target set can be any compound of the chemical space. We also provide an algorithm for identifying precursors which can be supplied to the growth media in order to increase the number of ways to synthesize specific target compounds.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>We find the topological approach to be faster by several orders of magnitude than the steady state approach. Yet both methods are generally scalable in time with the number of pathways in the metabolic network. Therefore this work provides a powerful tool for pathway enumeration with direct application to biosynthetic pathway design.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1752-0509-6-10","type":"journal-article","created":{"date-parts":[[2012,2,7]],"date-time":"2012-02-07T15:14:30Z","timestamp":1328627670000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":56,"title":["Enumerating metabolic pathways for the production of heterologous target chemicals in chassis organisms"],"prefix":"10.1186","volume":"6","author":[{"given":"Pablo","family":"Carbonell","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Davide","family":"Fichera","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shashi B","family":"Pandit","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Loup","family":"Faulon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,2,6]]},"reference":[{"key":"847_CR1","doi-asserted-by":"publisher","first-page":"122+","DOI":"10.1186\/1752-0509-5-122","volume":"5","author":"P Carbonell","year":"2011","unstructured":"Carbonell P, Planson AG, Fichera D, Faulon JL: A retrosynthetic biology approach to metabolic pathway design for therapeutic production. BMC Systems Biology. 2011, 5: 122+-10.1186\/1752-0509-5-122.","journal-title":"BMC Systems Biology"},{"issue":"3","key":"847_CR2","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1002\/bit.24356","volume":"109","author":"AG Planson","year":"2011","unstructured":"Planson AG, Carbonell P, Paillard E, Pollet N, Faulon JL: Compound toxicity screening and structure-activity relationship modeling in Escherichia coli. Biotechnol Bioeng. 2011, 109 (3): 846-850.","journal-title":"Biotechnol Bioeng"},{"key":"847_CR3","first-page":"13","volume-title":"Metabolic Engineering, Marcel Dekker","author":"J Edwards","year":"1999","unstructured":"Edwards J, Ramakrishna R, Schilling C, Palsson B: Metabolic Engineering, Marcel Dekker. 1999, 13-57."},{"key":"847_CR4","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1142\/9789812772367_0006","volume":"3","author":"D Fell","year":"2007","unstructured":"Fell D: Metabolic Networks. Complex Systems and Interdisciplinary Science World Scientific. 2007, 3: 163-198.","journal-title":"Complex Systems and Interdisciplinary Science World Scientific"},{"key":"847_CR5","volume-title":"J Biomed Biotechnol","author":"F Llaneras","year":"2010","unstructured":"Llaneras F, Pic\u00f3 J: Which metabolic pathways generate and characterize the flux space? A comparison among elementary modes, extreme pathways and minimal generators. J Biomed Biotechnol. 2010, 2010:"},{"issue":"8","key":"847_CR6","doi-asserted-by":"publisher","first-page":"1739","DOI":"10.1093\/bioinformatics\/bti228","volume":"21","author":"SL Bell","year":"2005","unstructured":"Bell SL, Palsson B: expa: a program for calculating extreme pathways in biochemical reaction networks. Bioinformatics. 2005, 21 (8): 1739-1740. 10.1093\/bioinformatics\/bti228.","journal-title":"Bioinformatics"},{"issue":"19","key":"847_CR7","doi-asserted-by":"publisher","first-page":"2229","DOI":"10.1093\/bioinformatics\/btn401","volume":"24","author":"M Terzer","year":"2008","unstructured":"Terzer M, Stelling J: Large-scale computation of elementary flux modes with bit pattern trees. Bioinformatics. 2008, 24 (19): 2229-2235. 10.1093\/bioinformatics\/btn401.","journal-title":"Bioinformatics"},{"key":"847_CR8","first-page":"51","volume-title":"Contributions to the theory of games","author":"TS Motzkin","year":"1953","unstructured":"Motzkin TS, Raiffa H, Thompson GL, Thrall RM: The double description method. Contributions to the theory of games. 1953, Princenton, NJ: Princeton University Press, 2: 51-73."},{"issue":"11","key":"847_CR9","doi-asserted-by":"publisher","first-page":"2367","DOI":"10.1101\/gr.2872004","volume":"14","author":"P Pharkya","year":"2004","unstructured":"Pharkya P, Burgard AP, Maranas CD: OptStrain: A computational framework for redesign of microbial production systems. Genome Res. 2004, 14 (11): 2367-2376. 10.1101\/gr.2872004.","journal-title":"Genome Res"},{"issue":"23","key":"847_CR10","doi-asserted-by":"publisher","first-page":"3158","DOI":"10.1093\/bioinformatics\/btp564","volume":"25","author":"LF de Figueiredo","year":"2009","unstructured":"de Figueiredo LF, Podhorski A, Rubio A, Kaleta C, Beasley JE, Schuster S, Planes FJ: Computing the shortest elementary flux modes in genome-scale metabolic networks. Bioinformatics. 2009, 25 (23): 3158-3165. 10.1093\/bioinformatics\/btp564.","journal-title":"Bioinformatics"},{"issue":"5","key":"847_CR11","doi-asserted-by":"publisher","first-page":"R49+","DOI":"10.1186\/gb-2011-12-5-r49","volume":"12","author":"J Pey","year":"2011","unstructured":"Pey J, Prada J, Beasley J, Planes F: Path finding methods accounting for stoichiometry in metabolic networks. Genome Biol. 2011, 12 (5): R49+-","journal-title":"Genome Biol"},{"issue":"8","key":"847_CR12","doi-asserted-by":"publisher","first-page":"1603","DOI":"10.1093\/bioinformatics\/bti213","volume":"21","author":"V Hatzimanikatis","year":"2005","unstructured":"Hatzimanikatis V, Li C, Ionita JA, Henry CS, Jankowski MD, Broadbelt LJ: Exploring the diversity of complex metabolic networks. Bioinformatics. 2005, 21 (8): 1603-1609. 10.1093\/bioinformatics\/bti213.","journal-title":"Bioinformatics"},{"key":"847_CR13","doi-asserted-by":"publisher","first-page":"35+","DOI":"10.1186\/1752-0509-4-35","volume":"4","author":"A Cho","year":"2010","unstructured":"Cho A, Yun H, Park JHH, Lee SYY, Park S: Prediction of novel synthetic pathways for the production of desired chemicals. BMC Systems Biology. 2010, 4: 35+-10.1186\/1752-0509-4-35.","journal-title":"BMC Systems Biology"},{"issue":"suppl 2","key":"847_CR14","doi-asserted-by":"publisher","first-page":"W326","DOI":"10.1093\/nar\/gki437","volume":"33","author":"D Croes","year":"2005","unstructured":"Croes D, Couche F, Wodak SJ, van Helden J: Metabolic PathFinding: inferring relevant pathways in biochemical networks. Nucleic Acids Res. 2005, 33 (suppl 2): W326-W330.","journal-title":"Nucleic Acids Res"},{"key":"847_CR15","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1016\/j.jmb.2005.09.079","volume":"356","author":"D Croes","year":"2006","unstructured":"Croes D, Couche F, Wodak SJ, van Helden J: Inferring meaningful pathways in weighted metabolic networks. J Mol Biol. 2006, 356: 222-236. 10.1016\/j.jmb.2005.09.079.","journal-title":"J Mol Biol"},{"issue":"2","key":"847_CR16","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1016\/j.jmb.2009.03.006","volume":"388","author":"K Faust","year":"2009","unstructured":"Faust K, Croes D, van Helden J: Metabolic Pathfinding Using RPAIR Annotation. J Mol Biol. 2009, 388 (2): 390-414. 10.1016\/j.jmb.2009.03.006.","journal-title":"J Mol Biol"},{"issue":"7","key":"847_CR17","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1093\/bioinformatics\/bti116","volume":"21","author":"SA Rahman","year":"2005","unstructured":"Rahman SA, Advani P, Schunk R, Schrader R, Schomburg D: Metabolic pathway analysis web service (Pathway Hunter Tool at CUBIC). Bioinformatics. 2005, 21 (7): 1189-1193. 10.1093\/bioinformatics\/bti116.","journal-title":"Bioinformatics"},{"key":"847_CR18","first-page":"P062+","volume":"15","author":"M Kotera","year":"2004","unstructured":"Kotera M, Hattori M, Oh MA, Yamamoto R, Komeno T, Yabuzaki J, Tonomura K, Goto S, Kanehisa M: RPAIR: a reactant-pair database representing chemical changes in enzymatic reactions. Genome Informatics. 2004, 15: P062+-","journal-title":"Genome Informatics"},{"issue":"50","key":"847_CR19","doi-asserted-by":"publisher","first-page":"16487","DOI":"10.1021\/ja0466457","volume":"126","author":"M Kotera","year":"2004","unstructured":"Kotera M, Okuno Y, Hattori M, Goto S, Kanehisa M: Computational assignment of the EC numbers for genomic-scale analysis of enzymatic reactions. J Am Chem Soc. 2004, 126 (50): 16487-16498. 10.1021\/ja0466457.","journal-title":"J Am Chem Soc"},{"key":"847_CR20","first-page":"471","volume-title":"Pac Symp Biocomput","author":"P Romero","year":"2001","unstructured":"Romero P, Karp P: Nutrient-related analysis of pathway genome database. Pac Symp Biocomput. 2001, 471-482."},{"key":"847_CR21","first-page":"233","volume-title":"Lecture Notes in Bioinformatics, Volume LNBI 5251","author":"L Cottret","year":"2008","unstructured":"Cottret L, Milreu P, Acuna V, Marchetti-Spaccamela A, Viduani-Martinez F, Sagot M, Stougie L: Enumerating precursor sets of target metabolites in a metabolic network. Lecture Notes in Bioinformatics, Volume LNBI 5251. 2008, Springer-Verlag, 233-244."},{"issue":"6","key":"847_CR22","doi-asserted-by":"publisher","first-page":"1477","DOI":"10.1016\/j.cor.2003.11.014","volume":"32","author":"LR Nielsen","year":"2005","unstructured":"Nielsen LR, Andersen KA, Pretolani D: Finding the K shortest hyperpaths. Comput Oper Res. 2005, 32 (6): 1477-1497. 10.1016\/j.cor.2003.11.014.","journal-title":"Comput Oper Res"},{"key":"847_CR23","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0166-218X(93)90045-P","volume":"42","author":"G Gallo","year":"1993","unstructured":"Gallo G, Longo G, Nguyen S, Pallottino S: Directed Hypergraphs and Applications. Discrete Appl Math. 1993, 42: 177-201. 10.1016\/0166-218X(93)90045-P.","journal-title":"Discrete Appl Math"},{"issue":"4","key":"847_CR24","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1049\/ip-syb:20050035","volume":"152","author":"S Klamt","year":"2005","unstructured":"Klamt S, Gagneur J, von Kamp A: Algorithmic approaches for computing elementary modes in large biochemical reaction networks. IEE Proc Systems Biology. 2005, 152 (4): 249-255. 10.1049\/ip-syb:20050035.","journal-title":"IEE Proc Systems Biology"},{"key":"847_CR25","first-page":"502","volume-title":"Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW)","author":"D Jevremovic","year":"2011","unstructured":"Jevremovic D, Boley D, Sosa CP: Divide-and-Conquer Approach to the Parallel Computation of Elementary Flux Modes in Metabolic Networks. Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW). 2011, 502-511. IEEE International Symposium on, IEEE 2011"},{"key":"847_CR26","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1038\/73786","volume":"18","author":"S Schuster","year":"2000","unstructured":"Schuster S, Fell D, Dandekar T: A general definition of metabolic pathways useful for systematic organization and analysis of complex metabolic network. Nat Biotechnol. 2000, 18: 326-332. 10.1038\/73786.","journal-title":"Nat Biotechnol"},{"key":"847_CR27","doi-asserted-by":"publisher","first-page":"D355","DOI":"10.1093\/nar\/gkp896","volume":"38","author":"M Kanehisa","year":"2010","unstructured":"Kanehisa M, Goto S, Furumichi M, Tanabe M, Hirakawa M: KEGG for representation and analysis of molecular networks involving diseases and drugs. Nucleic Acids Res. 2010, 38: D355-D360. 10.1093\/nar\/gkp896.","journal-title":"Nucleic Acids Res"},{"key":"847_CR28","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.biosystems.2008.06.015","volume":"95","author":"V Acuna","year":"2009","unstructured":"Acuna V, Chierichetti F, Lacroix V, Marchetti-Spaccamela A, Sagot M, Stougie L: Modes and cuts in metabolic networks: Complexity and algorithms. BioSystems. 2009, 95: 51-60. 10.1016\/j.biosystems.2008.06.015.","journal-title":"BioSystems"},{"key":"847_CR29","doi-asserted-by":"publisher","first-page":"1477","DOI":"10.1016\/j.cor.2003.11.014","volume":"32","author":"L Nielsen","year":"2005","unstructured":"Nielsen L, Andersen K, Pretolani D: Finding theK shortest hyperpaths. Computers & Operations Research. 2005, 32: 1477-1497. 10.1016\/j.cor.2003.11.014.","journal-title":"Computers & Operations Research"},{"key":"847_CR30","volume-title":"Optimal traversal of directed hypergraphs","author":"G Ausiello","year":"1992","unstructured":"Ausiello G, Italiano G, Nanni U: Optimal traversal of directed hypergraphs. 1992, Berkeley, CA: International Computer Science Institute"}],"container-title":["BMC Systems Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1752-0509-6-10.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T18:43:21Z","timestamp":1630521801000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcsystbiol.biomedcentral.com\/articles\/10.1186\/1752-0509-6-10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,6]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["847"],"URL":"https:\/\/doi.org\/10.1186\/1752-0509-6-10","relation":{},"ISSN":["1752-0509"],"issn-type":[{"value":"1752-0509","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,6]]},"assertion":[{"value":"2 August 2011","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 February 2012","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 February 2012","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"10"}}