Comparison and improvement of algorithms for computing minimal cut sets

[摘要] BackgroundConstrained 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.ResultsHere 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.ConclusionsGenerally, both of our new implementations are by at least one order of magnitude faster than other currently available implementations.

[发布日期] 2013-11-06

[关键词] Metabolic network analysis;Elementary modes;Minimal cut sets;Knockout strategies;Integer programming;Berge’s algorithm