Comparison and improvement of algorithms for computing minimal cut sets

BMC Bioinformatics

Methodology Article

Christian Jungreuthmayer¹  Govind Nair¹  Jürgen Zanghellini¹  Steffen Klamt² 

[1] Austrian Centre of Industrial Biotechnology, Vienna, Austria;Department of Biotechnology, University of Natural Resources and Life Sciences, Vienna, Austria;Max Planck Institute for Dynamics of Complex Technical Systems, Magdeburg, Germany;

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

DOI  :  10.1186/1471-2105-14-318

 received in 2013-01-18, accepted in 2013-10-30,  发布年份 2013

来源: Springer

【 摘 要 】

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.

【 授权许可】

Unknown   
© Jungreuthmayer et al.; licensee BioMed Central Ltd. 2013. This article is published under license to BioMed Central Ltd. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.