Exact Algorithms for Finding a Minimum Reaction Cut under a Boolean Model of Metabolic Networks
A reaction cut is a set of chemical reactions whose deletion blocks the operation of given reactions or the production of given chemical compounds. In this paper, we study two problems ReactionCut and MD-ReactionCut for calculating the minimum reaction cut of a metabolic network under a Boolean model. These problems are based on the flux balance model and the minimal damage model respectively. We show that Reaction Cut and MD-ReactionCut are NP-hard even if the maximum outdegree of reaction nodes (K(out)) is one. We also present O(1.822(n)), O(1.959(n)) and o(2(n)) time algorithms for MD-ReactionCut with K(out) = 2,3,k respectively where n is the number of reaction nodes and k is a constant. The same algorithms also work for Reaction Cut if there is no directed cycle. Furthermore, we present a 2(O((log) (n)root n)) time algorithm, which is faster than O((1 + epsilon)(n)) for any positive constant epsilon, for the planar case of MD-ReactionCut under a reasonable constraint utilizing Lipton and Tarjan's separator algorithm.
algorithm reaction cut metabolic network booleon model robustness