論文

査読有り
2011年10月

Determining a Singleton Attractor of a Boolean Network with Nested Canalyzing Functions

JOURNAL OF COMPUTATIONAL BIOLOGY
  • Tatsuya Akutsu
  • ,
  • Avraham A. Melkman
  • ,
  • Takeyuki Tamura
  • ,
  • Masaki Yamamoto

18
10
開始ページ
1275
終了ページ
1290
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1089/cmb.2010.0281
出版者・発行元
MARY ANN LIEBERT INC

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.

リンク情報
DOI
https://doi.org/10.1089/cmb.2010.0281
DBLP
https://dblp.uni-trier.de/rec/journals/jcb/AkutsuMTY11
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000295079100001&DestApp=WOS_CPL
URL
http://dblp.uni-trier.de/db/journals/jcb/jcb18.html#journals/jcb/AkutsuMTY11
ID情報
  • DOI : 10.1089/cmb.2010.0281
  • ISSN : 1066-5277
  • DBLP ID : journals/jcb/AkutsuMTY11
  • Web of Science ID : WOS:000295079100001

エクスポート
BibTeX RIS