講演抄録/キーワード |
講演名 |
2009-10-16 14:50
代謝ネットワークの最小反応カットを求めるアルゴリズム ○田村武幸(京大)・竹本和広(東大)・阿久津達也(京大) COMP2009-36 |
抄録 |
(和) |
本稿において我々は,ブーリアンモデルの代謝ネットワークの最小反応カットを計算する2つのタイプの問題として,
ReactionCutとMD-ReactionCutを扱う.
これらの問題はそれぞれ,流束収支モデルと最小損傷モデルに基づいている.
我々は,ReactionCutとMD-ReactionCutが反応ノードの最大出次数($K_{out}$)が1の時でさえ
NP困難であることを示す.
また,MD-ReactionCutの$K_{out}=2, 3, k$のそれぞれに対し,
$O(1.822^n)$, $O(1.959^n)$, $o(2^n)$時間アルゴリズムを紹介する.
ただし,$n$は反応ノードの数であり,$k$は定数である.
これらのアルゴリズムは,ネットワークが閉路を含まなければ,
ReactionCutにも適用することができる. |
(英) |
In this article, we study two problems ReactionCut and MD-ReactionCut
for calculating minimum reaction cuts of a metabolic network under a Boolean model.
These problems are based on flux balance model and minimal damage model respectively.
We show that ReactionCut 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 ReactionCut if there is no cycle. |
キーワード |
(和) |
代謝ネットワーク / 反応カット / ブーリアンモデル / 堅牢性 / / / / |
(英) |
Metabolic network / Reaction cut / Boolean model / Robustness / / / / |
文献情報 |
信学技報, vol. 109, no. 235, COMP2009-36, pp. 27-34, 2009年10月. |
資料番号 |
COMP2009-36 |
発行日 |
2009-10-09 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2009-36 |