{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T18:36:11Z","timestamp":1723055771921},"reference-count":48,"publisher":"Oxford University Press (OUP)","issue":"23","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,12,1]]},"abstract":"Abstract<\/jats:title>\n Motivation: Elementary flux modes (EFMs) represent a key concept to analyze metabolic networks from a pathway-oriented perspective. In spite of considerable work in this field, the computation of the full set of elementary flux modes in large-scale metabolic networks still constitutes a challenging issue due to its underlying combinatorial complexity.<\/jats:p>\n Results: In this article, we illustrate that the full set of EFMs can be enumerated in increasing order of number of reactions via integer linear programming. In this light, we present a novel procedure to efficiently determine the K-shortest EFMs in large-scale metabolic networks. Our method was applied to find the K-shortest EFMs that produce lysine in the genome-scale metabolic networks of Escherichia coli and Corynebacterium glutamicum. A detailed analysis of the biological significance of the K-shortest EFMs was conducted, finding that glucose catabolism, ammonium assimilation, lysine anabolism and cofactor balancing were correctly predicted. The work presented here represents an important step forward in the analysis and computation of EFMs for large-scale metabolic networks, where traditional methods fail for networks of even moderate size.<\/jats:p>\n Contact: \u00a0fplanes@tecnun.es<\/jats:p>\n Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btp564","type":"journal-article","created":{"date-parts":[[2009,10,1]],"date-time":"2009-10-01T01:32:17Z","timestamp":1254360737000},"page":"3158-3165","source":"Crossref","is-referenced-by-count":160,"title":["Computing the shortest elementary flux modes in genome-scale metabolic networks"],"prefix":"10.1093","volume":"25","author":[{"given":"Luis F.","family":"de Figueiredo","sequence":"first","affiliation":[{"name":"1 Friedrich-Schiller-University Jena, 07743 Jena, Germany, 2 PhD Program in Computational Biology, Instituto Gulbenkian de Ci\u00eancia, 2780-156 Oeiras, Portugal, 3 CEIT and TECNUN, University of Navarra, 20016 San Sebasti\u00e1n, Spain and 4 Brunel University, Uxbridge, UB8 3PH, UK"},{"name":"1 Friedrich-Schiller-University Jena, 07743 Jena, Germany, 2 PhD Program in Computational Biology, Instituto Gulbenkian de Ci\u00eancia, 2780-156 Oeiras, Portugal, 3 CEIT and TECNUN, University of Navarra, 20016 San Sebasti\u00e1n, Spain and 4 Brunel University, Uxbridge, UB8 3PH, UK"}]},{"given":"Adam","family":"Podhorski","sequence":"additional","affiliation":[{"name":"1 Friedrich-Schiller-University Jena, 07743 Jena, Germany, 2 PhD Program in Computational Biology, Instituto Gulbenkian de Ci\u00eancia, 2780-156 Oeiras, Portugal, 3 CEIT and TECNUN, University of Navarra, 20016 San Sebasti\u00e1n, Spain and 4 Brunel University, Uxbridge, UB8 3PH, UK"}]},{"given":"Angel","family":"Rubio","sequence":"additional","affiliation":[{"name":"1 Friedrich-Schiller-University Jena, 07743 Jena, Germany, 2 PhD Program in Computational Biology, Instituto Gulbenkian de Ci\u00eancia, 2780-156 Oeiras, Portugal, 3 CEIT and TECNUN, University of Navarra, 20016 San Sebasti\u00e1n, Spain and 4 Brunel University, Uxbridge, UB8 3PH, UK"}]},{"given":"Christoph","family":"Kaleta","sequence":"additional","affiliation":[{"name":"1 Friedrich-Schiller-University Jena, 07743 Jena, Germany, 2 PhD Program in Computational Biology, Instituto Gulbenkian de Ci\u00eancia, 2780-156 Oeiras, Portugal, 3 CEIT and TECNUN, University of Navarra, 20016 San Sebasti\u00e1n, Spain and 4 Brunel University, Uxbridge, UB8 3PH, UK"}]},{"given":"John E.","family":"Beasley","sequence":"additional","affiliation":[{"name":"1 Friedrich-Schiller-University Jena, 07743 Jena, Germany, 2 PhD Program in Computational Biology, Instituto Gulbenkian de Ci\u00eancia, 2780-156 Oeiras, Portugal, 3 CEIT and TECNUN, University of Navarra, 20016 San Sebasti\u00e1n, Spain and 4 Brunel University, Uxbridge, UB8 3PH, UK"}]},{"given":"Stefan","family":"Schuster","sequence":"additional","affiliation":[{"name":"1 Friedrich-Schiller-University Jena, 07743 Jena, Germany, 2 PhD Program in Computational Biology, Instituto Gulbenkian de Ci\u00eancia, 2780-156 Oeiras, Portugal, 3 CEIT and TECNUN, University of Navarra, 20016 San Sebasti\u00e1n, Spain and 4 Brunel University, Uxbridge, UB8 3PH, UK"}]},{"given":"Francisco J.","family":"Planes","sequence":"additional","affiliation":[{"name":"1 Friedrich-Schiller-University Jena, 07743 Jena, Germany, 2 PhD Program in Computational Biology, Instituto Gulbenkian de Ci\u00eancia, 2780-156 Oeiras, Portugal, 3 CEIT and TECNUN, University of Navarra, 20016 San Sebasti\u00e1n, Spain and 4 Brunel University, Uxbridge, UB8 3PH, UK"}]}],"member":"286","published-online":{"date-parts":[[2009,9,30]]},"reference":[{"key":"2023013112195693900_B1","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.biosystems.2008.06.015","article-title":"Modes and cuts in metabolic networks: complexity and algorithms","volume":"95","author":"Acu\u00f1a","year":"2009","journal-title":"Biosystems"},{"key":"2023013112195693900_B2","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":"2023013112195693900_B3","doi-asserted-by":"crossref","first-page":"1453","DOI":"10.1126\/science.277.5331.1453","article-title":"The complete genome sequence of Escherichia coli K-12","volume":"277","author":"Blattner","year":"1997","journal-title":"Science"},{"key":"2023013112195693900_B4","first-page":"429","article-title":"Biosynthesis of threonine, lysine, and methionine","volume-title":"Escherichia coli and Salmonella typhimurium\u2014Cellular and Molecular Biology.","author":"Cohen","year":"1987","edition":"1st"},{"key":"2023013112195693900_B5","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0303-2647(03)00067-4","article-title":"A method for classifying metabolites in topological pathway analyses based on minimization of pathway number","volume":"70","author":"Dandekar","year":"2003","journal-title":"Biosystems"},{"key":"2023013112195693900_B6","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1007\/978-3-642-59735-0_17","article-title":"Metabolic flux analysis of Corynebacterium glutamicum","volume-title":"Bioreaction Engineering, Modelling and Control.","author":"de Graaf","year":"2000"},{"key":"2023013112195693900_B7","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF00813746","article-title":"Biology of L-lysine overproduction by Corynebacterium glutamicum","volume":"6","author":"Eggeling","year":"1994","journal-title":"Amino Acids"},{"key":"2023013112195693900_B8","doi-asserted-by":"crossref","volume-title":"Handbook of Corynebacterium glutamicum.","author":"Eggeling","year":"2005","DOI":"10.1201\/9781420039696"},{"key":"2023013112195693900_B9","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":"2023013112195693900_B10","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1042\/bj3110035","article-title":"Physiological control of metabolic flux: The requirement for multisite modulation","volume":"311","author":"Fell","year":"1995","journal-title":"Biochem. J."},{"key":"2023013112195693900_B11","doi-asserted-by":"crossref","first-page":"46446","DOI":"10.1074\/jbc.M307968200","article-title":"A novel metabolic cycle catalyzes glucose oxidation and anaplerosis in hungry Escherichia coli","volume":"278","author":"Fischer","year":"2003","journal-title":"J. Biol. Chem."},{"key":"2023013112195693900_B12","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1186\/1471-2105-5-175","article-title":"Computation of elementary modes: a unifying framework and the new binary approach","volume":"5","author":"Gagneur","year":"2004","journal-title":"BMC Bioinformatics"},{"key":"2023013112195693900_B13","first-page":"182","article-title":"Metabolic analysis of Corynebacterium glutamicum during lactate and succinate productions under oxygen deprivation conditions","volume":"7","author":"Inui","year":"2004","journal-title":"J. Mol. Microbiol. Biotechnol."},{"key":"2023013112195693900_B14","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1111\/j.1432-1033.1993.tb18153.x","article-title":"A universal method for achieving increases in metabolite production","volume":"216","author":"Kacser","year":"1993","journal-title":"Eur. J. Biochem."},{"key":"2023013112195693900_B15","doi-asserted-by":"crossref","first-page":"1872","DOI":"10.1101\/gr.090639.108","article-title":"Can the whole be less than the sum of its parts? Pathway analysis in genome-scale metabolic networks using elementary flux patterns","volume":"19","author":"Kaleta","year":"2009","journal-title":"Genome Res."},{"key":"2023013112195693900_B16","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/S0168-1656(03)00154-8","article-title":"The complete Corynebacterium glutamicum ATCC 13032 genome sequence and its impact on the production of L-aspartate-derived amino acids and vitamins","volume":"104","author":"Kalinowski","year":"2003","journal-title":"J. Biotechnol."},{"key":"2023013112195693900_B17","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1002\/bit.22067","article-title":"In silicogenome-scale reconstruction and validation of the Corynebacterium glutamicum metabolic network","volume":"102","author":"Kjeldsen","year":"2009","journal-title":"Biotechnol. Bioeng."},{"key":"2023013112195693900_B18","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":"2023013112195693900_B19","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1049\/ip-syb:20050035","article-title":"Algorithmic approaches for computing elementary modes in large biochemical reaction networks","volume":"152","author":"Klamt","year":"2005","journal-title":"Syst. Biol."},{"key":"2023013112195693900_B20","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1186\/1752-0509-1-2","article-title":"Structural and functional analysis of cellular networks with CellNetAnalyzer","volume":"1","author":"Klamt","year":"2007","journal-title":"BMC Syst Biol."},{"key":"2023013112195693900_B21","doi-asserted-by":"crossref","first-page":"1219","DOI":"10.1093\/bioinformatics\/bti145","article-title":"Application of Petri net theory for modelling and validation of the sucrose breakdown pathway in the potato tuber","volume":"12","author":"Koch","year":"2005","journal-title":"Bioinformatics"},{"key":"2023013112195693900_B22","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1002\/(SICI)1097-0290(19961005)52:1<129::AID-BIT13>3.0.CO;2-J","article-title":"Pathway analysis, engineering, and physiological considerations for redirecting central metabolism","volume":"52","author":"Liao","year":"1996","journal-title":"Biotechnol. Bioeng."},{"key":"2023013112195693900_B23","doi-asserted-by":"crossref","first-page":"1119","DOI":"10.1002\/bit.260361107","article-title":"Computer-aided synthesis of biochemical pathways","volume":"36","author":"Mavrovouniotis","year":"1990","journal-title":"Biotechnol. Bioeng."},{"key":"2023013112195693900_B24","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1006\/jtbi.1994.1018","article-title":"Optimization of metabolism: the evolution of metabolic pathways toward simplicity through the game of the pentose phosphate cycle","volume":"166","author":"Mel\u00e9ndez-Hevia","year":"1994","journal-title":"J. Theor. Biol."},{"key":"2023013112195693900_B25","doi-asserted-by":"crossref","first-page":"1415","DOI":"10.1074\/jbc.M203030200","article-title":"Dihydroxyacetone kinases in Saccharomyces cerevisiae are involved in detoxification of dihydroxyacetone","volume":"278","author":"Molin","year":"2003","journal-title":"J. Biol. Chem."},{"issue":"Pt 2","key":"2023013112195693900_B26","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1042\/bj2870473","article-title":"A strategy for increasing an in vivo flux by genetic manipulations. The tryptophan system of yeast","volume":"287","author":"Niederberger","year":"1992","journal-title":"Biochem. J."},{"key":"2023013112195693900_B27","doi-asserted-by":"crossref","volume-title":"Handbook of Applied Optimization","author":"Pardalos","year":"2002","DOI":"10.1007\/978-1-4757-5362-2"},{"key":"2023013112195693900_B28","doi-asserted-by":"crossref","first-page":"E126","DOI":"10.1086\/383593","article-title":"Evolution of cross-feeding in microbial populations","volume":"163","author":"Pfeiffer","year":"2004","journal-title":"Am. Nat."},{"key":"2023013112195693900_B29","doi-asserted-by":"crossref","first-page":"2244","DOI":"10.1016\/j.dam.2008.06.035","article-title":"Path finding approaches and metabolic pathways","volume":"157","author":"Planes","year":"2009","journal-title":"Disc. Appl. Math."},{"key":"2023013112195693900_B30","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":"2023013112195693900_B31","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1006\/jtbi.2000.1073","article-title":"Theory for the systemic definition of metabolic pathways and their use in interpreting metabolic function from a pathway-oriented perspective","volume":"203","author":"Schilling","year":"2000","journal-title":"J. Theor. Biol."},{"key":"2023013112195693900_B32","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1142\/S0218339094000131","article-title":"On elementary flux modes in biochemical reaction systems at steady state","volume":"2","author":"Schuster","year":"1994","journal-title":"J. Biol. Syst"},{"key":"2023013112195693900_B33","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0167-7799(98)01290-6","article-title":"Detection of elementary flux modes in biochemical networks: a promising tool for pathway analysis and metabolic engineering","volume":"17","author":"Schuster","year":"1999","journal-title":"Trends Biotechnol."},{"key":"2023013112195693900_B34","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. Biotechnol."},{"key":"2023013112195693900_B35","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/s002850200143","article-title":"Reaction routes in biochemical reaction systems: algebraic properties, validated calculation procedure and example from nucleotide metabolism","volume":"45","author":"Schuster","year":"2002","journal-title":"J. Math. Biol."},{"key":"2023013112195693900_B36","first-page":"199","article-title":"Understanding the roadmap of metabolism by pathway analysis","volume-title":"Metabolomics \u2013 Methods and Protocols","author":"Schuster","year":"2007"},{"key":"2023013112195693900_B37","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1186\/1471-2105-8-313","article-title":"Integrated network reconstruction, visualization and analysis using YANAsquare","volume":"8","author":"Schwarz","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023013112195693900_B38","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1111\/j.1574-6968.2007.01032.x","article-title":"Role of GldA in dihydroxyacetone and methylglyoxal metabolism of Escherichia coli K12","volume":"279","author":"Subedi","year":"2008","journal-title":"FEMS Microbiol. Lett."},{"key":"2023013112195693900_B39","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":"2023013112195693900_B40","doi-asserted-by":"crossref","first-page":"40041","DOI":"10.1074\/jbc.M606263200","article-title":"Analysis of growth of Lactobacillus plantarum WCFS1 on a complex medium using a genome-scale metabolic model","volume":"281","author":"Teusink","year":"2006","journal-title":"J. Biol. Chem."},{"key":"2023013112195693900_B41","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1016\/0167-7799(83)90055-0","article-title":"The production of L-lysine by fermentation","volume":"1","author":"Tosaka","year":"1983","journal-title":"Trends Biotechnol."},{"key":"2023013112195693900_B42","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":"2023013112195693900_B43","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1002\/bit.260410606","article-title":"Metabolic flux distributions in Corynebacterium glutamicum during growth and lysine overproduction","volume":"41","author":"Vallino","year":"1993","journal-title":"Biotechnol. Bioeng"},{"key":"2023013112195693900_B44","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1002\/bit.10648","article-title":"Metabolic flux and metabolic network analysis of Penicillium chrysogenum using 2D[13C1H] COSY NMR measurements and cumulative bondomer simulation","volume":"83","author":"van Winden","year":"2003","journal-title":"Biotechnol. Bioeng."},{"key":"2023013112195693900_B45","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":"2023013112195693900_B46","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1016\/j.mib.2006.03.001","article-title":"Metabolic engineering of Escherichia coli and Corynebacterium glutamicum for biotechnological production of organic acids and amino acids","volume":"9","author":"Wendisch","year":"2006","journal-title":"Curr. Opin. Microbiol."},{"key":"2023013112195693900_B47","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/7171_2006_089","article-title":"The L-lysine story: from metabolic pathways to industrial production","volume-title":"Amino acid biosynthesis \u2013 Pathways, Regulation and Metabolic Engineering.","author":"Wittmann","year":"2007"},{"key":"2023013112195693900_B48","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1038\/nchembio816","article-title":"Kinetic flux profiling of nitrogen assimilation in Escherichia coli","volume":"2","author":"Yuan","year":"2006","journal-title":"Nat. Chem. Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/23\/3158\/48998339\/bioinformatics_25_23_3158.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/23\/3158\/48998339\/bioinformatics_25_23_3158.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T22:00:17Z","timestamp":1675202417000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/23\/3158\/216440"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,30]]},"references-count":48,"journal-issue":{"issue":"23","published-print":{"date-parts":[[2009,12,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp564","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,12,1]]},"published":{"date-parts":[[2009,9,30]]}}}
