期刊
IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS
卷 9, 期 5, 页码 1410-1421出版社
IEEE COMPUTER SOC
DOI: 10.1109/TCBB.2012.87
关键词
Boolean network; periodic attractor; SAT; nested canalyzing function; treewidth
类别
资金
- MEXT, Japan [22650045]
- JSPS Invitation Fellowship Program for Research in Japan (Short Term)
- JSPS, Japan [23700017]
- Grants-in-Aid for Scientific Research [23700017, 22650045] Funding Source: KAKEN
In this paper, we study the problem of finding a periodic attractor of a Boolean network (BN), which arises in computational systems biology and is known to be NP-hard. Since a general case is quite hard to solve, we consider special but biologically important subclasses of BNs. For finding an attractor of period 2 of n BN consisting of n OR functions of positive literals, we present a polynomial time algorithm. For finding an attractor of period 2 of n BN consisting of n AND/OR functions of literals, we present an O(1.985(n)) time algorithm. For finding an attractor of a fixed period of n BN consisting of n nested canalyzing functions and having constant treewidth w, we present an O(n(2p(w+1))poly(n)) time algorithm.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据