%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 }