An O(1.787{sup}n)-time Algorithm for Detecting a Singleton Attractor in a Boolean Network Consisting of AND/OR Nodes

摘要

The Boolean network (BN) is a mathematical model of genetic networks. It is known that detecting a singleton attractor is NP-hard even for AND/OR BNs (i.e., BNs consisting of AND/OR nodes), where singleton attractors correspond to steady states. Though a naive algorithm can detect a singleton attractor for an AND/OR BN in O(n2{sup}n) time, no O((2-ε){sup}n) (ε>0) time algorithm was known even for an AND/OR BN with non-restricted indegree, where n is the number of nodes in a BN. In this paper, we present an O(1.787{sup}n) time algorithm for detecting a singleton attractor of a given AND/OR BN.