Rugged landscape

Fig. 11.12 Three sample fitness landscapes (a) has a single smooth maximum, (b) has many equivalent local maxima and one global maximum, but is circularly symmetric (c.) has many irregularly spaced local maxima, and is a good example of a rugged landscape.

Levinthal, D. 1997. Adaptation on rugged landscapes. Management Science, 43 934-950. 

In management science, use of rugged landscape models has been brought to bear on questions concerning the adaptability of organizations, optimal organizational structure, the co-evolution of organizations, and further topics. 

Eisen, H.N. (1989). Affinity maturation a retrospective view. In Molecular evolution on rugged landscapes proteins, RNA and the immune system (Perelson, A.S. Kauffman, A.A., Eds.), pp. 75-82. Addison Wesley, Redwood City. 

REM landscapes have been applied to the maturation of the immune system. When exposed to a new antigen, antibodies undergo on average only 6-10 point mutations in the course of achieving typically a 50-100-fold increase in affinity [70,71], Such short walks from random initial points to local peaks occur in rugged landscapes. The short walks and only modest affinity increase can be interpreted to indicate that the antibody affinity landscape is essentially uncorrelated [14,71,81,91], However, because there is such... 

Fig. 15. Example of frustration in an NK fitness landscape model. The tables list the fitness contributions for sites 3 and 4 as a function of their K = 2 epistatic inputs and their own values. The highest fitness contribution for fi requires [a2.a,.a4] =[1,0,0], while for f4 it requires [a3,a4,a5]= [1,0,1]. These two constraints cannot be mutually satisfied, leading to frustration. As K increases, the number of such conflicts rises and results in an increasingly rugged landscape whose peaks are of increasingly lower average fitness.

Fig. 4. The role of neutral networks in evolutionary optimization through adaptive walks and random drift. Adaptive walks allow to choose the next step arbitrarily from all directions where fitness is (locally) nondecreasing. Populations can bridge over narrow valleys with widths of a few point mutations. In the absence of selective neutrality (upper part) they are, however, unable to span larger Hamming distances and thus will approach only the next major fitness peak. Populations on rugged landscapes with extended neutral networks evolve along the network by a combination of adaptive walks and random drift at constant fitness (lower part). In this manner, populations bridge over large valleys and may eventually reach the global maximum ofthe fitness landscape.

Fig. 4. Smooth and rugged landscapes, (a) In a smooth landscape, adjacent sequences have similar fitness, (b) In a rugged landscape, adjacent sequences do not have similar fitness.

The correlation of the landscape measures the fitness similarity between a sequence and its d-mutant neighbors, where d is the number of mutations. As a sequence accumulates mutations, the fitness is increasingly altered. On smooth landscapes, the rate of fitness change is slow and therefore the landscape is correlated. Conversely, on rugged landscapes, the rate is more rapid and the landscape is uncorrelated. Studies of the relationship between fitness and distance have been used to quantitate the correlation among population ensembles on the RNA landscape (Fontana and Shuster, 1987), recombination dynamics (Born-holdt, 1998), and the success of genetic algorithms (Manderick et al., 1991 Jones and Forrest, 1995). 

In the IVK-model, as K increases, the number of fitter neighbors decreases more quickly as the sequence becomes more optimized (Kauffman and Weinberger, 1989). Thus, in order to discover improved mutants, the number of mutants screened has to increase more rapidly on random landscapes as the sequence increases in fitness (Fig. 4). The rate of decrease for the number of uphill paths is greater for rugged landscapes due to the shortening of the walk length to local optima. This implies that a protein that is tolerant (a smoother landscape) can undergo more rounds of mutation and improvement. 

Fig. 12. The average number of mutations tried at a suboptimal fitness plotted versus the fitness for the case D = AN = 1500, where A is the alphabet size and AT is the sequence length. Note the rapid increase in the number of required trials when the sequence reaches the inner boundary region. The line is generated analytically under the assumption of the random energy landscape. Reprinted with permission from Macken, C. A., Hagen, P. S., and Perelson, A. S., Evolutionary Walks on Rugged Landscapes, SIAM J. Appl. Math., 51 (1991), p. 821. Copyright 1991 by the Society for Industrial and Applied Mathematics. All rights reserved.

Theoretical study of the A -body system now focuses on the 0 hypersurface topography, or, more colloquially, its rugged landscape. Specific landscape characteristics of interest are the number of minima and their distribution and the nature of saddle points (transition states) throughout the landscape. A schematic illustration of an energy landscape is shown in Fig. 6 (Stillinger, 1995). 

The degree of complexity in the interactions between the amino acids is parameterized by the value of K. Low values of K lead to figure-of-merit landscapes upon which evolution is easy, and high values of K lead to extremely rugged landscapes upon which evolution is difficult. Combinatorial... 

Kauffman, S., and Levin, S., Towards a general theory of adaptive walks on rugged landscapes. J. Theor. Biol. 128,11-45 (1987). "... 

First predicted by R. A Fisher in The Genetical Theory of Natural Selection. Oxford Oxford University Press (1930). For recent empirical corroboration, see, for example, C. Burch and L. Chao. Evolution by small steps and rugged landscapes in the RNA virus phi6. Genetics, 151 (1999), 921-7. 

The elastic band method has been applied with remarkable success.63,64 However, it cannot be applied to problems that have rugged energy landscapes, like proteins. Recently, a similar method has been developed, that was designed to be applicable to rugged landscape systems. It is called the finite-temperature string method .65... 

---