Elementary flux modes (EFMs)--non-decomposable minimal pathways--are 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.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--the ancestors of extreme rays--that 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 approximately 26 Mio. EFMs. Within the top 2% modes considering biomass production, most of the gain in flux variability is achieved. In addition, we compute approximately 5 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 >85% of modes that generate several amino acids simultaneously.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.
Beschreibung
Large-scale computation of elementary flux modes with bit pattern trees. - PubMed - NCBI
%0 Journal Article
%1 Terzer2008Largescale
%A Terzer, M
%A Stelling, J
%D 2008
%J Bioinformatics
%K elementary-modes software-tool
%N 19
%P 2229-2235
%R 10.1093/bioinformatics/btn401
%T Large-scale computation of elementary flux modes with bit pattern trees
%U https://www.ncbi.nlm.nih.gov/pubmed/?term=Large-scale+computation+of+elementary+flux+modes+with+bit+pattern+trees.
%V 24
%X Elementary flux modes (EFMs)--non-decomposable minimal pathways--are 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.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--the ancestors of extreme rays--that 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 approximately 26 Mio. EFMs. Within the top 2% modes considering biomass production, most of the gain in flux variability is achieved. In addition, we compute approximately 5 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 >85% of modes that generate several amino acids simultaneously.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.
@article{Terzer2008Largescale,
abstract = {Elementary flux modes (EFMs)--non-decomposable minimal pathways--are 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.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--the ancestors of extreme rays--that 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 approximately 26 Mio. EFMs. Within the top 2% modes considering biomass production, most of the gain in flux variability is achieved. In addition, we compute approximately 5 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 >85% of modes that generate several amino acids simultaneously.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.},
added-at = {2019-05-15T11:23:27.000+0200},
author = {Terzer, M and Stelling, J},
biburl = {https://www.bibsonomy.org/bibtex/2cbf44f0109a613d58060c99e04521a69/karthikraman},
description = {Large-scale computation of elementary flux modes with bit pattern trees. - PubMed - NCBI},
doi = {10.1093/bioinformatics/btn401},
interhash = {00ff30c4a1086ab11eb2543bb14a62a3},
intrahash = {cbf44f0109a613d58060c99e04521a69},
journal = {Bioinformatics},
keywords = {elementary-modes software-tool},
month = oct,
number = 19,
pages = {2229-2235},
pmid = {18676417},
timestamp = {2019-05-15T11:23:27.000+0200},
title = {Large-scale computation of elementary flux modes with bit pattern trees},
url = {https://www.ncbi.nlm.nih.gov/pubmed/?term=Large-scale+computation+of+elementary+flux+modes+with+bit+pattern+trees.},
volume = 24,
year = 2008
}