IEICE TRANSACTIONS on Fundamentals
Exact Algorithms for Finding a Minimum Reaction Cut under a Boolean Model of Metabolic Networks
Summary :
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)
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E93-A No.8 pp.1497-1507
- Publication Date
- 2010/08/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E93.A.1497
- Type of Manuscript
- PAPER
- Category
- Algorithms and Data Structures
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takeyuki TAMURA, Tatsuya AKUTSU, "Exact Algorithms for Finding a Minimum Reaction Cut under a Boolean Model of Metabolic Networks" in IEICE TRANSACTIONS on Fundamentals,
vol. E93-A, no. 8, pp. 1497-1507, August 2010, doi: 10.1587/transfun.E93.A.1497.
Abstract: 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)
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E93.A.1497/_p
Copy
@ARTICLE{e93-a_8_1497,
author={Takeyuki TAMURA, Tatsuya AKUTSU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Exact Algorithms for Finding a Minimum Reaction Cut under a Boolean Model of Metabolic Networks},
year={2010},
volume={E93-A},
number={8},
pages={1497-1507},
abstract={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)
keywords={},
doi={10.1587/transfun.E93.A.1497},
ISSN={1745-1337},
month={August},}
Copy
TY - JOUR
TI - Exact Algorithms for Finding a Minimum Reaction Cut under a Boolean Model of Metabolic Networks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1497
EP - 1507
AU - Takeyuki TAMURA
AU - Tatsuya AKUTSU
PY - 2010
DO - 10.1587/transfun.E93.A.1497
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E93-A
IS - 8
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - August 2010
AB - 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)
ER -
English
