Biological SystemsNo Access

FINDING ATTRACTORS IN ASYNCHRONOUS BOOLEAN DYNAMICS

THOMAS SKODAWESSELY

Bioinformatics Group, Institute for Computer Science, Leipzig University, Härtelstrasse 16-18, 04107 Leipzig, Germany

Search for more papers by this author

and

KONSTANTIN KLEMM

Bioinformatics Group, Institute for Computer Science, Leipzig University, Härtelstrasse 16-18, 04107 Leipzig, Germany

Search for more papers by this author

https://doi.org/10.1142/S0219525911003098Cited by:19 (Source: Crossref)

Abstract

We present a computational method for finding attractors (ergodic sets of states) of Boolean networks under asynchronous update. The approach is based on a systematic removal of state transitions to render the state transition graph acyclic. In this reduced state transition graph, all attractors are fixed points that can be enumerated with little effort in most instances. This attractor set is then extended to the attractor set of the original dynamics. Our numerical tests on standard Kauffman networks indicate that the method is efficient in the sense that the total number of state vectors visited grows moderately with the number of states contained in attractors.

Keywords:

References

R. Albert and A.-L. Barabási, Phys. Rev. Lett. 84, 5660 (2000), DOI: 10.1103/PhysRevLett.84.5660. Web of Science, Google Scholar
R. Albert and H. G. Othmer, J. Theor. Biol. 223, 1 (2003), DOI: 10.1016/S0022-5193(03)00035-3. Web of Science, Google Scholar
F. Ay, F. Xu and T. Kahveci, PLoS ONE 4, e7992 (2009), DOI: 10.1371/journal.pone.0007992. Web of Science, Google Scholar
S. Bilke and F. Sjunnesson, Phys. Rev. E 65, 016129 (2001), DOI: 10.1103/PhysRevE.65.016129. Web of Science, Google Scholar
S. Bornholdt, Science 310, 449 (2005), DOI: 10.1126/science.1119959. Web of Science, Google Scholar
M. I. Davidich and S. Bornholdt, PLoS ONE 3, e1672 (2008), DOI: 10.1371/journal.pone.0001672. Web of Science, Google Scholar
H. de Jeong, J. Comput. Biol. 9, 67 (2002). Web of Science, Google Scholar
B. Drossel, Reviews of Nonlinear Dynamics and Complexity, Volume 1 (Wiley-VCH, 2008) pp. 69–99. Google Scholar
E. Dubrova and M. Teslenko, IEEE/ACM Transactions on Computational Biology and Bioinformatics 99, (2010). Google Scholar
M. R. Garey and D. S. Johnson , Computers and Intractability. A Guide to the Theory of NP-Completeness ( W. H. Freeman and Company , San Francisco , 1979 ) . Google Scholar
F. Greil and B. Drossel, Phys. Rev. Lett. 95, 048701 (2005), DOI: 10.1103/PhysRevLett.95.048701. Web of Science, Google Scholar
I. Harvey and T. Bossomaier, Time out of joint: Attractors in asynchronous random boolean networks, Proceedings of the Fourth European Conference on Artificial Life (ECAL97) (MIT Press, 1997) pp. 67–75. Google Scholar
D. J. Irons, Physica D 217, 7 (2006). Web of Science, Google Scholar
S. Kauffman, J. Theor. Biol. 22, 437 (1969). Web of Science, Google Scholar
S. A. Kauffman , The Origins of Order ( Oxford University Press , New York , 1993 ) . Crossref, Google Scholar
F. Liet al., Proc. Nat. Acad. Sci. U.S.A. 101, 4781 (2004), DOI: 10.1073/pnas.0305937101. Web of Science, Google Scholar
D. MacLean and D. J. Studholme, PLoS ONE 5, e9101 (2010), DOI: 10.1371/journal.pone.0009101. Web of Science, Google Scholar
M. Milano and A. Roli, Lect. Notes Comput. Sci. 1792, 72 (2000), DOI: 10.1007/3-540-46238-4_7. Google Scholar
C. L. Nehaniv, Int. J. Algebr. Comput. 14, 719 (2004). Link, Web of Science, Google Scholar
A. S. Ribeiro and S. A. Kauffman, J. Theor. Biol. 247, 743 (2007), DOI: 10.1016/j.jtbi.2007.04.020. Web of Science, Google Scholar
K. A. Richardson, Adv. Complex Syst. 8, 365 (2005). Link, Web of Science, Google Scholar
B. Samuelsson and C. Troein, Phys. Rev. Lett. 90, 098701 (2003), DOI: 10.1103/PhysRevLett.90.098701. Web of Science, Google Scholar
A. Shreimet al., Phys. Rev. E 82, 035102 (2010), DOI: 10.1103/PhysRevE.82.035102. Web of Science, Google Scholar
S. Zhanget al., EURASIP Journal on Bioinformatics and Systems Biology 20180 (2007). Google Scholar