On Distribution and Enumeration of Attractors in Probabilistic Boolean Networks

摘要

In this paper, we study attractors in Probabilistic Boolean Networks (PBNs). We study the expected number of singleton attractors in a PBN and show that it is 1.5n if the number of Boolean functions assigned to each node is 2, where n is the number of nodes in a PBN. Then,we present algorithms for identifying singleton and small attractors and perform both theoretical and computational analyses on their average case time complexities. The results of computational experiments suggest that thcsc algorithms are much more efficient than the naive algorithm that examines all possible 2n states. We also show a simple and interesting relation between the distribution of attractors in a BN and the steady-state distribution in a corresponding variant of a PBN.