User:Inman Harvey/Proposed/Neutral networks

• Dr. Inman Harvey, EASy Group, Informatics, University of Sussex

The dynamics of evolutionary change in biology, and of search in evolutionary optimization, can be visualized as a population climbing the peaks of a fitness landscape, where height represents fitness.

Figure 1: Traditional picture of a fitness landscape without neutrality

Genetic changes such as mutations are visualized much as movements north-south or east-west on a 2-dimensional geographical map, but scaled up to a dimensionality corresponding to the number of genes. Some fitness landscapes may contain 'ridges' or level connected pathways of the same fitness -- connected via single potential mutations -- and these are Neutral Networks. If such Neutral Networks percolate widely through a fitness landscape, they can transform the evolutionary dynamics. Populations can escape what otherwise might have been local optima by random genetic drift, thus giving opportunities for chancing upon portals to regions of higher fitness.

Figure 2: A fitness landscape with neutrality: red 'portals' offer access between 3 neutral networks

Biologists analyse the extent to which Neutral Networks may or may not exist in practice to any significant extent in the fitness landscapes implicit in biological systems under natural selection. At the smaller end of the scale, RNA Neutral Networks correspond to those mutations at base-level that do not affect the shapes that the RNA folds into, and hence do not affect their function or fitness (Schuster et al 1994). At the larger end of the scale, looking at macro-evolution,all possible genotypes associated with a viable species can be allocated a nominal fitness of one, and all nonviable genotypes a nominal fitness of zero;this gives a `holey adaptive landscape` on which to visualise possible micro-evolutionary pathways (Gavrilets 2004).

Formal investigations of Neutral Networks study the dynamics of evolution on abstract fitness landscapes that include varying degrees of neutrality: how does neutrality relate to measures of ruggedness (Barnett 2001)? What is the expected waiting time traversing a ridge before finding a portal to a fitter region (van Nimwegen et al, 1999, 2000)?

Practitioners of evolutionary computation are interested in analysing the extent to which neutral networks may or may not exist in practice in the fitness landscapes implicit in the problems where they are trying to optimise some function. There is evidence that in many difficult real problems neutral networks are very significant, and this has implications for how one should best design an evolutionary algorithm (Thompson and Harvey 1996).

Biological Relevance

An early foretaste of neutral networks was given by Maynard Smith's 1970 introduction of the "Concept of a Protein Space". He uses an analogy between proteins and words in a word game; the letters represent amino-acids, and meaningful words correspond to functional proteins. "If evolution by natural selection is to occur, functional proteins must form a continuous network which can be traversed by unit mutational steps without passing through nonfunctional intermediates". In the analogy, although there are many meaningless mutations of the word WORD, there is also a pathway through single meaningful steps from WORD to GENE -- WORD-WORE-GORE-GONE-GENE.

Figure 3: Meaningful words correspond to functional proteins, on a neutral network; meaningless words form a different neutral network.

If each meaningful word (functional protein) has one or more meaningful mutant neighbours, then the resultant network makes possible evolution by natural selection. This is what we would nowadays call a neutral network, if we classify all the meaningful words as equally fit; the meaningless words form a different neutral network at zero fitness.

The term "neutral networks" was introduced by Schuster and colleagues analysing RNA evolution (Schuster 1992), and can be related to the quasi-species model. RNA molecules are strings of bases (A,U,G,C) that define a sequence space, with a metric based on Hamming distance; one can also consider shape space, for instance the secondary structure of RNA, in terms of stacks (paired complementary sections of RNA)loops (between stacks) and free ends.there are far less shapes than sequences. Models of secondary structure show that there are neutral networks percolating through shape space; paths connected in sequence space by single mutations, but neutral in the sense that all points on such a path fold to the same secondary structure. this percolation property shows that 'the problem of evolution is tractable'. Schuster (1992): "The numbers of sequences that have to be searched in order to find adequate solutions in adaptive evolution are many orders of magnitude smaller than those guessed on naive statistical grounds. In the absence of selected differences populations drift readily through sequence space, since long neutral paths are common. This is in essence what is predicted by the "neutral theory of evolution", and what is often observed in molecular phylogeny by sequence comparison of different organisms."

