title: An improved algorithm for stoichiometric network analysis: theory and applications.
abstract: BACKGROUND
  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, 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 Escherichia 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.
authors.affiliation: Institute of Pharmacology, University of Bern, Friedbuehlstrasse 49, CH-3010 Bern, Switzerland. robert.urbanczik@pki.unibe.ch
authors.forename: R
authors.initials: R
authors.lastname: Urbanczik
authors.forename: C
authors.initials: C
authors.lastname: Wagner
mesh_terms: D000465:Algorithms; D020650:Combinatorial Chemistry Techniques; D003198:Computer Simulation; D016208:Databases, Factual; D004734:Energy Metabolism / Q000502:physiology; D004926:Escherichia coli / Q000502:physiology*; D029968:Escherichia coli Proteins / Q000378:metabolism*; D020869:Gene Expression Profiling / Q000379:methods*; D015964:Gene Expression Regulation, Bacterial / Q000502:physiology*; D008954:Models, Biological; D025941:Protein Interaction Mapping / Q000379:methods*; D015398:Signal Transduction / Q000502:physiology*; D014157:Transcription Factors / Q000378:metabolism
chemical_list: D029968:Escherichia coli Proteins; D014157:Transcription Factors