Compositional properties of random Boolean networks
2005 (English)In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, Vol. 71, no 5, 056116- p.Article in journal (Refereed) Published
Random Boolean networks (RBNs) are used in a number of applications, including cell differentiation, immune response, evolution, gene regulatory networks, and neural networks. This paper addresses the problem of computing attractors in RBNs. An RBN with n vertices has up to 2(n) states. Therefore, for large n, computing attractors by full enumeration of states is not feasible. The state space can be reduced by removing irrelevant vertices, which have no influence on the network's dynamics. In this paper, we show that attractors of an RBN can be computed compositionally from the attractors of the independent components of the subgraph induced by the relevant vertices of the network. The presented approach reduces the complexity of the problem from O(2(n)) to O(2(l)), where l is the number of relevant vertices in the largest component.
Place, publisher, year, edition, pages
2005. Vol. 71, no 5, 056116- p.
kauffman networks, automata
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-15020DOI: 10.1103/PhysRevE.71.056116ISI: 000231688300028ScopusID: 2-s2.0-26944502278OAI: oai:DiVA.org:kth-15020DiVA: diva2:333061
QC 201209262010-08-052010-08-052012-09-26Bibliographically approved