Exact Algorithms for Finding a Minimum Reaction Cut under a Boolean Model of Metabolic Networks

Takeyuki TAMURA  Tatsuya AKUTSU  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E93-A   No.8   pp.1497-1507
Publication Date: 2010/08/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E93.A.1497
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
metabolic network,  reaction cut,  algorithm,  boolean model,  robustness,  

Full Text: PDF(490.3KB)>>
Buy this Article

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 ReactionCut and MD-ReactionCut are NP-hard even if the maximum outdegree of reaction nodes (Kout) is one. We also present O(1.822n), O(1.959n) and o(2n) time algorithms for MD-ReactionCut with Kout=2, 3, k respectively where n is the number of reaction nodes and k is a constant. The same algorithms also work for ReactionCut if there is no directed cycle. Furthermore, we present a 2O((log n)) time algorithm, which is faster than O((1+ε)n) for any positive constant ε, for the planar case of MD-ReactionCut under a reasonable constraint utilizing Lipton and Tarjan's separator algorithm.