Bioinformatics Advance Access originally published online on August 1, 2008
Bioinformatics 2008 24(19):2229-2235; doi:10.1093/bioinformatics/btn401
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Large-scale computation of elementary flux modes with bit pattern trees
Institute of Computational Science and Swiss Institute of Bioinformatics, ETH Zurich, 8092 Zurich, Switzerland
*To whom correspondence should be addressed.
 |
Abstract |
|---|
Motivation: 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.
Results: 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 
26 Mio. EFMs. Within the top 2% modes considering biomass production, most of the gain in flux variability is achieved. In addition, we compute 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.
Availability: 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.
Contact: joerg.stelling{at}inf.ethz.ch
Supplementary information: Supplementary data are available at Bioinformatics online.
Associate Editor: John Quackenbush
Received on March 3, 2008; revised on July 14, 2008; accepted on July 28, 2008
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  L. F. de Figueiredo, A. Podhorski, A. Rubio, C. Kaleta, J. E. Beasley, S. Schuster, and F. J. Planes Computing the shortest elementary flux modes in genome-scale metabolic networks Bioinformatics, December 1, 2009; 25(23): 3158 - 3165. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. Kaleta, L. F. de Figueiredo, and S. Schuster Can the whole be less than the sum of its parts? Pathway analysis in genome-scale metabolic networks using elementary flux patterns Genome Res., October 1, 2009; 19(10): 1872 - 1883. [Abstract] [Full Text] [PDF]
|
|