{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T04:23:10Z","timestamp":1772252590502,"version":"3.50.1"},"reference-count":50,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2021,10,19]],"date-time":"2021-10-19T00:00:00Z","timestamp":1634601600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>Metabolic pathway analysis is a key method to study a metabolism in its steady state, and the concept of elementary fluxes (EFs) plays a major role in the analysis of a network in terms of non-decomposable pathways. The supports of the EFs contain in particular those of the elementary flux modes (EFMs), which are the support-minimal pathways, and EFs coincide with EFMs when the only flux constraints are given by the irreversibility of certain reactions. Practical use of both EFMs and EFs has been hampered by the combinatorial explosion of their number in large, genome-scale systems. The EFs give the possible pathways in a steady state but the real pathways are limited by biological constraints, such as thermodynamic or, more generally, kinetic constraints and regulatory constraints from the genetic network. We provide results on the mathematical structure and geometrical characterization of the solution space in the presence of such biological constraints (which is no longer a convex polyhedral cone or a convex polyhedron) and revisit the concept of EFMs and EFs in this framework. We show that most of the results depend only on very general properties of compatibility of constraints with vector signs: either sign-invariance, satisfied by regulatory constraints, or sign-monotonicity (a stronger property), satisfied by thermodynamic and kinetic constraints. We show in particular that the solution space for sign-monotone constraints is a union of particular faces of the original polyhedral cone or polyhedron and that EFs still coincide with EFMs and are just those of the original EFs that satisfy the constraint, and we show how to integrate their computation efficiently in the double description method, the most widely used method in the tools dedicated to EFs computation. We show that, for sign-invariant constraints, the situation is more complex: the solution space is a disjoint union of particular semi-open faces (i.e., without some of their own faces of lesser dimension) of the original polyhedral cone or polyhedron and, if EFs are still those of the original EFs that satisfy the constraint, their computation cannot be incrementally integrated into the double description method, and the result is not true for EFMs, that are in general strictly more numerous than those of the original EFMs that satisfy the constraint.<\/jats:p>","DOI":"10.3390\/computation9100111","type":"journal-article","created":{"date-parts":[[2021,10,20]],"date-time":"2021-10-20T01:23:46Z","timestamp":1634693026000},"page":"111","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Metabolic Pathway Analysis in the Presence of Biological Constraints"],"prefix":"10.3390","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1679-0804","authenticated-orcid":false,"given":"Philippe","family":"Dague","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris-Saclay, CNRS, ENS Paris-Saclay, Inria, Laboratoire M\u00e9thodes Formelles, 91190 Gif-sur-Yvette, France"}]}],"member":"1968","published-online":{"date-parts":[[2021,10,19]]},"reference":[{"key":"ref_1","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":"ref_2","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."},{"key":"ref_3","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":"ref_4","doi-asserted-by":"crossref","first-page":"753904","DOI":"10.1155\/2010\/753904","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":"J. Biomed. Biotechnol."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1009","DOI":"10.1002\/biot.201200269","article-title":"Elementary flux modes in a nutshell: Properties, calculation and applications","volume":"8","author":"Zanghellini","year":"2013","journal-title":"Biotechnol. J."},{"key":"ref_6","first-page":"90","article-title":"Elementary Vectors and Conformal Sums in Polyhedral Geometry and their Relevance for Metabolic Pathway Analysis","volume":"7","author":"Regensburger","year":"2016","journal-title":"Front. Genet."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Klamt, S., Regensburger, G., Gerstl, M.P., Jungreuthmayer, C., Schuster, S., Mahadevan, R., Zanghellini, J., and M\u00fcller, S. (2017). From elementary flux modes to elementary flux vectors: Metabolic pathway analysis with arbitrary linear flux constraints. PLoS Comput. Biol., 13.","DOI":"10.1371\/journal.pcbi.1005409"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"4193","DOI":"10.1073\/pnas.95.8.4193","article-title":"The underlying pathway structure of biochemical reaction networks","volume":"95","author":"Schilling","year":"1998","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_9","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":"ref_10","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1089\/cmb.2009.0020","article-title":"On Algebraic Properties of Extreme Pathways in Metabolic Networks","volume":"17","author":"Jevremovic","year":"2010","journal-title":"J. Comput. Biol."},{"key":"ref_11","unstructured":"Kuhn, H.W., and Tucker, A.W. (1953). The double description method. Contributions to the Theory of Games II, Annals of Mathematics Studies, Princeton University Press."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/3-540-61576-8_77","article-title":"Double Description Method Revisited","volume":"Volume 1120","author":"Deza","year":"1996","journal-title":"Combinatorics and Computer Science"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1093\/bioinformatics\/bty550","article-title":"Flux tope analysis: Studying the coordination of reaction directions in metabolic networks","volume":"35","author":"Gerstl","year":"2019","journal-title":"Bioinformatics"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Gudmundsson, S., and Thiele, I. (2010). Computationally efficient flux variability analysis. BMC Bioinform., 11.","DOI":"10.1186\/1471-2105-11-489"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/BF02918360","article-title":"Stoichiometry network analysis","volume":"12","author":"Clarke","year":"1988","journal-title":"Cell Biophys."},{"key":"ref_16","unstructured":"Rockafellar, R.T. (1969). The elementary vectors of a subspace of RN. Combinatorial Mathematics and Its Applications, University of North Carolina Press."},{"key":"ref_17","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":"ref_18","doi-asserted-by":"crossref","unstructured":"Gagneur, J., and Klamt, S. (2004). Computation of elementary modes: A unifying framework and the new binary approach. BMC Bioinform., 5.","DOI":"10.1186\/1471-2105-5-175"},{"key":"ref_19","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":"Podhorski","year":"2009","journal-title":"Bioinformatics"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1007\/s00454-008-9050-5","article-title":"Generating all vertices of a polyhedron is hard","volume":"39","author":"Khachiyan","year":"2008","journal-title":"Discret. Comput. Geom."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1016\/j.biosystems.2009.11.004","article-title":"A note on the complexity of finding and enumerating elementary modes","volume":"99","author":"Sagot","year":"2010","journal-title":"BioSystems"},{"key":"ref_22","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":"Chierichetti","year":"2009","journal-title":"BioSystems"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1287\/moor.8.3.381","article-title":"The complexity of vertex enumeration methods","volume":"8","author":"Dyer","year":"1983","journal-title":"Math. Oper. Res."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1112\/S0025579300002850","article-title":"The maximum numbers of faces of a convex polytope","volume":"17","author":"McMullen","year":"1970","journal-title":"Mathematika"},{"key":"ref_25","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":"ref_26","doi-asserted-by":"crossref","first-page":"1265","DOI":"10.1093\/bioinformatics\/btv742","article-title":"FluxModeCalculator: An efficient tool for large-scale flux mode computation","volume":"32","year":"2016","journal-title":"Bioinformatics"},{"key":"ref_27","unstructured":"Atkins, P., and de Paula, J. (2014). Physical Chemistry, Freeman. [10th ed.]."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1792","DOI":"10.1529\/biophysj.106.093138","article-title":"Thermodynamics-based metabolic flux analysis","volume":"92","author":"Henry","year":"2007","journal-title":"Biophys. J."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1528","DOI":"10.1093\/bioinformatics\/btq141","article-title":"Modular rate laws for enzymatic reactions: Thermodynamics, elasticities and implementation","volume":"26","author":"Liebermeister","year":"2010","journal-title":"Bioinformatics"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"2772","DOI":"10.1016\/j.febslet.2013.07.028","article-title":"A note on the kinetics of enzyme action: A decomposition that highlights thermodynamic effects","volume":"587","author":"Noor","year":"2013","journal-title":"FEBS Lett."},{"key":"ref_31","unstructured":"Jungreuthmayer, C., Ruckerbauer, D.E., and Zanghellini, J. (2012). Utilizing gene regulatory information to speed up the calculation of elementary flux modes. arXiv."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.biosystems.2013.04.002","article-title":"regEfmtool: Speeding up elementary flux mode calculation using transcriptional regulatory rules in the form of three-state logic","volume":"113","author":"Jungreuthmayer","year":"2013","journal-title":"BioSystems"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Jungreuthmayer, C., Ruckerbauer, D.E., Gerstl, M.P., Hanscho, M., and Zanghellini, J. (2015). Avoiding the enumeration of infeasible elementary flux modes by including transcriptional regulatory rules in the enumeration process saves computational costs. PLoS ONE, 10.","DOI":"10.1371\/journal.pone.0129840"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1101\/gr.1926504","article-title":"Flux coupling analysis of genome-scale metabolic network reconstructions","volume":"14","author":"Burgard","year":"2004","journal-title":"Genome Res."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Larhlimi, A., David, L., Selbig, J., and Bockmayr, A. (2012). F2C2: A fast tool for the computation of flux coupling in genome-scale metabolic networks. BMC Bioinform., 13.","DOI":"10.1186\/1471-2105-13-57"},{"key":"ref_36","first-page":"91","article-title":"EFM\u2013Recorder\u2014Faster Elementary Mode Enumeration via Reaction Coupling Order","volume":"1","author":"Goldstein","year":"2015","journal-title":"Adv. Syst. and Synth. Biol."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Peres, S., Jolic\u0153ur, M., Moulin, C., Dague, P., and Schuster, S. (2017). How important is thermodynamics for identifying elementary flux modes?. PLoS ONE, 12.","DOI":"10.1371\/journal.pone.0171440"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1042\/BST20170260","article-title":"Thermodynamic constraints for identifying the elementary flux modes","volume":"46","author":"Peres","year":"2018","journal-title":"Biochem. Soc. Trans."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"1782","DOI":"10.1111\/febs.13702","article-title":"Which sets of elementary flux modes form thermodynamically feasible flux distributions?","volume":"283","author":"Gerstl","year":"2016","journal-title":"FEBS J."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/j.jtbi.2013.11.015","article-title":"Enzyme allocation problems in kinetic metabolic networks: Optimal solutions are elementary flux modes","volume":"347","author":"Regensburger","year":"2014","journal-title":"J. Theor. Biol."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"1547","DOI":"10.1111\/febs.12722","article-title":"Metabolic states with maximal specific rate carry flux through an elementary flux mode","volume":"281","author":"Wortel","year":"2014","journal-title":"FEBS J."},{"key":"ref_42","unstructured":"Morterol, M., Dague, P., Peres, S., and Simon, L. (2016, January 5). Minimality of Metabolic Flux Modes under Boolean Regulation Constraints. Proceedings of the 12th International Workshop on Constraint-Based Methods for Bioinformatics (WCB\u201916), Toulouse, France."},{"key":"ref_43","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":"ref_44","doi-asserted-by":"crossref","first-page":"2232","DOI":"10.1093\/bioinformatics\/btv111","article-title":"tEFMA: Computing thermodynamically feasible elementary flux modes in metabolic networks","volume":"31","author":"Gerstl","year":"2015","journal-title":"Bioinformatics"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"8930","DOI":"10.1038\/srep08930","article-title":"Metabolomics integrated elementary flux mode analysis in large metabolic networks","volume":"5","author":"Gerstl","year":"2015","journal-title":"Sci. Rep."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1089\/cmb.2007.0229","article-title":"Computing knock-out strategies in metabolic networks","volume":"15","author":"Haus","year":"2008","journal-title":"J. Comput. Biol."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Jungreuthmayer, C., Nair, G., Klamt, S., and Zanghellini, J. (2013). Comparison and improvement of algorithms for computing minimal cut sets. BMC Bioinform., 14.","DOI":"10.1186\/1471-2105-14-318"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1093\/bioinformatics\/btr674","article-title":"Minimal cut sets in a metabolic network are elementary modes in a dual network","volume":"28","author":"Ballerstein","year":"2012","journal-title":"Bioinformatics"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"von Kamp, A., and Klamt, S. (2014). Enumeration of Smallest Intervention Strategies in Genome-Scale Metabolic Networks. PLoS Comput. Biol., 10.","DOI":"10.1371\/journal.pcbi.1003378"},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Mahout, M., Carlson, R.P., and Peres, S. (2020). Answer Set Programming for Computing Constraints-Based Elementary Flux Modes: Application to Escherichia coli Core Metabolism. Processes, 8.","DOI":"10.3390\/pr8121649"}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/9\/10\/111\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:17:55Z","timestamp":1760167075000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/9\/10\/111"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,19]]},"references-count":50,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2021,10]]}},"alternative-id":["computation9100111"],"URL":"https:\/\/doi.org\/10.3390\/computation9100111","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2020.06.27.175455","asserted-by":"object"}]},"ISSN":["2079-3197"],"issn-type":[{"value":"2079-3197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,19]]}}}