{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T13:24:10Z","timestamp":1762521850328},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,2,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: A fundamental computational problem in the area of metabolic engineering is finding metabolic pathways between a pair of source and target metabolites efficiently. We present an approach, namely FogLight, for searching metabolic networks utilizing Boolean (AND-OR) operations represented in matrix notation to efficiently reduce the search space. This enables the enumeration of all pathways between metabolites that are too distant for the application of brute-force methods.<\/jats:p>\n               <jats:p>Results: Benchmarking tests run with FogLight show that it can reduce the search space by up to 98%, after which the accelerated search for high accurate results is guaranteed. Using FogLight, several pathways between eight given pairs of metabolites are found of which the pathways from CO2 to ethanol are specifically discussed. Additionally, in comparison with three path-finding tools, namely PHT, FMM and RouteSearch, FogLight can find shorter and more pathways for attempted source-target metabolite pairs.<\/jats:p>\n               <jats:p>Contact: \u00a0szamani@aut.ac.ir, gholamreza.bidkhori@vtt.fi<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv578","type":"journal-article","created":{"date-parts":[[2015,10,11]],"date-time":"2015-10-11T01:19:15Z","timestamp":1444526355000},"page":"398-408","source":"Crossref","is-referenced-by-count":14,"title":["FogLight: an efficient matrix-based approach to construct metabolic pathways by search space reduction"],"prefix":"10.1093","volume":"32","author":[{"given":"Mehrshad","family":"Khosraviani","sequence":"first","affiliation":[{"name":"1 Department of Computer Engineering & IT, Amirkabir University of Technology, Tehran, Iran and"}]},{"given":"Morteza","family":"Saheb Zamani","sequence":"additional","affiliation":[{"name":"1 Department of Computer Engineering & IT, Amirkabir University of Technology, Tehran, Iran and"}]},{"given":"Gholamreza","family":"Bidkhori","sequence":"additional","affiliation":[{"name":"1 Department of Computer Engineering & IT, Amirkabir University of Technology, Tehran, Iran and"}]}],"member":"286","published-online":{"date-parts":[[2015,10,10]]},"reference":[{"key":"2023020110304232000_btv578-B1","doi-asserted-by":"crossref","DOI":"10.1145\/2593069.2593158","article-title":"Majority-inverter graph: a novel data-structure and algorithms for efficient logic optimization","author":"Amar\u00fa","year":"2014"},{"key":"2023020110304232000_btv578-B2","article-title":"Optimal traversal of directed hypergraphs","volume-title":"Technical Report TR\u201392\u2013073","author":"Ausiello","year":"1992"},{"key":"2023020110304232000_btv578-B3","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0304-3975(83)90050-6","article-title":"Admissible heuristic search in AND\/OR graphs","volume":"24","author":"Bagchi","year":"1983","journal-title":"Theor. Comput. Sci."},{"key":"2023020110304232000_btv578-B4","doi-asserted-by":"crossref","first-page":"1668","DOI":"10.1126\/science.2047876","article-title":"Toward a science of metabolic engineering","volume":"252","author":"Bailey","year":"1991","journal-title":"Science"},{"key":"2023020110304232000_btv578-B5","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1093\/bioinformatics\/btl554","article-title":"Recovering metabolic pathways via optimization","volume":"23","author":"Beasley","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020110304232000_btv578-B6","doi-asserted-by":"crossref","first-page":"791","DOI":"10.1021\/bp0100880","article-title":"Minimal reaction sets for Escherichia coli metabolism under different growth requirements and uptake environments","volume":"17","author":"Burgard","year":"2001","journal-title":"Biotechnol. Prog."},{"key":"2023020110304232000_btv578-B7","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1016\/j.ymben.2014.07.009","article-title":"Generation of an atlas for commodity chemical production in Escherichia coli and a novel pathway prediction algorithm, GEM-Path","volume":"25","author":"Campodonico","year":"2014","journal-title":"Metab. Eng."},{"key":"2023020110304232000_btv578-B8","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1186\/1752-0509-6-10","article-title":"Enumerating metabolic pathways for the production of heterologous target chemicals in chassis organisms","volume":"6","author":"Carbonell","year":"2012","journal-title":"BMC Syst. Biol."},{"key":"2023020110304232000_btv578-B9","doi-asserted-by":"crossref","first-page":"D459","DOI":"10.1093\/nar\/gkt1103","article-title":"The MetaCyc database of metabolic pathways and enzymes and the BioCyc collection of Pathway\/Genome Databases","volume":"42","author":"Caspi","year":"2014","journal-title":"Nucleic Acids Res."},{"key":"2023020110304232000_btv578-B10","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1186\/1752-0509-4-35","article-title":"Prediction of novel synthetic pathways for the production of desired chemicals","volume":"4","author":"Cho","year":"2010","journal-title":"BMC Syst. Biol."},{"key":"2023020110304232000_btv578-B11","doi-asserted-by":"crossref","first-page":"W129","DOI":"10.1093\/nar\/gkp264","article-title":"FMM: a web server for metabolic pathway reconstruction and comparative analysis","volume":"37","author":"Chou","year":"2009","journal-title":"Nucleic Acids Res."},{"key":"2023020110304232000_btv578-B12","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/j.jmb.2005.09.079","article-title":"Inferring meaningful pathways in weighted metabolic networks","volume":"356","author":"Croes","year":"2006","journal-title":"J. Mol. Biol."},{"key":"2023020110304232000_btv578-B13","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1186\/1471-2105-11-15","article-title":"Machine learning methods for metabolic pathway prediction","volume":"11","author":"Dale","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023020110304232000_btv578-B14","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0263-7855(88)85004-5","article-title":"Predicting metabolic pathways by logic programming","volume":"6","author":"Darvas","year":"1988","journal-title":"J. Mol. Graphics"},{"key":"2023020110304232000_btv578-B15","article-title":"Logic optimization using rule-based randomized search","author":"F\u00e4rm","year":"2005"},{"key":"2023020110304232000_btv578-B16","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1016\/j.coche.2012.07.005","article-title":"Stoichiometric and energetic analyses of non-photosynthetic CO2-fixation pathways to support synthetic biology strategies for production of fuels and chemicals","volume":"1","author":"Fast","year":"2012","journal-title":"Curr. Opin. Chem. Eng."},{"key":"2023020110304232000_btv578-B17","doi-asserted-by":"crossref","first-page":"1704","DOI":"10.1016\/j.compbiomed.2013.08.017","article-title":"An evolutionary approach for searching metabolic pathways","volume":"43","author":"Gerard","year":"2013","journal-title":"Comput. Biol. Med."},{"key":"2023020110304232000_btv578-B18","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1049\/iet-syb:20060077","article-title":"Currency and commodity metabolites: their identification and relation to the modularity of metabolic networks","volume":"1","author":"Huss","year":"2007","journal-title":"IET Syst. Biol."},{"key":"2023020110304232000_btv578-B19","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1186\/1752-0509-8-28","article-title":"An efficient graph theory based method to identify every minimal reaction set in a metabolic network","volume":"8","author":"Jonnalagadda","year":"2014","journal-title":"BMC Syst. Biol."},{"key":"2023020110304232000_btv578-B20","doi-asserted-by":"crossref","first-page":"D199","DOI":"10.1093\/nar\/gkt1076","article-title":"Data, information, knowledge and principle: back to metabolism in KEGG","volume":"42","author":"Kanehisa","year":"2014","journal-title":"Nucleic Acids Res."},{"key":"2023020110304232000_btv578-B21","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1109\/64.294129","article-title":"Representing, analyzing, and synthesizing biochemical pathways","volume":"9","author":"Karp","year":"1994","journal-title":"IEEE Expert"},{"key":"2023020110304232000_btv578-B22","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1093\/bioinformatics\/16.9.825","article-title":"Pathway analysis in metabolic databases via differential metabolic display (DMD)","volume":"16","author":"Kuffner","year":"2000","journal-title":"Bioinformatics"},{"key":"2023020110304232000_btv578-B23","doi-asserted-by":"crossref","first-page":"2043","DOI":"10.1093\/bioinformatics\/btu150","article-title":"Optimal metabolic route search based on atom mappings","volume":"30","author":"Latendresse","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020110304232000_btv578-B24","article-title":"Designer organisms for photosynthetic production of ethanol from carbon dioxide and water","author":"Lee","year":"2011"},{"key":"2023020110304232000_btv578-B25","doi-asserted-by":"crossref","first-page":"S17","DOI":"10.1186\/1471-2105-13-S17-S17","article-title":"CMPF: class-switching minimized pathfinding in metabolic networks","volume":"13","author":"Lim","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023020110304232000_btv578-B26","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1093\/bioinformatics\/19.2.270","article-title":"Reconstruction of metabolic networks from genome data and analysis of their global structure for various organisms","volume":"19","author":"Ma","year":"2003","journal-title":"Bioinformatics"},{"key":"2023020110304232000_btv578-B27","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/j.jbiotec.2012.03.005","article-title":"Cyanobacterial biofuel production","volume":"162","author":"Machado","year":"2012","journal-title":"J. Biotechnol."},{"key":"2023020110304232000_btv578-B28","first-page":"325","article-title":"Identification of qualitatively feasible metabolic pathways","author":"Mavrovouniotis","year":"1993","journal-title":"Artif. Intell. Mol. Biol."},{"key":"2023020110304232000_btv578-B29","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":"2023020110304232000_btv578-B30","first-page":"784","article-title":"Hypergraph models of metabolism","volume":"8","author":"Pearcy","year":"2014","journal-title":"Int. J. Biol. Vet. Agric. Food Eng."},{"key":"2023020110304232000_btv578-B31","doi-asserted-by":"crossref","first-page":"R49","DOI":"10.1186\/gb-2011-12-5-r49","article-title":"Path finding methods accounting for stoichiometry in metabolic networks","volume":"12","author":"Pey","year":"2011","journal-title":"Genome Biol."},{"key":"2023020110304232000_btv578-B32","doi-asserted-by":"crossref","first-page":"2367","DOI":"10.1101\/gr.2872004","article-title":"OptStrain: a computational framework for redesign of microbial production systems","volume":"14","author":"Pharkya","year":"2004","journal-title":"Genome Res."},{"key":"2023020110304232000_btv578-B33","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":"2023020110304232000_btv578-B34","doi-asserted-by":"crossref","first-page":"2554","DOI":"10.1093\/bioinformatics\/btn471","article-title":"DESHARKY: automatic design of metabolic pathways for optimal cell growth","volume":"24","author":"Rodrigo","year":"2008","journal-title":"Bioinformatics"},{"key":"2023020110304232000_btv578-B35","volume-title":"Biochemical Pathways: An Atlas Of Biochemistry And Molecular Biology","author":"Schomburg","year":"2012"},{"key":"2023020110304232000_btv578-B36","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1142\/S0218339094000131","article-title":"On elementray flux modes in biochemical reaction systems at steady state","volume":"02","author":"Schuster","year":"1994","journal-title":"J. Biol. Syst."},{"key":"2023020110304232000_btv578-B37","doi-asserted-by":"crossref","first-page":"4757","DOI":"10.1007\/s00253-014-5600-3","article-title":"Metabolic engineering of Escherichia coli to enhance hydrogen production from glycerol","volume":"98","author":"Tran","year":"2014","journal-title":"Appl. Microbiol. Biotechnol."},{"key":"2023020110304232000_btv578-B38","first-page":"144","article-title":"An algorithm for identifying dominant-edge metabolic pathways","volume-title":"ICCAD","author":"Ullah","year":"2009"},{"key":"2023020110304232000_btv578-B39","doi-asserted-by":"crossref","first-page":"1803","DOI":"10.1098\/rspb.2001.1711","article-title":"The small world inside large metabolic networks","volume":"268","author":"Wagner","year":"2001","journal-title":"Proc. Biol. Sci. R. Soc."},{"key":"2023020110304232000_btv578-B40","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1016\/j.ymben.2011.01.006","article-title":"Probabilistic pathway construction","volume":"13","author":"Yousofshahi","year":"2011","journal-title":"Metab. Eng."},{"key":"2023020110304232000_btv578-B41","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1186\/1754-6834-6-57","article-title":"Metabolic engineering of Escherichia coli for high-specificity production of isoprenol and prenol as next generation of biofuels","volume":"6","author":"Zheng","year":"2013","journal-title":"Biotechnol. Biofuels"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/3\/398\/49016646\/bioinformatics_32_3_398.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/3\/398\/49016646\/bioinformatics_32_3_398.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T21:47:47Z","timestamp":1675288067000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/3\/398\/1743496"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,10]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,2,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv578","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2016,2,1]]},"published":{"date-parts":[[2015,10,10]]}}}