title: Comparison and improvement of algorithms for computing minimal cut sets.
abstract: 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.forename: Christian
authors.initials: C
authors.lastname: Jungreuthmayer
authors.forename: Govind
authors.initials: G
authors.lastname: Nair
authors.forename: Steffen
authors.initials: S
authors.lastname: Klamt
authors.affiliation: Austrian Centre of Industrial Biotechnology, Vienna, Austria. juergen.zanghellini@acib.at.
authors.forename: Jürgen
authors.initials: J
authors.lastname: Zanghellini
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D004926:Escherichia coli / Q000235:genetics; D017353:Gene Deletion; D055786:Gene Knockout Techniques; D006801:Humans; D007091:Image Processing, Computer-Assisted; D053858:Metabolic Networks and Pathways / Q000235:genetics; D008957:Models, Genetic; D012984:Software; D013816:Thermodynamics