{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T07:53:26Z","timestamp":1761983606342,"version":"build-2065373602"},"reference-count":37,"publisher":"Oxford University Press (OUP)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015,3,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Elementary flux modes (EFMs) analysis constitutes a fundamental tool in systems biology. However, the efficient calculation of EFMs in genome-scale metabolic networks (GSMNs) is still a challenge. We present a novel algorithm that uses a linear programming-based tree search and efficiently enumerates a subset of EFMs in GSMNs.<\/jats:p>\n               <jats:p>Results: Our approach is compared with the EFMEvolver approach, demonstrating a significant improvement in computation time. We also validate the usefulness of our new approach by studying the acetate overflow metabolism in the Escherichia coli bacteria. To do so, we computed 1 million EFMs for each energetic amino acid and then analysed the relevance of each energetic amino acid based on gene\/protein expression data and the obtained EFMs. We found good agreement between previous experiments and the conclusions reached using EFMs. Finally, we also analysed the performance of our approach when applied to large GSMNs.<\/jats:p>\n               <jats:p>Availability and implementation: The stand-alone software TreeEFM is implemented in C++ and interacts with the open-source linear solver COIN-OR Linear program Solver (CLP).<\/jats:p>\n               <jats:p>Contact: fplanes@ceit.es<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu733","type":"journal-article","created":{"date-parts":[[2014,11,8]],"date-time":"2014-11-08T01:28:35Z","timestamp":1415410115000},"page":"897-904","source":"Crossref","is-referenced-by-count":16,"title":["TreeEFM: calculating elementary flux modes using linear optimization in a tree-based algorithm"],"prefix":"10.1093","volume":"31","author":[{"given":"Jon","family":"Pey","sequence":"first","affiliation":[{"name":"1 CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, 2Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and 3Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK"}]},{"given":"Juan A.","family":"Villar","sequence":"additional","affiliation":[{"name":"1 CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, 2Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and 3Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK"}]},{"given":"Luis","family":"Tobalina","sequence":"additional","affiliation":[{"name":"1 CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, 2Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and 3Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK"}]},{"given":"Alberto","family":"Rezola","sequence":"additional","affiliation":[{"name":"1 CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, 2Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and 3Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK"}]},{"given":"Jos\u00e9 Manuel","family":"Garc\u00eda","sequence":"additional","affiliation":[{"name":"1 CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, 2Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and 3Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK"}]},{"given":"John E.","family":"Beasley","sequence":"additional","affiliation":[{"name":"1 CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, 2Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and 3Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK"}]},{"given":"Francisco J.","family":"Planes","sequence":"additional","affiliation":[{"name":"1 CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, 2Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and 3Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK"}]}],"member":"286","published-online":{"date-parts":[[2014,11,6]]},"reference":[{"key":"2023020116191377300_btu733-B1","doi-asserted-by":"crossref","first-page":"183","DOI":"10.2140\/pjm.1955.5.183","article-title":"The generalized simplex method for minimizing a linear form under linear inequality restraints","volume":"5","author":"Dantzig","year":"1955","journal-title":"Pacific J. Math."},{"key":"2023020116191377300_btu733-B2","doi-asserted-by":"crossref","first-page":"2615","DOI":"10.1093\/bioinformatics\/btn500","article-title":"Can sugars be produced from fatty acids? A test case for pathway analysis tools","volume":"24","author":"De Figueiredo","year":"2008","journal-title":"Bioinformatics"},{"key":"2023020116191377300_btu733-B3","doi-asserted-by":"crossref","first-page":"3158","DOI":"10.1093\/bioinformatics\/btp564","article-title":"Computing the shortest elementary flux modes in genome-scale metabolic networks","volume":"25","author":"De Figueiredo","year":"2009","journal-title":"Bioinformatics"},{"key":"2023020116191377300_btu733-B4","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1038\/msb4100155","article-title":"A genome-scale metabolic reconstruction for Escherichia coli K-12 MG1655 that accounts for 1260 ORFs and thermodynamic information","volume":"3","author":"Feist","year":"2007","journal-title":"Mol. Syst. Biol."},{"key":"2023020116191377300_btu733-B5","doi-asserted-by":"crossref","first-page":"3192","DOI":"10.1111\/j.1742-4658.2012.08700.x","article-title":"Detecting and investigating substrate cycles in a genome - scale human metabolic network","volume":"279","author":"Gebauer","year":"2012","journal-title":"FEBS J."},{"key":"2023020116191377300_btu733-B6","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0168-1656(94)90131-7","article-title":"Amino acid utilization during batch and continuous cultures of Escherichia coli on a semi-synthetic medium","volume":"37","author":"Gschaedler","year":"1994","journal-title":"J. Biotechnol."},{"key":"2023020116191377300_btu733-B7","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/S0168-1656(01)00373-X","article-title":"Effect of glycine on the cell yield and growth rate of Escherichia coli: evidence for cell-density-dependent glycine degradation as determined by 13C NMR spectroscopy","volume":"92","author":"Han","year":"2002","journal-title":"J. Biotechnol."},{"key":"2023020116191377300_btu733-B8","doi-asserted-by":"crossref","first-page":"977","DOI":"10.1038\/nbt.1672","article-title":"High-throughput generation, optimization and analysis of genome-scale metabolic models","volume":"28","author":"Henry","year":"2010","journal-title":"Nat. Biotechnol."},{"key":"2023020116191377300_btu733-B9","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1016\/j.cell.2008.08.021","article-title":"Cancer cell metabolism: Warburg and beyond","volume":"134","author":"Hsu","year":"2008","journal-title":"Cell"},{"key":"2023020116191377300_btu733-B10","doi-asserted-by":"crossref","first-page":"1569","DOI":"10.1093\/bioinformatics\/btu021","article-title":"Complete enumeration of elementary flux modes through scalable, demand-based subnetwork definition","volume":"30","author":"Hunt","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020116191377300_btu733-B11","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1038\/nrm1857","article-title":"The model organism as a system: integrating \u2018omics\u2019 data sets","volume":"7","author":"Joyce","year":"2006","journal-title":"Nat. Rev. Mol. Cell Biol."},{"key":"2023020116191377300_btu733-B12","first-page":"179","article-title":"EFMEvolver: computing elementary flux modes in genome-scale metabolic networks","volume":"P-157","author":"Kaleta","year":"2009","journal-title":"Lect. Notes Inf."},{"key":"2023020116191377300_btu733-B13","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1023\/A:1020390132244","article-title":"Combinatorial complexity of pathway analysis in metabolic networks","volume":"29","author":"Klamt","year":"2002","journal-title":"Mol. Biol. Rep."},{"key":"2023020116191377300_btu733-B14","doi-asserted-by":"crossref","first-page":"497","DOI":"10.2307\/1910129","article-title":"An automatic method of solving discrete programming problems","volume":"28","author":"Land","year":"1960","journal-title":"Econometric Soc."},{"key":"2023020116191377300_btu733-B15","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1046\/j.1432-1327.1998.2550220.x","article-title":"Gene cloning, biochemical characterization and physiological role of a thermostable low-specificity L-threonine aldolase from Escherichia coli","volume":"255","author":"Liu","year":"1998","journal-title":"Eur. J. Biochem."},{"key":"2023020116191377300_btu733-B16","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1147\/rd.471.0057","article-title":"The common optimization interface for operations research: promoting open-source software in the operations research community","volume":"47","author":"Lougee-Heimer","year":"2003","journal-title":"IBM J. Res. Dev."},{"key":"2023020116191377300_btu733-B17","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/s002530051101","article-title":"Influence of acetic acid on the growth of Escherichia coli K12 during high-cell-density cultivation in a dialysis reactor","volume":"48","author":"Nakano","year":"1997","journal-title":"Appl. Microbiol. Biotechnol."},{"key":"2023020116191377300_btu733-B18","doi-asserted-by":"crossref","first-page":"2197","DOI":"10.1093\/bioinformatics\/btu193","article-title":"Direct calculation of Elementary Flux Modes satisfying several biological constraints in genome-scale metabolic networks","volume":"30","author":"Pey","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020116191377300_btu733-B19","doi-asserted-by":"crossref","first-page":"975","DOI":"10.1093\/bioinformatics\/btt653","article-title":"Refining carbon flux paths using atomic trace data","volume":"30","author":"Pey","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020116191377300_btu733-B20","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1186\/1752-0509-7-134","article-title":"Integrating gene and protein expression data with genome-scale metabolic networks to infer functional pathways","volume":"7","author":"Pey","year":"2013","journal-title":"BMC Syst. Biol."},{"key":"2023020116191377300_btu733-B21","doi-asserted-by":"crossref","first-page":"886","DOI":"10.1038\/nrmicro1023","article-title":"Genome-scale models of microbial cells: evaluating the consequences of constraints","volume":"2","author":"Price","year":"2004","journal-title":"Nat. Rev. Microbiol."},{"key":"2023020116191377300_btu733-B22","doi-asserted-by":"crossref","first-page":"534","DOI":"10.1093\/bioinformatics\/btq681","article-title":"Exploring metabolic pathways in genome-scale networks via generating flux modes","volume":"27","author":"Rezola","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020116191377300_btu733-B23","doi-asserted-by":"crossref","first-page":"2009","DOI":"10.1093\/bioinformatics\/btt328","article-title":"Selection of human tissue-specific elementary flux modes using gene expression data","volume":"29","author":"Rezola","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020116191377300_btu733-B24","article-title":"Advances in network-based metabolic pathway analysis and gene expression data integration","author":"Rezola","year":"2014","journal-title":"Brief. Bioinf."},{"key":"2023020116191377300_btu733-B25","doi-asserted-by":"crossref","first-page":"2900","DOI":"10.1093\/bioinformatics\/btt493","article-title":"GIM3E: condition-specific models of cellular metabolism developed from metabolomics and expression data","volume":"29","author":"Schmidt","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020116191377300_btu733-B26","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1038\/73786","article-title":"A general definition of metabolic pathways useful for systematic organization and analysis of complex metabolic networks","volume":"18","author":"Schuster","year":"2000","journal-title":"Nat. Biotech."},{"key":"2023020116191377300_btu733-B27","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/S0958-1669(00)00199-3","article-title":"Advances in Escherichia coli production of therapeutic proteins","volume":"12","author":"Swartz","year":"2001","journal-title":"Curr. Opin. Biotech."},{"key":"2023020116191377300_btu733-B28","doi-asserted-by":"crossref","first-page":"2229","DOI":"10.1093\/bioinformatics\/btn401","article-title":"Large-scale computation of elementary flux modes with bit pattern trees","volume":"24","author":"Terzer","year":"2008","journal-title":"Bioinformatics"},{"key":"2023020116191377300_btu733-B29","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1038\/nprot.2009.203","article-title":"A protocol for generating a high-quality genome-scale metabolic reconstruction","volume":"5","author":"Thiele","year":"2010","journal-title":"Nat. Protoc."},{"key":"2023020116191377300_btu733-B30","doi-asserted-by":"crossref","first-page":"e45635","DOI":"10.1371\/journal.pone.0045635","article-title":"Multiscale modeling of metabolism and macromolecular synthesis in E. coli and its application to the evolution of codon usage","volume":"7","author":"Thiele","year":"2012","journal-title":"PLoS One"},{"key":"2023020116191377300_btu733-B31","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1038\/nbt.2488","article-title":"A community-driven global reconstruction of human metabolism","volume":"31","author":"Thiele","year":"2013","journal-title":"Nat. Biotechnol."},{"key":"2023020116191377300_btu733-B32","doi-asserted-by":"crossref","first-page":"813","DOI":"10.1007\/s00253-008-1770-1","article-title":"Elementary mode analysis: a useful metabolic pathway analysis tool for characterizing cellular metabolism","volume":"81","author":"Trinh","year":"2009","journal-title":"Appl. Microbiol. Biotechnol."},{"key":"2023020116191377300_btu733-B33","doi-asserted-by":"crossref","first-page":"1203","DOI":"10.1093\/bioinformatics\/bti127","article-title":"An improved algorithm for stoichiometric network analysis: theory and applications","volume":"21","author":"Urbanczik","year":"2005","journal-title":"Bioinformatics"},{"key":"2023020116191377300_btu733-B34","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1186\/1752-0509-4-166","article-title":"Systems biology approach reveals that overflow metabolism of acetate in Escherichia coli is triggered by carbon catabolite repression of acetyl-CoA synthetase","volume":"4","author":"Valgepea","year":"2010","journal-title":"BMC Syst. Biol."},{"key":"2023020116191377300_btu733-B35","doi-asserted-by":"crossref","first-page":"3653","DOI":"10.1128\/AEM.72.5.3653-3661.2006","article-title":"Overflow metabolism in Escherichia coli during steady-state growth: transcriptional regulation and effect of the redox ratio","volume":"72","author":"Vemuri","year":"2006","journal-title":"Appl. Environ. Microbiol."},{"key":"2023020116191377300_btu733-B36","doi-asserted-by":"crossref","first-page":"1930","DOI":"10.1093\/bioinformatics\/btl267","article-title":"Metatool 5.0: fast and flexible elementary modes analysis","volume":"22","author":"Von Kamp","year":"2006","journal-title":"Bioinformatics"},{"key":"2023020116191377300_btu733-B37","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/j.copbio.2007.11.005","article-title":"Bioinformatics applications for pathway analysis of microarray data","volume":"19","author":"Werner","year":"2008","journal-title":"Curr. Opin. Biotech."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/6\/897\/49011241\/bioinformatics_31_6_897.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/6\/897\/49011241\/bioinformatics_31_6_897.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T00:32:11Z","timestamp":1675297931000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/31\/6\/897\/214785"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,6]]},"references-count":37,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2015,3,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu733","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"type":"electronic","value":"1367-4811"},{"type":"print","value":"1367-4803"}],"subject":[],"published-other":{"date-parts":[[2015,3,15]]},"published":{"date-parts":[[2014,11,6]]}}}