- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Feedback topology and XOR-dynamics in Boolean networks with varying input structure

L. Ciandrini1,*, C. Maffi2,†, A. Motta3, B. Bassetti3,4, and M. Cosentino Lagomarsino3,4,‡

  • 1Dip. di Fisica Nucleare e Teorica, Università di Pavia, Via Bassi 6, 27100 Pavia, Italy
  • 2Laboratoire de Biophysique Statistique, EPFL SB ITP, CH-1015 Lausanne, Switzerland
  • 3Dip. Fisica, Università degli Studi di Milano, Via Celoria 16, 20133 Milano, Italy
  • 4INFN, Via Celoria 16, 20133 Milano, Italy

  • *Present address: Institute for Complex Systems and Mathematical Biology, Kings College, University of Aberdeen, United Kingdom; l.ciandrini@abdn.ac.uk
  • †carlo.maffi@epfl.ch
  • ‡marco.cosentino-lagomarsino@unimi.it
PDF

Phys. Rev. E 80, 026122 – Published 21 August, 2009

DOI: https://doi.org/10.1103/PhysRevE.80.026122

Abstract

We analyze a model of fixed in-degree random Boolean networks in which the fraction of input-receiving nodes is controlled by the parameter γ. We investigate analytically and numerically the dynamics of graphs under a parallel XOR updating scheme. This scheme is interesting because it is accessible analytically and its phenomenology is at the same time under control and as rich as the one of general Boolean networks. We give analytical formulas for the dynamics on general graphs, showing that with a XOR-type evolution rule, dynamic features are direct consequences of the topological feedback structure, in analogy with the role of relevant components in Kauffman networks. Considering graphs with fixed in-degree, we characterize analytically and numerically the feedback regions using graph decimation algorithms (Leaf Removal). With varying γ, this graph ensemble shows a phase transition that separates a treelike graph region from one in which feedback components emerge. Networks near the transition point have feedback components made of disjoint loops, in which each node has exactly one incoming and one outgoing link. Using this fact, we provide analytical estimates of the maximum period starting from topological considerations.

View figure in article

Article Text

