ダウンロード数: 329
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
cmb.2010.0281.pdf | 168.49 kB | Adobe PDF | 見る/開く |
タイトル: | Determining a singleton attractor of a boolean network with nested canalyzing functions. |
著者: | Akutsu, Tatsuya https://orcid.org/0000-0001-9763-797X (unconfirmed) Melkman, Avraham A Tamura, Takeyuki https://orcid.org/0000-0003-1596-901X (unconfirmed) Yamamoto, Masaki |
著者名の別形: | 阿久津, 達也 |
キーワード: | SAT Boolean network singleton attractor nested canalyzing function |
発行日: | Sep-2011 |
出版者: | Mary Ann Liebert |
誌名: | Journal of computational biology : a journal of computational molecular cell biology |
巻: | 18 |
号: | 10 |
開始ページ: | 1275 |
終了ページ: | 1290 |
抄録: | In this article, we study the problem of finding a singleton attractor for several biologically important subclasses of Boolean networks (BNs). The problem of finding a singleton attractor in a BN is known to be NP-hard in general. For BNs consisting of n nested canalyzing functions, we present an O(1.799(n)) time algorithm. The core part of this development is an O(min(2(k/2) · 2(m/2), 2(k)) · poly(k, m)) time algorithm for the satisfiability problem for m nested canalyzing functions over k variables. For BNs consisting of chain functions, a subclass of nested canalyzing functions, we present an O(1.619(n)) time algorithm and show that the problem remains NP-hard, even though the satisfiability problem for m chain functions over k variables is solvable in polynomial time. Finally, we present an o(2(n)) time algorithm for bounded degree BNs consisting of canalyzing functions. |
著作権等: | ©2011 Mary Ann Liebert, Inc. publishers. "Journal of computational biology : a journal of computational molecular cell biology" is available online at: http://online.liebertpub.com. This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 |
URI: | http://hdl.handle.net/2433/149246 |
DOI(出版社版): | 10.1089/cmb.2010.0281 |
PubMed ID: | 21554129 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。