Determining a singleton attractor of a boolean network with nested canalyzing functions.

HANDLE 被引用文献1件 オープンアクセス

抄録

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.

収録刊行物

被引用文献 (1)*注記

もっと見る

キーワード

詳細情報 詳細情報について

  • CRID
    1050845760653717632
  • NII論文ID
    120003517916
  • ISSN
    15578666
  • HANDLE
    2433/149246
  • 本文言語コード
    en
  • 資料種別
    journal article
  • データソース種別
    • IRDB
    • CiNii Articles

問題の指摘

ページトップへ