Journal
BMC BIOINFORMATICS
Volume 14, Issue -, Pages -Publisher
BMC
DOI: 10.1186/1471-2105-14-318
Keywords
Metabolic network analysis; Elementary modes; Minimal cut sets; Knockout strategies; Integer programming; Berge's algorithm
Categories
Funding
- Federal Ministry of Economy, Family and Youth (BMWFJ)
- Federal Ministry of Traffic, Innovation and Technology (bmvit)
- Styrian Business Promotion Agency SFG
- Standortagentur Tirol
- ZIT - Technology Agency of the City of Vienna through the COMET
- German Federal Ministry of Education and Research [e:Bio - 0316183D]
- Ministry of Education and Research of Saxony-Anhalt (Research Center Dynamic Systems: Biosystems Engineering)
Ask authors/readers for more resources
Background: Constrained minimal cut sets (cMCSs) have recently been introduced as a framework to enumerate minimal genetic intervention strategies for targeted optimization of metabolic networks. Two different algorithmic schemes (adapted Berge algorithm and binary integer programming) have been proposed to compute cMCSs from elementary modes. However, in their original formulation both algorithms are not fully comparable. Results: Here we show that by a small extension to the integer program both methods become equivalent. Furthermore, based on well-known preprocessing procedures for integer programming we present efficient preprocessing steps which can be used for both algorithms. We then benchmark the numerical performance of the algorithms in several realistic medium-scale metabolic models. The benchmark calculations reveal (i) that these preprocessing steps can lead to an enormous speed-up under both algorithms, and (ii) that the adapted Berge algorithm outperforms the binary integer approach. Conclusions: Generally, both of our new implementations are by at least one order of magnitude faster than other currently available implementations.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available