References (47)

  1. A. L. Barabasi and Z. N. Oltvai, Nat. Rev. Genet. 5, 101 (2004).
  2. U. Alon, Science 301, 1866 (2003).
  3. L. H. Hartwell, J. J. Hopfield, S. Leibler, and A. W. Murray, Nature (London) 402, C47 (1999).
  4. D. Bray, Science 301, 1864 (2003).
  5. Z. N. Oltvai and A. L. Barabasi, Science 298, 763 (2002).
  6. T. I. Lee et al., Science 298, 799 (2002).
  7. M. Babu, N. Luscombe, L. Aravind, M. Gerstein, and S. Teichmann, Curr. Opin. Struct. Biol. 14, 283 (2004).
  8. R. Thomas, J. Theor. Biol. 42, 563 (1973).
  9. S. A. Kauffman, The Origins of Order: Self-Organization and Selection in Evolution (Oxford University Press, New York, 1993).
  10. N. Guelzim, S. Bottani, P. Bourgine, and F. Képès, Nat. Genet. 31, 60 (2002).
  11. M. Isalan, C. Lemerle, K. Michalodimitrakis, C. Horn, P. Beltrao, E. Raineri, M. Garriga-Canut, and L. Serrano, Nature (London) 452, 840 (2008).
  12. S. A. Kauffman, J. Theor. Biol. 22, 437 (1969).
  13. C. Gershenson, in Workshop and Tutorial Proceedings, 9th International Conference on the Simulation and Synthesis of Living Systems (Artificial Life IX), edited by M. Bedau, P. Husbands, T. Hutton, S. Kumar, and H. Suzuki (MIT Press, Cambridge, MA, 2004), pp. 160–173.
  14. M. Aldana, S. Coppersmith, and L. P. Kadanoff, in Perspectives and Problems in Nonlinear Science: A Celebratory Volume in Honor of Lawrence Sirovich, Springer Applied Mathematical Science Series, edited by E. Kaplan, J. E. Mardsen, and K. R. Sreenivasan (Springer, New York, 2003), pp. 23–89.
  15. B. Drossel, in Reviews of Nonlinear Dynamics and Complexity, edited by H. Schuster (Wiley, New York, 2008), Vol. 1.
  16. A. S. Ribeiro and S. A. Kauffman, J. Theor. Biol. 247, 743 (2007).
  17. U. Bastolla and G. Parisi, J. Theor. Biol. 187, 117 (1997).
  18. A. S. N. Seshasayee, P. Bertone, G. M. Fraser, and N. M. Luscombe, Curr. Opin. Microbiol. 9, 511 (2006).
  19. N. M. Luscombe, Nature (London) 431, 308 (2004).
  20. S. Balaji, M. Madan Babu, and L. Aravind, J. Mol. Biol. 372, 1108 (2007).
  21. U. Paul, V. Kaufman, and B. Drossel, Phys. Rev. E 73, 026118 (2006).
  22. B. Samuelsson and C. Troein, Phys. Rev. Lett. 90, 098701 (2003).
  23. B. Drossel, Phys. Rev. E 72, 016110 (2005).
  24. M. C. Lagomarsino, P. Jona, and B. Bassetti, Phys. Rev. Lett. 95, 158701 (2005).
  25. L. Correale, M. Leone, A. Pagnani, M. Weigt, and R. Zecchina, J. Stat. Mech.: Theory Exp. (2006), P03002.
  26. L. Correale, M. Leone, A. Pagnani, M. Weigt, and R. Zecchina, Phys. Rev. Lett. 96, 018101 (2006).
  27. M. Cosentino Lagomarsino, P. Jona, and B. Bassetti, Proceedings of the CMSB Conference, Lecture Notes in Bioinformatics (Springer, New York, 2006).
  28. V. F. Kolchin, Random Graphs (Cambridge University Press, New York, 1998).
  29. S. Caracciolo and A. Sportiello, J. Phys. A 35, 7661 (2002).
  30. T. Mihaljev and B. Drossel, Phys. Rev. E 74, 046101 (2006).
  31. M. Mézard, G. Parisi, and M. Virasoro, Spin Glass Theory and Beyond, World Scientific Lecture Notes in Physics (World Scientific, Singapore, 1987).
  32. M. Mézard, F. Ricci-Tersenghi, and R. Zecchina, J. Stat. Phys. 111, 505 (2003).
  33. H. Flyvbjerg and M. Kjaer, J. Phys. A 21, 1695 (1988).
  34. S. Bilke and F. Sjunnesson, Phys. Rev. E 65, 016129 (2001).
  35. M. Andrecut and S. A. Kauffman, Phys. Lett. A 372, 4757 (2008).
  36. M. Bauer and O. Golinelli, Eur. Phys. J. B 24, 339 (2001).
  37. M. Weigt, Eur. Phys. J. B 28, 369 (2002).
  38. C. Maffi, Master thesis, Università degli studi di Milano, 2006.
  39. J. E. S. Socolar and S. A. Kauffman, Phys. Rev. Lett. 90, 068702 (2003).
  40. V. Kaufman and B. Drossel, New J. Phys. 8, 228 (2006).
  41. P. Krawitz and I. Shmulevich, Phys. Rev. E 76, 036115 (2007).
  42. U. Bastolla and G. Parisi, Physica D 115, 203 (1998).
  43. U. Bastolla and G. Parisi, Physica D 115, 219 (1998).
  44. V. Kaufman, T. Mihaljev, and B. Drossel, Phys. Rev. E 72, 046124 (2005).
  45. F. Bassetti, M. Cosentino Lagomarsino, B. Bassetti, and P. Jona, Phys. Rev. E 75, 056109 (2007).
  46. This is the in connectivity, which remains constant as removal does not affect in distribution pn. The reverse will be true for LRd.
  47. We call loop as the topological chains reserving the term cycle to the dynamics.

Outline

Information

Phys. Rev. E 80, 026122– Published 21 August, 2009
  • Received 11 September 2008

© 2009 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation