{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T03:26:48Z","timestamp":1773804408264,"version":"3.50.1"},"reference-count":18,"publisher":"Oxford University Press (OUP)","issue":"19","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,10,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Elementary flux modes (EFMs)\u2014non-decomposable minimal pathways\u2014are commonly accepted tools for metabolic network analysis under steady state conditions. Valid states of the network are linear superpositions of elementary modes shaping a polyhedral cone (the flux cone), which is a well-studied convex set in computational geometry. Computing EFMs is thus basically equivalent to extreme ray enumeration of polyhedral cones. This is a combinatorial problem with poorly scaling algorithms, preventing the large-scale analysis of metabolic networks so far.<\/jats:p>\n               <jats:p>Results: Here, we introduce new algorithmic concepts that enable large-scale computation of EFMs. Distinguishing extreme rays from normal (composite) vectors is one critical aspect of the algorithm. We present a new recursive enumeration strategy with bit pattern trees for adjacent rays\u2014the ancestors of extreme rays\u2014that is roughly one order of magnitude faster than previous methods. Additionally, we introduce a rank updating method that is particularly well suited for parallel computation and a residue arithmetic method for matrix rank computations, which circumvents potential numerical instability problems. Multi-core architectures of modern CPUs can be exploited for further performance improvements. The methods are applied to a central metabolism network of Escherichia coli, resulting in \u224826 Mio. EFMs. Within the top 2% modes considering biomass production, most of the gain in flux variability is achieved. In addition, we compute \u22485 Mio. EFMs for the production of non-essential amino acids for a genome-scale metabolic network of Helicobacter pylori. Only large-scale EFM analysis reveals the &amp;gt;85% of modes that generate several amino acids simultaneously.<\/jats:p>\n               <jats:p>Availability: An implementation in Java, with integration into MATLAB and support of various input formats, including SBML, is available at http:\/\/www.csb.ethz.ch in the tools section; sources are available from the authors upon request.<\/jats:p>\n               <jats:p>Contact: \u00a0joerg.stelling@inf.ethz.ch<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btn401","type":"journal-article","created":{"date-parts":[[2008,8,2]],"date-time":"2008-08-02T00:26:00Z","timestamp":1217636760000},"page":"2229-2235","source":"Crossref","is-referenced-by-count":270,"title":["Large-scale computation of elementary flux modes with bit pattern trees"],"prefix":"10.1093","volume":"24","author":[{"given":"Marco","family":"Terzer","sequence":"first","affiliation":[{"name":"Institute of Computational Science and Swiss Institute of Bioinformatics, ETH Zurich, 8092 Zurich, Switzerland"}]},{"given":"J\u00f6rg","family":"Stelling","sequence":"additional","affiliation":[{"name":"Institute of Computational Science and Swiss Institute of Bioinformatics, ETH Zurich, 8092 Zurich, Switzerland"}]}],"member":"286","published-online":{"date-parts":[[2008,8,1]]},"reference":[{"key":"2023020211111611700_B1","doi-asserted-by":"crossref","first-page":"1543","DOI":"10.1073\/pnas.0306458101","article-title":"The metabolic world ofEscherichia coliis not small","volume":"101","author":"Arita","year":"2004","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023020211111611700_B2","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","article-title":"Multidimensional binary search trees used for associative searching","volume":"18","author":"Bentley","year":"1975","journal-title":"Commun. ACM"},{"key":"2023020211111611700_B3","first-page":"91","article-title":"Double description method revisited","volume-title":"Combinatorics and Computer Science.","author":"Fukuda","year":"1995"},{"key":"2023020211111611700_B4","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":"2023020211111611700_B5","doi-asserted-by":"crossref","first-page":"73","DOI":"10.7551\/mitpress\/9780262195485.003.0005","article-title":"Stoichiometric and constraint-based modeling","volume-title":"System Modeling in Cellular Biology.","author":"Klamt","year":"2006"},{"key":"2023020211111611700_B6","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":"IEE Proc. Syst. Biol"},{"key":"2023020211111611700_B7","article-title":"Seminumerical Algorithms","volume-title":"The Art of Computer Programming3rd edn.","author":"Knuth","year":"1997","edition":"3rd edn."},{"key":"2023020211111611700_B8","first-page":"51","article-title":"The double description method","volume-title":"Contributions to the Theory of Games II of Annals of Math. Studies.","author":"Motzkin","year":"1953"},{"key":"2023020211111611700_B9","first-page":"760","article-title":"Determination of redundancy and systems properties of the metabolic network ofHelicobacter Pyloriusing genome-scale extreme pathway analysis","volume":"12","author":"Price","year":"2002","journal-title":"Genetics Res"},{"key":"2023020211111611700_B10","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":"2023020211111611700_B11","doi-asserted-by":"crossref","DOI":"10.1038\/msb4100162","article-title":"Systematic evaluation of objective functions for predicting intracellular fluxes inEscherichia coli","volume":"3","author":"Schuetz","year":"2007","journal-title":"Mol. Syst. Biol"},{"key":"2023020211111611700_B12","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":"2023020211111611700_B13","first-page":"15112","article-title":"Analysis of optimality in natural and perturbed metabolic networks","volume-title":"Proc. Natl Acad. Sci. USA.","author":"Segr\u00e9","year":"2002"},{"key":"2023020211111611700_B14","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1038\/nature01166","article-title":"Metabolic network structure determines key aspects of functionality and regulation","volume":"420","author":"Stelling","year":"2002","journal-title":"Nature"},{"key":"2023020211111611700_B15","first-page":"333","article-title":"Accelerating the computation of elementary modes using pattern trees","volume-title":"Lecture Notes in Computer Science.","author":"Terzer","year":"2006"},{"key":"2023020211111611700_B16","doi-asserted-by":"crossref","first-page":"4176","DOI":"10.1093\/bioinformatics\/bti674","article-title":"Functional stoichiometric analysis of metabolic networks","volume":"21","author":"Urbanczik","year":"2005","journal-title":"Bioinformatics"},{"key":"2023020211111611700_B17","doi-asserted-by":"crossref","first-page":"2425","DOI":"10.1021\/jp034523f","article-title":"Nullspace approach to determine the elementary modes of chemical reaction systems","volume":"108","author":"Wagner","year":"2004","journal-title":"J. Phys. Chem. B"},{"key":"2023020211111611700_B18","doi-asserted-by":"crossref","first-page":"3837","DOI":"10.1529\/biophysj.104.055129","article-title":"The geometry of the flux cone of a metabolic network","volume":"89","author":"Wagner","year":"2005","journal-title":"Biophys. J"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/19\/2229\/49050673\/bioinformatics_24_19_2229.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/19\/2229\/49050673\/bioinformatics_24_19_2229.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T13:34:07Z","timestamp":1675344847000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/24\/19\/2229\/246674"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8,1]]},"references-count":18,"journal-issue":{"issue":"19","published-print":{"date-parts":[[2008,10,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn401","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2008,10,1]]},"published":{"date-parts":[[2008,8,1]]}}}