文献

J-GLOBAL ID：201502239571791090   整理番号：15A0194664

有界ツリー幅を有するAND/OR Booleネットワークにおけるシングルトンアトラクタを検出するための固定パラメータアルゴリズム

A Fixed-Parameter Algorithm for Detecting a Singleton Attractor in an AND/OR Boolean Network with Bounded Treewidth

著者 (5件)： CHANG Chia-jung (Dep. of Computer Sci. and Information Engineering, National Taiwan Univ.) ,  TAMURA Takeyuki (Bioinformatics Center, Inst. for Chemical Res., Kyoto Univ.) ,  CHAO Kun-mao (Dep. of Computer Sci. and Information Engineering, National Taiwan Univ.) ,  CHAO Kun-mao (Graduate Inst. of Biomedical Electronics and Bioinformatics, National Taiwan Univ.) ,  AKUTSU Tatsuya (Bioinformatics Center, Inst. for Chemical Res., Kyoto Univ.)
資料名： IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Web)  (IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Web))
巻： E98.A  号： 1  ページ： 384-390 (J-STAGE)  発行年： 2015年 
JST資料番号： U0466A  ISSN： 1745-1337  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： Booleネットワークは遺伝子調節ネットワークのための数学モデルとして使用可能である。自身を周期的に反復するBooleネットワークの状態であるアトラクタは遺伝子調節ネットワークの安定ステージを表現可能である。最短周期のアトラクタを発見する問題はNP困難であると知られている。本論文では,文字のANDおよびOR Boole関数のみを有し,有界ツリー幅kを有するBooleネットワークのためのシングルトンアトラクタ(SA)を検出する固定パラメータアルゴリズムを与える。アルゴリズムを更に拡張し,有界ツリー幅を有するBooleネットワークを一定の深さの入れ子で方向づけるSAを検出する。また,有界ツリー幅を有する一般的BooleネットワークのSAの検出の固定パラメータ取り扱いにくさも証明する。(翻訳著者抄録)

シソーラス用語： *幅 ,  *グラフ理論 ,  境界 ,  木【グラフ】 ,  *Boole関数 ,  アルゴリズム ,  遺伝子 ,  NP困難
準シソーラス用語： *有界ツリー幅

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

引用文献 (14件)：

• [1] T. Akutsu, S. Kosub, A.A. Melkman, and T. Tamura, “Finding a periodic attractor of a Boolean network,” IEEE/ACM Trans. Computational Biology and Bioinformatics, vol.9, pp.151-160, 2012.
• [2] J. Chen, B. Chor, M. Fellows, X. Huang, D. Juedes, I. Kanj, and G. Xia, “Tight lower bounds for certain parameterized NP-hard problems,” Proc. 19th IEEE Annual Conference on Computational Complexity, pp.150-160, 2004.
• [3] V. Devloo, P. Hansen, and M. Labbé, “Identification of all steady states in large networks by logical analysis,” Bulletin of Mathematical Biology, vol.65, pp.1025-1051, 2003.
• [4] E. Dubrova and M. Teslenko, “A SAT-based algorithm for finding attractors in synchronous Boolean networks,” IEEE/ACM Trans. Computational Biology and Bioinformatics, vol.8, pp.1393-1398, 2011.
• [5] J. Flum and M. Grohe, Parameterized Complexity Theory, Springer, 2006.

タイトルに関連する用語 (4件)： 有界ツリー幅 ,  Booleネットワーク ,  パラメータ ,  アルゴリズム