Computation of elementary modes: a unifying framework and the new binary approach

BackgroundMetabolic pathway analysis has been recognized as a central approach to the structural analysis of metabolic networks. The concept of elementary (flux) modes provides a rigorous formalism to describe and assess pathways and has proven to be valuable for many applications. However, computing elementary modes is a hard computational task. In recent years we assisted in a multiplication of algorithms dedicated to it. We require a summarizing point of view and a continued improvement of the current methods.ResultsWe show that computing the set of elementary modes is equivalent to computing the set of extreme rays of a convex cone. This standard mathematical representation provides a unified framework that encompasses the most prominent algorithmic methods that compute elementary modes and allows a clear comparison between them. Taking lessons from this benchmark, we here introduce a new method, the binary approach, which computes the elementary modes as binary patterns of participating reactions from which the respective stoichiometric coefficients can be computed in a post-processing step. We implemented the binary approach in FluxAnalyzer 5.1, a software that is free for academics. The binary approach decreases the memory demand up to 96% without loss of speed giving the most efficient method available for computing elementary modes to date.ConclusionsThe equivalence between elementary modes and extreme ray computations offers opportunities for employing tools from polyhedral computation for metabolic pathway analysis. The new binary approach introduced herein was derived from this general theoretical framework and facilitates the computation of elementary modes in considerably larger networks.

• Publication year

  2004

• Venue

  BMC Bioinformatics

• Publication date

  2004-11-04

• Fields of study

  Biology, Medicine, Computer Science

• Identifiers
  DOI 10.1186/1471-2105-5-175PMID 15527509PMCID 544875
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Oriented Matroids

  2017cited by this paper
• Stoichiometric network analysis

  2008cited by this paper
• Nullspace Approach to Determine the Elementary Modes of Chemical Reaction Systems

  2004influential reference
• Comparison of network-based pathway analysis methods.

  2004cited by this paper
• Flux coupling analysis of genome-scale metabolic network reconstructions.

  2004cited by this paper
• Minimal cut sets in biochemical reaction networks

  2004cited by this paper
• Metabolic pathway analysis of yeast strengthens the bridge between transcriptomics and metabolic networks

  2004cited by this paper
• Thermodynamic constraints for biochemical networks.

  2004cited by this paper
• Combinatorial Complexity of Pathway Analysis in Metabolic Networks

  2004influential reference
• Reconstructing metabolic flux vectors from extreme pathways: defining the α-spectrum

  2003cited by this paper
• Constraints-based models: regulation of gene expression reduces the steady-state solution space.

  2003cited by this paper
• Reconstructing metabolic flux vectors from extreme pathways: defining the alpha-spectrum.

  2003cited by this paper
• Two approaches for metabolic pathway analysis?

  2003cited by this paper
• FluxAnalyzer: exploring structure, pathways, and flux distributions in metabolic networks on interactive flux maps

  2003influential reference
• Metabolic pathways in the post-genome era.

  2003influential reference
• Parallel out-of-core algorithm for genome-scale enumeration of metabolic systemic pathways

  2002cited by this paper
• Metabolic network structure determines key aspects of functionality and regulation

  2002cited by this paper
• Use of network analysis of metabolic systems in bioengineering

  2002cited by this paper
• Energy balance for analysis of complex metabolic networks.

  2002cited by this paper
• Reaction routes in biochemical reaction systems: Algebraic properties, validated calculation procedure and example from nucleotide metabolism

  2002influential reference
• Extreme pathways and Kirchhoff's second law.

  2002cited by this paper
• The genome-scale metabolic extreme pathway structure in Haemophilus influenzae shows significant network redundancy.

  2002cited by this paper
• Extreme pathway lengths and reaction participation in genome-scale metabolic networks.

  2002cited by this paper
• Determination of redundancy and systems properties of the metabolic network of Helicobacter pylori using genome-scale extreme pathway analysis.

  2002cited by this paper
• Theory for the systemic definition of metabolic pathways and their use in interpreting metabolic function from a pathway-oriented perspective.

  2000cited by this paper
• A general definition of metabolic pathways useful for systematic organization and analysis of complex metabolic networks

  2000influential reference
• METATOOL: for studying metabolic networks

  1999influential reference
• Oriented Matroids: Notation

  1999cited by this paper
• Detection of elementary flux modes in biochemical networks: a promising tool for pathway analysis and metabolic engineering.

  1999cited by this paper
• Metabolic Pathway Analysis: Basic Concepts and Scientific Applications in the Post‐genomic Era

  1999cited by this paper
• The Regulation of Cellular Systems

  1996cited by this paper
• Double Description Method Revisited

  1995influential reference
• ON ELEMENTARY FLUX MODES IN BIOCHEMICAL REACTION SYSTEMS AT STEADY STATE

  1994influential reference
• Oriented Matroids

  1993cited by this paper
• Detecting strictly detailed balanced subnetworks in open chemical reaction networks

  1991cited by this paper
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra

  1991cited by this paper
• Methods of Mathematical Economics

  1980cited by this paper
