The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Um corte de reação é um conjunto de reações químicas cuja exclusão bloqueia a operação de determinadas reações ou a produção de determinados compostos químicos. Neste artigo, estudamos dois problemas ReactionCut e MD-ReactionCut para cálculo do corte mínimo de reação de uma rede metabólica sob um modelo booleano. Esses problemas são baseados no modelo de equilíbrio de fluxo e no modelo de dano mínimo, respectivamente. Mostramos que ReactionCut e MD-ReactionCut são NP-difíceis mesmo se o grau máximo de nós de reação (KFora) é um. Apresentamos também O(1.822n), O(1.959n) e o(2n) algoritmos de tempo para MD-ReactionCut com KFora=2, 3, k respectivamente onde n é o número de nós de reação e k é uma constante. Os mesmos algoritmos também funcionam para ReactionCut se não houver ciclo direcionado. Além disso, apresentamos um 2O((registro n)
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.
Copiar
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
Copiar
@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},}
Copiar
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 -