講演抄録/キーワード |
講演名 |
2007-05-25 13:20
AND/OR節点で構成されるブーリアンネットワークの定常状態を検出する$O(1.787^n)$時間アルゴリズム ○田村武幸・阿久津達也(京大) COMP2007-13 |
抄録 |
(和) |
ブーリアンネットワーク(BN)は遺伝子ネットワークの数学的モデルのひとつである.BNの定常状態を検出する問題はAND/OR BN,すなわちBNがAND/OR節点で構成される場合ですらNP困難であることが知られている.AND/OR BNの定常状態はナイーブなアルゴリズムを用いれば,$O(n2^n)$時間で検出することができるが,$O((2-\epsilon)^n)$ ($\epsilon>0$)時間のアルゴリズムは入次数が制限された場合にしか知られていない.ただし$n$はBNに含まれるノード数である.本稿では入次数に制限のないAND/OR BNの定常状態を検出する$O(1.787^n)$時間のアルゴリズムを紹介する. |
(英) |
The Boolean network (BN) is a mathematical model of genetic networks. It is known that detecting a singleton attractor is NP-hard even for AND/OR BNs (i.e., BNs consisting of AND/OR nodes), where singleton attractors correspond to steady states. Though a naive algorithm can detect a singleton attractor for an AND/OR BN in $O(n 2^n)$ time, no $O((2-\epsilon)^n)$ ($\epsilon > 0$) time algorithm was known even for an AND/OR BN with non-restricted indegree, where $n$ is the number of nodes in a BN. In this paper, we present an $O(1.787^n)$ time algorithm for detecting a singleton attractor of a given AND/OR BN. |
キーワード |
(和) |
ブーリアンネットワーク / 定常状態 / SAT / バイオインフォマティクス / アルゴリズム / / / |
(英) |
Boolean network / singleton attractor / SAT / bioinformatics / algorithm / / / |
文献情報 |
信学技報, vol. 107, no. 73, COMP2007-13, pp. 13-18, 2007年5月. |
資料番号 |
COMP2007-13 |
発行日 |
2007-05-18 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2007-13 |