• Oriented matroids

  1978cited by this paper
• 3. The Double Description Method

  1953cited by this paper

• COBRA-k: A powerful framework bridging constraint-based and kinetic metabolic modeling

  2026cites this paper
• A distinctive approach to comprehending regulatory signalling mechanisms underlying the hypothalamic‒pituitary‒adrenal (HPA) axis

  2025cites this paper
• Algebraic differentiation for fast sensitivity analysis of optimal flux modes in metabolic models

  2025cites this paper
• A Trade-off between Force and Flow May Lead to Reduced Entropy Production Rate during Faster Microbial Growth

  2025cites this paper
• Low-degree decompositions of flux vectors in faces of the flux cone

  2024cites this paper
• Sensing cellular growth rate facilitates its robust optimal adaptation to changing conditions

  2024cites this paper
• Metabolic Network Analysis Reveals Human Impact on Urban Nitrogen Cycles

  2024cites this paper
• Adapting tree algorithms for partial enumeration of Extreme Pathways sets

  2024cites this paper
• Thermodynamics of unicellular life: Entropy production rate as function of the balanced growth rate

  2024cites this paper
• Logic programming-based Minimal Cut Sets reveal consortium-level therapeutic targets for chronic wound infections

  2024cites this paper
• Accelerated enumeration of extreme rays through a positive-definite elementarity test

  2024cites this paper
• A Markov constraint to uniquely identify elementary flux mode weights in unimolecular metabolic networks

  2023cites this paper
• On the representativeness and stability of a set of EFMs

  2023cites this paper
• Speeding Up the Structural Analysis of Metabolic Network Models Using the Fredman–Khachiyan Algorithm B

  2023cites this paper
• Whole-cell metabolic control analysis

  2023cites this paper
• Linking process and metabolic modelling for the estimation of carbon flux distribution in Corynebacterium glutamicum growth in spent sulfite liquor

  2022cites this paper
• On the geometry of elementary flux modes

  2022cites this paper
• parametrization of V as a surjective analytic map

  2022cites this paper
• Topological descriptors of the parameter region of multistationarity: Deciding upon connectivity

  2022cites this paper
• Understanding FBA Solutions under Multiple Nutrient Limitations

  2021cites this paper
• Modelling Cell Metabolism: A Review on Constraint-Based Steady-State and Kinetic Approaches

  2021influential citation
• EFMlrs: a Python package for elementary flux mode enumeration via lexicographic reverse search

  2021cites this paper
• Robustness of a feedback optimization scheme with application to bioprocess manufacturing

  2021cites this paper
• Computing difference abstractions of linear equation systems

  2021cites this paper
• Data-driven Metabolic Network Reduction for Multiple Modes Considering Uncertain Measurements

  2020cites this paper
• Boosting the extraction of elementary flux modes in genome-scale metabolic networks using the linear programming approach

  2020cites this paper
• Searching for principles of microbial physiology

  2020cites this paper
• Flux Coupling and the Objective Functions’ Length in EFMs

  2020cites this paper
• Unlocking Elementary Conversion Modes: ecmtool Unveils All Capabilities of Metabolic Networks

  2020cites this paper
• Adaptive laboratory evolution for growth coupled microbial production

  2020influential citation
• In Silico Prediction of Metabolic Fluxes in Cancer Cells with Altered S-adenosylmethionine Decarboxylase Activity

  2020cites this paper
• An extended and generalized framework for the calculation of metabolic intervention strategies based on minimal cut sets

  2020cites this paper
• Metabolic pathway analysis in the presence of biological constraints

  2020cites this paper
• In Silico Prediction of Metabolic Fluxes in Cancer Cells with Altered S-adenosylmethionine Decarboxylase Activity

  2020cites this paper
• Key Challenges in Designing CHO Chassis Platforms

  2020cites this paper
• Achieving Ecological Resilience Through Regime Shift Management

  2020cites this paper
• EFMviz: A COBRA Toolbox Extension to Visualize Elementary Flux Modes in Genome-Scale Metabolic Models

  2020cites this paper
• Environmental flexibility does not explain metabolic robustness

  2020cites this paper
• Elementary Conversion Modes enable exploration of all metabolic capabilities of any organism

  2020cites this paper
• Towards scaling elementary flux mode computation

  2019influential citation
• Theoretical derivations , mathematical proofs , core models , and a co-consumption experiment

  2019influential citation
• Finding MEMo: minimum sets of elementary flux modes

  2019influential citation
• Elementary Growth Modes provide a molecular description of cellular self-fabrication

  2019cites this paper
• Computing irreversible minimal cut sets in genome-scale metabolic networks via flux cone projection

  2019cites this paper
• An Analytical Theory of Cellular Growth

  2019cites this paper
• An analytical theory of balanced cellular growth

  2019cites this paper
• Improving the EFMs quality by augmenting their representativeness in LP methods

  2018cites this paper
• Designing Optimized Production Hosts by Metabolic Modeling.

  2018cites this paper
• The MONGOOSE Rational Arithmetic Toolbox.

  2018cites this paper
