Analyses and Algorithms for Predecessor and Control Problems for Boolean Networks of Bounded Indegree

• Item type: Trans(1)
• 公開日: 2008-11-28
• タイトル: Analyses and Algorithms for Predecessor and Control Problems for Boolean Networks of Bounded Indegree
• タイトル / 言語: en
• タイトル: Analyses and Algorithms for Predecessor and Control Problems for Boolean Networks of Bounded Indegree
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: Original Papers
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Bioinformatics Center Institute for Chemical Research Kyoto University
• 著者所属: Bioinformatics Center Institute for Chemical Research Kyoto University
• 著者所属: School of Mathematical Sciences Fudan University
• 著者所属: Department of Mathematics The University of Hong Kong
• 著者所属: Department of Mathematics Hong Kong Baptist University
• 著者所属(英): en
• 著者所属(英): Bioinformatics Center, Institute for Chemical Research, Kyoto University
• 著者所属(英): en
• 著者所属(英): Bioinformatics Center, Institute for Chemical Research, Kyoto University
• 著者所属(英): en
• 著者所属(英): School of Mathematical Sciences, Fudan University
• 著者所属(英): en
• 著者所属(英): Department of Mathematics, The University of Hong Kong
• 著者所属(英): en
• 著者所属(英): Department of Mathematics, Hong Kong Baptist University
• 著者名: Tatsuya, Akutsu; Morihiro, Hayashida; Shu-QinZhang; Wai-KiChing; MichaelK.Ng
• 著者名(英): Tatsuya, Akutsu; Morihiro, Hayashida; Shu, -QinZhang; Wai, -KiChing; Michael, K.Ng
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We study the predecessor and control problems for Boolean networks (BNs). The predecessor problem is to determine whether there exists a global state that transits to a given global state in a given BN and the control problem is to find a sequence of 0-1 vectors for control nodes in a given BN which leads the BN to a desired global state. The predecessor problem is useful both for the control problem for BNs and for analysis of landscape of basins of attractions in BNs. In this paper we focus on BNs of bounded indegree and show some hardness results on the computational complexity of the predecessor and control problems. We also present simple algorithms for the predecessor problem that are much faster than the naive exhaustive search-based algorithm. Furthermore we show some results on distribution of predecessors which leads to an improved algorithm for the control problem for BNs of bounded indegree.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We study the predecessor and control problems for Boolean networks (BNs). The predecessor problem is to determine whether there exists a global state that transits to a given global state in a given BN, and the control problem is to find a sequence of 0-1 vectors for control nodes in a given BN which leads the BN to a desired global state. The predecessor problem is useful both for the control problem for BNs and for analysis of landscape of basins of attractions in BNs. In this paper, we focus on BNs of bounded indegree and show some hardness results on the computational complexity of the predecessor and control problems. We also present simple algorithms for the predecessor problem that are much faster than the naive exhaustive search-based algorithm. Furthermore, we show some results on distribution of predecessors, which leads to an improved algorithm for the control problem for BNs of bounded indegree.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12177013
• 書誌情報: IPSJ Transactions on Bioinformatics （TBIO）; 巻 1, p. 23-34, 発行日 2008-11-28
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-6679
• 出版者 / 言語: ja
• 出版者: 情報処理学会