The DOI matches its Crossref record; 17 of the 17 references it cites were found in a registry or an index.
Large-scale computation of elementary flux modes with bit pattern trees
Open accessAbstract
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@inf.ethz.ch Supplementary information: Supplementary data are available at Bioinformatics online.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
Multidimensional binary search trees used for associative searching
Bentley, J. L. (1975) · Communications of the ACM · doi:10.1145/361002.361007 · Cited by 7,520
Analysis of optimality in natural and perturbed metabolic networks
Segrè, D., Vitkup, D., & Church, G. M. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.232349399 · Cited by 1,362
Genome-scale models of microbial cells: evaluating the consequences of constraints
Price, N. D., Reed, J. L., & Palsson, B. Ø. (2004) · Nature Reviews Microbiology · doi:10.1038/nrmicro1023 · Cited by 1,023
Metabolic network structure determines key aspects of functionality and regulation
Stelling, J., Klamt, S., Bettenbrock, K., Schuster, S., & Gilles, E. D. (2002) · Nature · doi:10.1038/nature01166 · Cited by 802
Self-citationSystematic evaluation of objective functions for predicting intracellular fluxes in Escherichia coli
Schuetz, R., Kuepfer, L., & Sauer, U. (2007) · Molecular Systems Biology · doi:10.1038/msb4100162 · Cited by 677
ON ELEMENTARY FLUX MODES IN BIOCHEMICAL REACTION SYSTEMS AT STEADY STATE
SCHUSTER, S., & HILGETAG, C. (1994) · Journal of Biological Systems · doi:10.1142/s0218339094000131 · Cited by 534
The metabolic world of Escherichia coli is not small
Arita, M. (2004) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0306458101 · Cited by 315
Computation of elementary modes: a unifying framework and the new binary approach
Gagneur, J., & Klamt, S. (2004) · BMC Bioinformatics · doi:10.1186/1471-2105-5-175 · Cited by 271
Price, N. D., Papin, J. A., & Palsson, B. Ø. (2002) · Genome Research · doi:10.1101/gr.218002 · Cited by 129
Cited by
Multidimensional Optimality of Microbial Metabolism
Schuetz, R., Zamboni, N., Zampieri, M., Heinemann, M., & Sauer, U. (2012) · Science · doi:10.1126/science.1216882 · Cited by 420
OptFlux: an open-source software platform for in silico metabolic engineering
Rocha, I., Maia, P., Evangelista, P., Vilaça, P., Soares, S., Pinto, J. P., Nielsen, J., Patil, K. R., Ferreira, E. C., & Rocha, M. (2010) · BMC Systems Biology · doi:10.1186/1752-0509-4-45 · Cited by 388
Genome-scale models of bacterial metabolism: reconstruction and applications
Durot, M., Bourguignon, P.-Y., & Schachter, V. (2009) · FEMS Microbiology Reviews · doi:10.1111/j.1574-6976.2008.00146.x · Cited by 326
Inverse problems in systems biology
Engl, H. W., Flamm, C., Kügler, P., Lu, J., Müller, S., & Schuster, P. (2009) · Inverse Problems · doi:10.1088/0266-5611/25/12/123014 · Cited by 122
Baroukh, C., Muñoz-Tamayo, R., Steyer, J.-P., & Bernard, O. (2014) · PLoS ONE · doi:10.1371/journal.pone.0104499 · Cited by 80
Metadata
- Authors
- Terzer, M., & Stelling, J.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2008-08-01
- Volume
- 24
- Issue
- 19
- Pages
- 2229-2235
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2110355460
- Cited by
- 328
- References
- 17
- FWCI
- 7.07
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Large-scale computation of elementary flux modes with bit pattern trees. https://app.cochat.ai/papers/10.1093/bioinformatics/btn401
- The paper
- Terzer, M., & Stelling, J. (2008). Large-scale computation of elementary flux modes with bit pattern trees. Bioinformatics. https://doi.org/10.1093/bioinformatics/btn401
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.