• Speeding up Dualization in the Fredman-Khachiyan Algorithm B

  2018cites this paper
• The number of active metabolic pathways is bounded by the number of cellular constraints at maximal metabolic rates

  2018cites this paper
• A polyhedral model for enumeration and optimization over the set of circuits

  2018influential citation
• Cybernetic Modeling for Bioreaction Engineering

  2018cites this paper
• Metabolic Network Reductions

  2018influential citation
• MCS2: minimal coordinated supports for fast enumeration of minimal cut sets in metabolic networks

  2018cites this paper
• Reduction, Projection, and Simplification of Metabolic Networks

  2018influential citation
• A system architecture for parallel analysis of flux-balanced metabolic pathways

  2018cites this paper
• Flux tope analysis: studying the coordination of reaction directions in metabolic networks

  2018cites this paper
• Determination of growth-coupling strategies and their underlying principles

  2018cites this paper
• Thermodynamic constraints for identifying elementary flux modes.

  2018cites this paper
• In Silico Approaches to Metabolic Engineering

  2017cites this paper
• Linking metabolic network features to phenotypes using sparse group lasso

  2017cites this paper
• From elementary flux modes to elementary flux vectors: Metabolic pathway analysis with arbitrary linear flux constraints

  2017cites this paper
• A graph-based approach to analyze flux-balanced pathways in metabolic networks

  2017cites this paper
• Redesigning metabolism based on orthogonality principles

  2017cites this paper
• Simplification of Reaction Networks, Confluence and Elementary Modes

  2017influential citation
• Maximal growth rate requires minimal metabolic complexity

  2017cites this paper
• Representativeness of a Set of Metabolic Pathways

  2017cites this paper
• Topological Representation of the Transit Sets of k-Point Crossover Operators

  2017cites this paper
• An algorithm for constructing the skeleton graph of degenerate systems of linear inequalities

  2017cites this paper
• A Genome Scale Model of Geobacillus thermoglucosidasius (C56-YS93) reveals its biotechnological potential on rice straw hydrolysate.

  2017cites this paper
• Predictive macroscopic modeling of Chinese hamster ovary cells in fed-batch processes

  2017cites this paper
• Simplifications Exactes et Structurelles de Réseaux de Réactions Biologiques. (Exact and Structural Simplifications of Biological Reaction Networks)

  2017cites this paper
• Toward Genome‐Scale Metabolic Pathway Analysis

  2016cites this paper
• FluxModeCalculator: an efficient tool for large-scale flux mode computation

  2016cites this paper
• Systems biology of bacteria-host interactions

  2016cites this paper
• An Elementary Tree Transformation Based Approach for Reliability Estimation of Interconnection Networks

  2016cites this paper
• Méthodes avancées de raisonnement en logique propositionnelle : application aux réseaux métaboliques. (Advanced reasoning methods in propositional logics: application to metabolic networks)

  2016cites this paper
• Study of the evolution of symbiosis at the metabolic level using models from game theory and economics

  2016influential citation
• gEFM: An Algorithm for Computing Elementary Flux Modes Using Graph Traversal

  2016cites this paper
• Constraint-based modelling of metabolism in Arabidopsis thaliana

  2016cites this paper
• Normalizing Chemical Reaction Networks by Confluent Structural Simplification

  2016cites this paper
• Robustness analysis of elementary flux modes generated by column generation.

  2016cites this paper
• Structural simplification of chemical reaction networks in partial steady states

  2016cites this paper
• Analysis of Bioprocesses. Dynamic Modeling is a Must

  2016cites this paper
• On the feasibility of growth-coupled product synthesis in microbial strains.

  2015cites this paper
• Designing minimal microbial strains of desired functionality using a genetic algorithm

  2015cites this paper
• Macroscopic modeling of mammalian cell growth and metabolism

  2015cites this paper
• Development of Complementary Elementary ModeAnalysis for Integration of Heterogeneous Biological Data into a Complex Metabolic Network

  2015cites this paper
• Recent advances in elementary flux modes and yield space analysis as useful tools in metabolic network studies

  2015cites this paper
• An algorithm for the reduction of genome-scale metabolic network models to meaningful core models

  2015cites this paper
• Metabolomics integrated elementary flux mode analysis in large metabolic networks

  2015cites this paper
• Algorithms for the constraint-based analysis of metabolic networks

  2015influential citation
• Macroscopic Modeling of Metabolic Reaction Networks and Dynamic Identification of Elementary Flux Modes by Column Generation

  2015cites this paper
• Finding minimal P / T-invariants as a CSP

  2015influential citation
• Advances in network-based metabolic pathway analysis and gene expression data integration

  2015cites this paper
• Robust generation of elementary flux modes

  2015cites this paper
• Fluxes and fluctuations in biochemical models

  2015cites this paper
• Interplay between Constraints, Objectives, and Optimality for Genome-Scale Stoichiometric Models

  2015cites this paper
• Computational Methods for Modelling and Analysing Biological Networks

  2015cites this paper