At a different end of the spectrum, Gavrilets considers macro-evolution of many organisms (and hence many species) by attributing fitnesses of 1 or 0, viable or nonviable, to all possible genotypes. Much as with Maynard Smith's protein space, this produces just two neutral networks, at different levels. This introduces the notion of a holey landscape, where relatively infrequent high-fitness genotypes former network across genotypes space; for many purposes it is practical to consider the high fitness is within a narrow fitness band to be all the same, and evolution along a holey landscape is nearly neutral.

Formal Studies

Neutral networks become significant in abstract models of fitness landscapes when one factors in neutrality and high dimensionality.

Figure 4: Punctuated Equilibria in fitness over generations

Evolutionary dynamics on such landscapes typically demonstrate punctuated equilibria; when tracking over many generations of evolutionary time the fittest member of the population (or the population average) there will be long periods of stasis, punctuated by jumps through a 'portal' to a higher neutral network. Such periods of fitness stasis may well hide mask significant amounts of genotypic change, through neutral drift.

A simple early such model was the Royal Road in Genetic Algorithms

References

Barnett, L. (2001). Netcrawling - optimal evolutionary search with neutral networks. In Proceedings of the 2001 Congress on Evolutionary Computation CEC2001 (pp. 30-37). IEEE Press. http://citeseer.ist.psu.edu/386127.html

Barnett, L. (2003). Evolutionary search on fitness landscapes with neutral networks. DPhil thesis, University of Sussex. http://tinyurl.com/zwyrx

Gavrilets, S., 2004. "Fitness Landscapes and the Origin of Species", Princeton University Press, Monographs in Population Biology vol 41.

Harvey, I. and Thompson, A, (1996). Through the Labyrinth Evolution Finds a Way: A Silicon Ridge. In Evolvable Systems : From Biology to Hardware, T. Higuchi, M. Iwata, and L. Weixin (eds.). Proc. of The First International Conference on Evolvable Systems: From Biology to Hardware (ICES96). Springer-Verlag 1996. ISBN: 3540631739 http://citeseer.ist.psu.edu/harvey96through.html

Maynard Smith, J., 1970. Natural selection and the concept of protein space. Nature 225, pp. 563–564.

Schuster, P., Fontana, W., Stadler, P.F., Hofacker, I.L. (1994). From Sequences to Shapes and Back: A Case Study in RNA Secondary Structures. Proc. Roy. Soc. Lond. B 255, 279-284.

van Nimwegen, E., Crutchfield, J.P. and Huynen, M. (1999). Neutral Evolution of Mutational Robustness. PNAS 96:9716-9720. http://www.pnas.org/cgi/content/abstract/96/17/9716

van Nimwegen, E., and Crutchfield, J.P. (Sep 2000). Metastable Evolutionary Dynamics: Crossing Fitness Barriers or Escaping via Neutral Paths? Bulletin of Mathematical Biology 62:5:799-848. http://xxx.uni-augsburg.de/abs/adap-org/9907002

Reidys, C., Forst, C.V., and Schuster, P. (2001) Replication and Mutation on Neutral Networks, Bull. Math. Biol., Volume 63, Number 1, January 2001 , pp. 57-94(38). Santa Fe Institute Preprint 98-04-036 http://www.tbi.univie.ac.at/~pks/PUBL/00-pks-008.pdf

Vassilev, V.K., and Miller, J.F. The Advantages of Landscape Neutrality in Digital Circuit Evolution (2000) In Proceedings of ICES 2000. Evolvable Systems: From Biology to Hardware, Edinburgh, Scotland. Pages 252-263. http://citeseer.ist.psu.edu/275641.html

See also

Neural networks