Bioinformatics Advance Access published online on November 11, 2004
Bioinformatics, doi:10.1093/bioinformatics/bti127
Bioinformatics © Oxford University Press 2004; all rights reserved
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1 Institute of Pharmacology, University of Bern, Friedbuehlstr. 49, CH-3010 Bern, Switzerland
* To whom correspondence should be addressed.
Motivation: Genome scale analysis of the metabolic network of a microorganism is a major challenge in bioinformatics. The combinatorial explosion, which occurs during the construction of elementary fluxes (non-redundant pathways) requires sophisticated and efficient algorithms to tackle the problem. Results: Mathematically, the calculation of elementary fluxes amounts to characterizing the space of solutions to a mixed system of linear equalities, given by the stoichiometry matrix, and linear inequalities, arising from the irreversibility of some or all of the reactions in the network. Previous approaches to this problem, have iteratively solved for the equalities while satisfying the inequalities throughout the process. In an extension of previous work (Wagner, J. Phys Chem. B, 108, 2004), here we consider the complementary approach and derive an algorithm which satisfies the inequalities one by one while staying in the space of solution of the equality constraints. Benchmarks on different subnetworks of the central carbon metabolism of E. Coli show that this new approach yields a significant reduction in the execution time of the calculation. This reduction arises since the odds that an intermediate elementary flux already fulfills an additional inequality are larger than when having to satisfy an additional equality constraint. Availability: The code is available upon request. Supplementary information: Pseudo code and a Mathematica implementation of the algorithm is on the OUP server.
Revised October 11, 2004
Accepted October 20, 2004
Article
An improved algorithm for stoichiometric network analysis: theory and applications
R. Urbanczik, E-mail: robert.urbanczik{at}pki.unibe.ch
Abstract 
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  F. J. Planes and J. E. Beasley An optimization model for metabolic pathways Bioinformatics, October 15, 2009; 25(20): 2723 - 2729. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
L. F. de Figueiredo, S. Schuster, C. Kaleta, and D. A. Fell Can sugars be produced from fatty acids? A test case for pathway analysis tools Bioinformatics, January 1, 2009; 25(1): 152 - 158. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
L. F. de Figueiredo, S. Schuster, C. Kaleta, and D. A. Fell Can sugars be produced from fatty acids? A test case for pathway analysis tools Bioinformatics, November 15, 2008; 24(22): 2615 - 2621. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. v. Kamp and S. Schuster Metatool 5.0: fast and flexible elementary modes analysis Bioinformatics, August 1, 2006; 22(15): 1930 - 1931. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. Urbanczik and C. Wagner Functional stoichiometric analysis of metabolic networks Bioinformatics, November 15, 2005; 21(22): 4176 - 4180. [Abstract] [Full Text] [PDF]
|
|