Bioinformatics Advance Access published online on August 1, 2008
Bioinformatics, doi:10.1093/bioinformatics/btn401
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Large scale computation of elementary flux modes with bit pattern trees
aInstitute of Computational Science and Swiss Institute of Bioinformatics, ETH Zurich, 8092 Zurich, Switzerland
*To whom correspondence should be addressed. Dr. Jörg Stelling, E-mail: joerg.stelling{at}inf.ethz.ch
 |
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 E. 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 nonessential amino acids for a genome-scale metabolic network of H. pylori. Only large-scale EFM analysis reveals the >85percnt; 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://csb.inf.ethz.ch in the tools section; sources are available fromthe authors upon request.
Contact: marco.terzer{at}inf.ethz.ch, joerg.stelling{at}inf.ethz.ch
Associate Editor: Prof. 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]
|
|