{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T05:12:57Z","timestamp":1790226777558,"version":"4.1.0"},"reference-count":27,"publisher":"Oxford University Press (OUP)","issue":"14","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,7,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: A key computational problem in metabolic engineering is finding efficient metabolic routes from a source to a target compound in genome-scale reaction networks, potentially considering the addition of new reactions. Efficiency can be based on many factors, such as route lengths, atoms conserved and the number of new reactions, and the new enzymes to catalyze them, added to the route. Fast algorithms are needed to systematically search these large genome-scale reaction networks.<\/jats:p>\n               <jats:p>Results: We present the algorithm used in the new RouteSearch tool within the Pathway Tools software. This algorithm is based on a general Branch-and-Bound search and involves constructing a network of atom mappings to facilitate efficient searching. As far as we know, it is the first published algorithm that finds guaranteed optimal routes where atom conservation is part of the optimality criteria. RouteSearch includes a graphical user interface that speeds user understanding of its search results. We evaluated the algorithm on five example metabolic-engineering problems from the literature; for one problem the published solution was equivalent to the optimal route found by RouteSearch; for the remaining four problems, RouteSearch found the published solution as one of its best-scored solutions. These problems were each solved in less than 5 s of computational time.<\/jats:p>\n               <jats:p>Availability and implementation: RouteSearch is accessible at BioCyc.org by using the menu command RouteSearch and by downloading Pathway Tools. Pathway Tools software is freely available to academic users, and for a fee to commercial users. Download from: http:\/\/biocyc.org\/download.shtml .<\/jats:p>\n               <jats:p>Contact: \u00a0mario.latendresse@sri.com<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu150","type":"journal-article","created":{"date-parts":[[2014,3,19]],"date-time":"2014-03-19T00:29:13Z","timestamp":1395188953000},"page":"2043-2050","source":"Crossref","is-referenced-by-count":51,"title":["Optimal metabolic route search based on atom mappings"],"prefix":"10.1093","volume":"30","author":[{"given":"Mario","family":"Latendresse","sequence":"first","affiliation":[{"name":"Bioinformatics Research Group\/Artificial Intelligence Center, SRI International, Menlo Park, CA 94025, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Markus","family":"Krummenacker","sequence":"additional","affiliation":[{"name":"Bioinformatics Research Group\/Artificial Intelligence Center, SRI International, Menlo Park, CA 94025, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter D.","family":"Karp","sequence":"additional","affiliation":[{"name":"Bioinformatics Research Group\/Artificial Intelligence Center, SRI International, Menlo Park, CA 94025, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2014,3,17]]},"reference":[{"key":"2023012711241944600_btu150-B1","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1038\/nature06450","article-title":"Non-fermentative pathways for synthesis of branched-chain higher alcohols as biofuels","volume":"451","author":"Atsumi","year":"2008","journal-title":"Nature"},{"key":"2023012711241944600_btu150-B2","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1007\/s00253-009-2085-6","article-title":"Engineering the isobutanol biosynthetic pathway in \n              Escherichia coli\n               by comparison of three aldehyde reductase\/alcohol dehydrogenase genes","volume":"85","author":"Atsumi","year":"2010","journal-title":"Appl. Microbiol. Biotechnol."},{"key":"2023012711241944600_btu150-B3","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","article-title":"On a routing problem","volume":"16","author":"Bellman","year":"1958","journal-title":"Q. App. Math."},{"key":"2023012711241944600_btu150-B4","doi-asserted-by":"crossref","first-page":"2108","DOI":"10.1093\/bioinformatics\/btn360","article-title":"MetaRoute: fast search for relevant metabolic routes for interactive network navigation and visualization","volume":"24","author":"Blum","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012711241944600_btu150-B5","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1089\/cmb.2008.0044","article-title":"Using atom mapping rules for an improved detection of relevant routes in weighted metabolic networks","volume":"15","author":"Blum","year":"2008","journal-title":"J. Comput. Biol."},{"key":"2023012711241944600_btu150-B6","doi-asserted-by":"crossref","first-page":"D742","DOI":"10.1093\/nar\/gkr1014","article-title":"The MetaCyc database of metabolic pathways and enzymes and the BioCyc collection of pathway\/genome databases","volume":"40","author":"Caspi","year":"2012","journal-title":"Nucleic Acids Res."},{"key":"2023012711241944600_btu150-B7","doi-asserted-by":"crossref","first-page":"5769","DOI":"10.1128\/AEM.00468-08","article-title":"Engineering of an \n              Escherichia coli\n               strain for the production of 3-methyl-1-butanol","volume":"74","author":"Connor","year":"2008","journal-title":"Appl. Environ. Microbiol."},{"key":"2023012711241944600_btu150-B8","doi-asserted-by":"crossref","first-page":"W326","DOI":"10.1093\/nar\/gki437","article-title":"Metabolic PathFinding: inferring relevant pathways in biochemical networks","volume":"33","author":"Croes","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023012711241944600_btu150-B9","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1137\/S0097539795290477","article-title":"Finding the \n              k\n               shortest paths","volume":"28","author":"Eppstein","year":"1998","journal-title":"SIAM J. Comput."},{"key":"2023012711241944600_btu150-B10","volume-title":"Network Flow Theory","author":"Ford","year":"1956"},{"key":"2023012711241944600_btu150-B11","doi-asserted-by":"crossref","first-page":"1548","DOI":"10.1093\/bioinformatics\/btq223","article-title":"Finding metabolic pathways using atom tracking","volume":"26","author":"Heath","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012711241944600_btu150-B12","volume-title":"Combinatorial Algorithms","author":"Hu","year":"1982"},{"key":"2023012711241944600_btu150-B13","doi-asserted-by":"crossref","first-page":"D109","DOI":"10.1093\/nar\/gkr988","article-title":"KEGG for integration and interpretation of large-scale molecular data sets","volume":"40","author":"Kanehisa","year":"2012","journal-title":"Nucleic Acids Res."},{"key":"2023012711241944600_btu150-B14","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1093\/bib\/bbp043","article-title":"Pathway Tools version 13.0: integrated software for pathway\/genome informatics and systems biology","volume":"11","author":"Karp","year":"2010","journal-title":"Brief. Bioinform."},{"key":"2023012711241944600_btu150-B15","doi-asserted-by":"crossref","first-page":"i135","DOI":"10.1093\/bioinformatics\/btt244","article-title":"Supervised de novo reconstruction of metabolic pathways from metabolome-scale compound sets","volume":"29","author":"Kotera","year":"2013","journal-title":"Bioinformatics"},{"key":"2023012711241944600_btu150-B16","doi-asserted-by":"crossref","first-page":"2970","DOI":"10.1021\/ci3002217","article-title":"Accurate atom-mapping computation for biochemical reactions","volume":"52","author":"Latendresse","year":"2012","journal-title":"J. Chem. Inf. Model."},{"key":"2023012711241944600_btu150-B17","doi-asserted-by":"crossref","first-page":"3409","DOI":"10.1007\/s00253-012-4618-7","article-title":"Biosynthesis of ethylene glycol in \n              Escherichia coli","volume":"97","author":"Liu","year":"2013","journal-title":"Appl. Microbiol. Biotechnol."},{"key":"2023012711241944600_btu150-B18","doi-asserted-by":"crossref","first-page":"1692","DOI":"10.1093\/bioinformatics\/btg217","article-title":"PathMiner: predicting metabolic pathways by heuristic search","volume":"19","author":"McShan","year":"2003","journal-title":"Bioinformatics"},{"key":"2023012711241944600_btu150-B19","doi-asserted-by":"crossref","first-page":"W138","DOI":"10.1093\/nar\/gkq318","article-title":"PathPred: an enzyme-catalyzed metabolic pathway prediction server","volume":"38","author":"Moriya","year":"2010","journal-title":"Nucleic Acids Res."},{"key":"2023012711241944600_btu150-B20","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1016\/j.copbio.2003.08.005","article-title":"Metabolic engineering for the microbial production of 1,3-propanediol","volume":"14","author":"Nakamura","year":"2003","journal-title":"Curr. Opin. Biotechnol."},{"key":"2023012711241944600_btu150-B21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1752-0509-3-103","article-title":"Inferring branching pathways in genome-scale metabolic networks","volume":"3","author":"Pitk\u00e4nen","year":"2009","journal-title":"BMC Syst. Biol."},{"key":"2023012711241944600_btu150-B22","doi-asserted-by":"crossref","first-page":"1189","DOI":"10.1093\/bioinformatics\/bti116","article-title":"Metabolic pathway analysis web service (Pathway Hunter tool at cubic)","volume":"21","author":"Rahman","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012711241944600_btu150-B23","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1016\/j.ymben.2011.02.002","article-title":"Optimization of a heterologous pathway for the production of flavonoids from glucose","volume":"13","author":"Santos","year":"2011","journal-title":"Metab. Eng."},{"key":"2023012711241944600_btu150-B24","doi-asserted-by":"crossref","first-page":"1287","DOI":"10.1007\/s10295-010-0907-2","article-title":"Use of the valine biosynthetic pathway to convert glucose into isobutanol","volume":"38","author":"Savrasova","year":"2011","journal-title":"J. Ind. Microbiol. Biotechnol."},{"key":"2023012711241944600_btu150-B25","doi-asserted-by":"crossref","first-page":"11055","DOI":"10.1074\/jbc.M008061200","article-title":"Fructose-6-phosphate aldolase is a novel class i aldolase from \n              Escherichia coli\n               and is related to a novel group of bacterial transaldolases","volume":"276","author":"Schurmann","year":"2001","journal-title":"J. Biol. Chem."},{"key":"2023012711241944600_btu150-B26","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1016\/j.ymben.2006.11.001","article-title":"Production of p-hydroxycinnamic acid from glucose in \n              Saccharomyces cerevisiae\n               and \n              Escherichia coli\n               by expression of heterologous genes from plants and fungi","volume":"9","author":"Vannelli","year":"2007","journal-title":"Metab. Eng."},{"key":"2023012711241944600_btu150-B27","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1111\/j.1365-313X.2011.04879.x","article-title":"A 2-oxoglutarate-dependent dioxygenase from \n              Ruta graveolens L.\n               exhibits p-coumaroyl CoA 2\u2032-hydroxylase activity (C2\u2019H): a missing step in the synthesis of umbelliferone in plants","volume":"70","author":"Vialart","year":"2012","journal-title":"Plant J."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/14\/2043\/48924590\/bioinformatics_30_14_2043.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/14\/2043\/48924590\/bioinformatics_30_14_2043.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T11:55:21Z","timestamp":1674820521000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/14\/2043\/2390321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,3,17]]},"references-count":27,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2014,7,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu150","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2014,7,15]]},"published":{"date-parts":[[2014,3,17]]}}}