{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T16:36:21Z","timestamp":1788280581159,"version":"build-2803163510"},"reference-count":24,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2024,12,20]],"date-time":"2024-12-20T00:00:00Z","timestamp":1734652800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"publisher","award":["101122224"],"award-info":[{"award-number":["101122224"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,12,26]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Analysis of metabolic networks through extreme rays such as extreme pathways and elementary flux modes has been shown to be effective for many applications. However, due to the combinatorial explosion of candidate vectors, their enumeration is currently limited to small- and medium-scale networks (typically &amp;lt;200 reactions). Partial enumeration of the extreme rays is shown to be possible, but either relies on generating them one-by-one or by implementing a sampling step in the enumeration algorithms. Sampling-based enumeration can be achieved through the canonical basis approach (CBA) or the nullspace approach (NSA). Both algorithms are very efficient in medium-scale networks, but struggle with elementarity testing in sampling-based enumeration of larger networks.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>In this paper, a novel elementarity test is defined and exploited, resulting in significant speedup of the enumeration. Even though NSA is currently considered more effective, the novel elementarity test allows CBA to significantly outpace NSA. This is shown through two case studies, ranging from a medium-scale network to a genome-scale metabolic network with over 600 reactions. In this study, extreme pathways are chosen as the extreme rays, but the novel elementarity test and CBA are equally applicable to the other types. With the increasing complexity of metabolic networks in recent years, CBA with the novel elementarity test shows even more promise as its advantages grows with increased network complexity. Given this scaling aspect, CBA is now the faster method for enumerating extreme rays in genome-scale metabolic networks.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>All case studies are implemented in Python. The codebase used to generate extreme pathways using the different approaches is available at https:\/\/gitlab.kuleuven.be\/biotec-plus\/pos-def-ep.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btae723","type":"journal-article","created":{"date-parts":[[2024,12,20]],"date-time":"2024-12-20T18:01:26Z","timestamp":1734717686000},"source":"Crossref","is-referenced-by-count":3,"title":["Accelerated enumeration of extreme rays through a positive-definite elementarity test"],"prefix":"10.1093","volume":"41","author":[{"given":"Wannes","family":"Mores","sequence":"first","affiliation":[{"name":"Chemical and Biochemical Process Technology and Control (BioTeC+), KU Leuven , 9000 Gent,","place":["Belgium"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Satyajeet S","family":"Bhonsale","sequence":"additional","affiliation":[{"name":"Chemical and Biochemical Process Technology and Control (BioTeC+), KU Leuven , 9000 Gent,","place":["Belgium"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Filip","family":"Logist","sequence":"additional","affiliation":[{"name":"Chemical and Biochemical Process Technology and Control (BioTeC+), KU Leuven , 9000 Gent,","place":["Belgium"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5904-1638","authenticated-orcid":false,"given":"Jan F M","family":"Van Impe","sequence":"additional","affiliation":[{"name":"Chemical and Biochemical Process Technology and Control (BioTeC+), KU Leuven , 9000 Gent,","place":["Belgium"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2024,12,20]]},"reference":[{"key":"2025011122404442600_btae723-B1","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1002\/bit.10803","article-title":"Optknock: a bilevel programming framework for identifying gene knockout strategies for microbial strain optimization","volume":"84","author":"Burgard","year":"2003","journal-title":"Biotechnol Bioeng"},{"key":"2025011122404442600_btae723-B2","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.jprocont.2016.04.012","article-title":"Nonlinear model predictive control of fed-batch fermentations using dynamic flux balance models","volume":"42","author":"Chang","year":"2016","journal-title":"J Process Control"},{"key":"2025011122404442600_btae723-B3","doi-asserted-by":"crossref","first-page":"2006.0004","DOI":"10.1038\/msb4100046","article-title":"Modeling methanogenesis with a genome-scale metabolic reconstruction of Methanosarcina barkeri","volume":"2","author":"Feist","year":"2006","journal-title":"Mol Syst Biol"},{"key":"2025011122404442600_btae723-B4","doi-asserted-by":"crossref","first-page":"1","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 Bioinform"},{"key":"2025011122404442600_btae723-B5","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF01442864","article-title":"Ueber die aufl\u00f6sung linearer gleichungen mit reellen coefficienten","volume":"6","author":"Gordan","year":"1873","journal-title":"Math Ann"},{"key":"2025011122404442600_btae723-B6","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/j.parco.2011.04.002","article-title":"Parallelization of nullspace algorithm for the computation of metabolic pathways","volume":"37","author":"Jevremovi\u0107","year":"2011","journal-title":"Parallel Comput"},{"key":"2025011122404442600_btae723-B7","author":"Kaleta"},{"key":"2025011122404442600_btae723-B8","first-page":"1","article-title":"Which metabolic pathways generate and characterize the flux space? A comparison among elementary modes, extreme pathways and minimal generators","volume":"2010","author":"Llaneras","year":"2010","journal-title":"BioMed Res Int"},{"key":"2025011122404442600_btae723-B9","doi-asserted-by":"crossref","first-page":"i515","DOI":"10.1093\/bioinformatics\/bts401","article-title":"Random sampling of elementary flux modes in large-scale metabolic networks","volume":"28","author":"Machado","year":"2012","journal-title":"Bioinformatics"},{"key":"2025011122404442600_btae723-B10","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0024-3795(81)90100-2","article-title":"A stable theorem of the alternative: an extension of the Gordan theorem","volume":"41","author":"Mangasarian","year":"1981","journal-title":"Linear Algebra Appl"},{"key":"2025011122404442600_btae723-B11","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1016\/j.jprocont.2022.09.002","article-title":"A systematic elementary flux mode selection procedure for deriving macroscopic bioreaction models from metabolic networks","volume":"118","author":"Maton","year":"2022","journal-title":"J Process Control"},{"key":"2025011122404442600_btae723-B12","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":"2025011122404442600_btae723-B13","doi-asserted-by":"crossref","first-page":"903","DOI":"10.1007\/s00285-014-0844-1","article-title":"On dynamically generating relevant elementary flux modes in a metabolic network using optimization","volume":"71","author":"Oddsd\u00f3ttir","year":"2015","journal-title":"J Math Biol"},{"key":"2025011122404442600_btae723-B14","doi-asserted-by":"crossref","first-page":"14464","DOI":"10.1021\/acs.iecr.1c01242","article-title":"Nonlinear predictive control of a bioreactor by surrogate model approximation of flux balance analysis","volume":"60","author":"de Oliveira","year":"2021","journal-title":"Ind Eng Chem Res"},{"key":"2025011122404442600_btae723-B15","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1128\/ecosalplus.10.2.1","article-title":"Reconstruction and use of microbial metabolic networks: the core Escherichia coli metabolic model as an educational guide","volume":"4","author":"Orth","year":"2010","journal-title":"EcoSal plus"},{"key":"2025011122404442600_btae723-B16","doi-asserted-by":"crossref","first-page":"897","DOI":"10.1093\/bioinformatics\/btu733","article-title":"Treeefm: calculating elementary flux modes using linear optimization in a tree-based algorithm","volume":"31","author":"Pey","year":"2015","journal-title":"Bioinformatics"},{"key":"2025011122404442600_btae723-B17","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":"2025011122404442600_btae723-B18","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":"2025011122404442600_btae723-B19","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":"2025011122404442600_btae723-B20","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":"2025011122404442600_btae723-B21","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1093\/bioinformatics\/btp704","article-title":"Predicting metabolic engineering knockout strategies for chemical production: accounting for competing pathways","volume":"26","author":"Tepper","year":"2010","journal-title":"Bioinformatics"},{"key":"2025011122404442600_btae723-B22","author":"Terzer","year":"2009"},{"key":"2025011122404442600_btae723-B23","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":"2025011122404442600_btae723-B24","doi-asserted-by":"crossref","first-page":"1875","DOI":"10.1093\/bib\/bbz094","article-title":"Towards scaling elementary flux mode computation","volume":"21","author":"Ullah","year":"2020","journal-title":"Brief Bioinform"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btae723\/61249356\/btae723.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/1\/btae723\/61249356\/btae723.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/1\/btae723\/61249356\/btae723.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T22:40:58Z","timestamp":1736635258000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btae723\/7929809"}},"subtitle":[],"editor":[{"given":"Pier Luigi","family":"Martelli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2024,12,20]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,12,26]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btae723","relation":{},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,1]]},"published":{"date-parts":[[2024,12,20]]},"article-number":"btae723"}}