Evolving specific network statistical properties using a gene regulatory network model

ABSTRACT

The generation of network topologies with specific, user-specified statistical properties is addressed using an Evolutionary Algorithm that is seeded by an Artificial Gene Regulatory Network Model. The work presented here extends previous work where the proposed approach was demonstrated to be able to evolve scale-free topologies. The present results reinforce the applicability of the proposed method, showing that the evolution of small-world topologies is also possible, but requires a carefully crafted fitness function.

REFERENCES

• 1: M. M. Babu, N. M. Luscombe, L. Aravind, M. Gerstein, and S. A. Teichmann. Structure and evolution of transcriptional regulatory networks. Current Opinion in Structural Biology, <b> 14:283--292, 2004.
• 2: W. Banzhaf. Artificial regulatory networks and genetic programming. In R. Riolo and B. Worzel, editors, Genetic Programming Theory and Practice, chapter 4, pages 43--62. Kluwer Publishers, 2003.
• 3: A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509--512, 1999.
• 4: S. N. Dorogovtsev , J. F. F. Mendes, Evolution of Networks: From Biological Nets to the Internet and WWW (Physics), Oxford University Press, Inc., New York, NY, 2003
• 5: Max Garzon, Models of massive parallelism: analysis of cellular automata and neural networks, Springer-Verlag, London, 1995
• 6: M. Giacobini, M. Preuss, and M. Tomassini. Effects of scale-free and small-world topologies on binary coded self-adaptive cea. In J. Gottlieb and G. R. Raidl, editors, Proc. Evolutionary Computation in Combinatorial Optimization, 6th European Conference, EvoCOP, volume 3906 of LNCS, pages 86--98. Springer, 2006.
• 7: Mario Giacobini , Marco Tomassini , Andrea Tettamanzi, Takeover time curves in random and small-world structured populations, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068224]
• 8: J. Guare. Six Degrees of Separation. Vintage, November 1990.
• 9: N. Guelzim, S. Bottani, P. Bourgine, and F. Képès. Topological and causal structure of the yeast transcriptional regulatory network. Nature Genetics, 31:60--63, 2002.
• 10: H. Jaeger. The echo state approach to analysing and training recurrent neural networks. Technical Report GMD Report 148, German National Research Center for Information Technology, 2001.
• 11: H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, and A.-L. Barabási. The large-scale organization of metabolic networks. Nature, 407:651--654, 2000.
• 12: Fei Jiang , Hugues Berry , Marc Schoenauer, Supervised and Evolutionary Learning of Echo State Networks, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_22]
• 13: P. D. Kuo, W. Banzhaf, and A. Leier. Network topology and the evolution of dynamics in an artificial regulatory network model created by whole genome duplication and divergence. Biosystems, 85(3):177--200, 2006.
• 14: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 15: M. Nicolau and M. Schoenauer. Evolving scale-free topologies using a gene regulatory network model. In Proc. IEEE Congress on Evolutionary Computation, CEC 2008, pages 3748--3755. IEEE Press, 2008.
• 16: R. Pastor-Satorras, E. Smith, and R. V. Solé. Evolving protein interaction networks through gene duplication. Theoretical Biology, 222:199--210, 2003.
• 17: Joshua L. Payne , Margaret J. Eppstein, Takeover times on scale-free topologies, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277018]
• 18: Joshua L. Payne , Margaret J. Eppstein, The influence of scaling and assortativity on takeover times in scale-free topologies, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389133]
• 19: I. Rechengerg. Evolutionsstrategie '94. Frommann-Holzboog, Stuttgart, 1994.
• 20: V. van Noort, B. Snel, and M. A. Huynen. The yeast coexpression network has a small-world, scale-free architecture and can be explained by a simple model. EMBO Reports, 5(3):280--284, 2004.
• 21: Duncan J. Watts, Small worlds: the dynamics of networks between order and randomness, Princeton University Press, Princeton, NJ, 1999
• 22: D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440--442, 1998.
• 23: K. Wolfe and D. Shields. Molecular evidence for an ancient duplication of the entire yeast genome. Nature, 387:708--713, 1997.
• 24: S. Wuchty. Scale-free behavior in protein domain networks. Molecular Biology and Evolution, 18:1694--1702, 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms

Keywords:
evolutionary computation, regulatory networks, small-world topology