The NK model of rugged fitness landscapes and its application to maturation of the immune response

Adaptive evolution is, to a large extent, a complex combinatorial optimization process. Such processes can be characterized as "uphill walks on rugged fitness landscapes". Concrete examples of fitness landscapes include the distribution of any specific functional property such as the capacity to catalyze a specific reaction, or bind a specific ligand, in "protein space". In particular, the property might be the affinity of all possible antibody molecules for a specific antigenic determinant. That affinity landscape presumably plays a critical role in maturation of the immune response. In this process, hypermutation and clonal selection act to select antibody V region mutant variants with successively higher affinity for the immunizing antigen. The actual statistical structure of affinity landscapes, although knowable, is currently unknown. Here, we analyze a class of mathematical models we call NK models. We show that these models capture significant features of the maturation of the immune response, which is currently thought to share features with general protein evolution. The NK models have the important property that, as the parameter K increases, the "ruggedness" of the NK landscape varies from a single peaked "Fujiyama" landscape to a multi-peaked "badlands" landscape. Walks to local optima on such landscapes become shorter as K increases. This fact allows us to choose a value of K that corresponds to the experimentally observed number of mutational "steps", 6-8, taken as an antibody sequence matures. If the mature antibody is taken to correspond to a local optimum in the model, tuning the model requires that K be about 40, implying that the functional contribution of each amino acid in the V region is affected by about 40 others. Given this value of K, the model then predicts several features of "antibody space" that are in qualitative agreement with experiment: (1) The fraction of fitter variants of an initial "roughed in" germ line antibody amplified by clonal selection is about 1-2%. (2) Mutations at some sites of the mature antibody hardly affect antibody function at all, but mutations at other sites dramatically decrease function. (3) The same "roughed in" antibody sequence can "walk" to many mature antibody sequences. (4) Many adaptive walks can end on the same local optimum. (5) Comparison of different mature sequences derived from the same initial V region shows evolutionary hot spots and parallel mutations. All these predictions are open to detailed testing by obtaining monoclonal antibodies early in the immune response and carrying out in vitro mutagenesis and adaptive hill climbing with respect to affinity for the immunizing antigen.     

The population genetics of adaptation on correlated fitness landscapes: the block model

Several recent theoretical studies of the genetics of adaptation have focused on the mutational landscape model, which considers evolution on rugged fitness landscapes (i.e., ones having many local optima). Adaptation in this model is characterized by several simple results. Here I ask whether these results also hold on correlated fitness landscapes, which are smoother than those considered in the mutational landscape model. In particular, I study the genetics of adaptation in the block model, a tunably rugged model of fitness landscapes. Considering the scenario in which adaptation begins from a high fitness wild-type DNA sequence, I use extreme value theory and computer simulations to study both single adaptive steps and entire adaptive walks. I show that all previous results characterizing single steps in adaptation in the mutational landscape model hold at least approximately on correlated landscapes in the block model; many entire-walk results, however, do not.     

A sharp minimum on the mean number of steps taken in adaptive walks

It was recently conjectured by H.A. Orr that from a random initial point on a random fitness landscape of alphabetic sequences with one-mutation adjacency, chosen from a larger class of landscapes, no adaptive algorithm can arrive at a local optimum in fewer than on average e-1 steps. Here, using an example in which the mean number of steps to a local optimum equals (A-1)/A, where A is the number of distinct "letters" in the "alphabet" from which sequences are constructed, it is shown that as originally stated, the conjecture does not hold. It is also demonstrated that (A-1)/A is a sharp minimum on the mean number of steps taken in adaptive walks on fitness landscapes of alphabetic sequences with one-mutation adjacency. As the example that achieves the new lower bound has properties that are not often considered as potential attributes for fitness landscapes-non-identically distributed fitnesses and negative fitness correlations for adjacent points-a weaker set of conditions characteristic of more commonly studied fitness landscapes is proposed under which the lower bound on the mean length of adaptive walks is conjectured to equal e-1.     

Properties of adaptive walks on uncorrelated landscapes under strong selection and weak mutation

We examine properties of adaptive walks on uncorrelated (i.e. random) fitness landscapes starting from moderately fit genotypes under strong selection weak mutation. As an extension of Orr's model for a single step in an adaptive walk under these conditions, we show that the fitness rank of the dominant genotype in a population after the fixation of a beneficial mutation is, on average, (i+6)/4, where i is the fitness rank of the starting genotype. This accounts for the change in rank due to acquiring a new set of single-mutation neighbors after fixing a new allele through natural selection. Under this scenario, adaptive walks can be modeled as a simple Markov chain on the space of possible fitness ranks with an absorbing state at i = 1, from which no beneficial mutations are accessible. We find that these walks are typically short and are often completed in a single step when starting from a moderately fit genotype. As in Orr's original model, these results are insensitive to both the distribution of fitness effects and most biological details of the system under consideration.     

Combinatorial vector fields and the valley structure of fitness landscapes

Adaptive (downhill) walks are a computationally convenient way of analyzing the geometric structure of fitness landscapes. Their inherently stochastic nature has limited their mathematical analysis, however. Here we develop a framework that interprets adaptive walks as deterministic trajectories in combinatorial vector fields and in return associate these combinatorial vector fields with weights that measure their steepness across the landscape. We show that the combinatorial vector fields and their weights have a product structure that is governed by the neutrality of the landscape. This product structure makes practical computations feasible. The framework presented here also provides an alternative, and mathematically more convenient, way of defining notions of valleys, saddle points, and barriers in landscape. As an application, we propose a refined approximation for transition rates between macrostates that are associated with the valleys of the landscape.     

Random field models for fitness landscapes

 In many cases fitness landscapes are obtained as particular instances of random fields by randomly assigning a large number of parameters. Models of this type are often characterized reasonably well by their covariance matrices. We characterize isotropic random fields on finite graphs in terms of their Fourier series expansions and investigate the relation between the covariance matrix of the random field model and the correlation structure of the individual landscapes constructed from this random field. Correlation measures are a good characteristic of “rugged landscapes” models as they are closely related to quantities like the number of local optima or the length of adaptive walks. Our formalism suggests to approximate landscape with known autocorrelation function by a random field model that has the same correlation structure. Received: 10 November 1995 / Revised version: 19 February 1996     

Properties of selected mutations and genotypic landscapes under Fisher's geometric model

The fitness landscape—the mapping between genotypes and fitness—determines properties of the process of adaptation. Several small genotypic fitness landscapes have recently been built by selecting a handful of beneficial mutations and measuring fitness of all combinations of these mutations. Here, we generate several testable predictions for the properties of these small genotypic landscapes under Fisher's geometric model of adaptation. When the ancestral strain is far from the fitness optimum, we analytically compute the fitness effect of selected mutations and their epistatic interactions. Epistasis may be negative or positive on average depending on the distance of the ancestral genotype to the optimum and whether mutations were independently selected, or coselected in an adaptive walk. Simulations show that genotypic landscapes built from Fisher's model are very close to an additive landscape when the ancestral strain is far from the optimum. However, when it is close to the optimum, a large diversity of landscape with substantial roughness and sign epistasis emerged. Strikingly, small genotypic landscapes built from several replicate adaptive walks on the same underlying landscape were highly variable, suggesting that several realizations of small genotypic landscapes are needed to gain information about the underlying architecture of the fitness landscape.     

Deterministic and stochastic regimes of asexual evolution on rugged fitness landscapes

We study the adaptation dynamics of an initially maladapted asexual population with genotypes represented by binary sequences of length L. The population evolves in a maximally rugged fitness landscape with a large number of local optima. We find that whether the evolutionary trajectory is deterministic or stochastic depends on the effective mutational distance d(eff) up to which the population can spread in genotype space. For d(eff) = L, the deterministic quasi-species theory operates while for d(eff) < 1, the evolution is completely stochastic. Between these two limiting cases, the dynamics are described by a local quasi-species theory below a crossover time T(x) while above T(x) the population gets trapped at a local fitness peak and manages to find a better peak via either stochastic tunneling or double mutations. In the stochastic regime d(eff) < 1, we identify two subregimes associated with clonal interference and uphill adaptive walks, respectively. We argue that our findings are relevant to the interpretation of evolution experiments with microbial populations.     

Cover-Encodings of Fitness Landscapes

The traditional way of tackling discrete optimization problems is by using local search on suitably defined cost or fitness landscapes. Such approaches are however limited by the slowing down that occurs when the local minima that are a feature of the typically rugged landscapes encountered arrest the progress of the search process. Another way of tackling optimization problems is by the use of heuristic approximations to estimate a global cost minimum. Here, we present a combination of these two approaches by using cover-encoding maps which map processes from a larger search space to subsets of the original search space. The key idea is to construct cover-encoding maps with the help of suitable heuristics that single out near-optimal solutions and result in landscapes on the larger search space that no longer exhibit trapping local minima. We present cover-encoding maps for the problems of the traveling salesman, number partitioning, maximum matching and maximum clique; the practical feasibility of our method is demonstrated by simulations of adaptive walks on the corresponding encoded landscapes which find the global minima for these problems.     

Evolutionary optimization in multimodal search space

Optimization by a simple evolution strategy based on a mutation and selection scheme without recombination was tested for its efficiency in multimodal search space. A modified Rastrigin function served as an objective function providing fitness landscapes with many local optima. It turned out that the evolutionary algorithm including adaptive stepsize control is wellsuited for optimization. The process is able to efficiently surmount local energy barriers and converge to the global optimum. The relation between the optimization time available and the optimal number of offspring was investigated and a simple rule proposed. Several numbers of offspring are nearly equally suited in a smooth search space, whereas in rough fitness landscapes an optimum is observed. In either case both very large and very small numbers of offspring turned out to be unfavourable for optimization.     

Environmental fluctuations: How do they affect the topography of the adaptive landscape?

A Phenotypic Adaptive Landscape is defined with fitness as the ordinate, and longevity of the juvenile phase and duration of disturbances to the adult phase as the horizontal axes. The effect of local environmental perturbations on the landscape’s shape is studied using a semistochastic population model. In this model the intrinsic population dynamics takes the form of a differential-delay nonlinear equation and the environmental disturbance appears as a multiplicativetelegraphic noise. We demonstrate that the landscape has no single characteristic scale. Rather, it shows adaptive peaks corresponding to an integer relation between the biological and the environmental periodicities. Since the system is constrained by a finite time and a finite physiological range, the landscape may have different topographies for different local environmental regimes. A very simple fully deterministic model is presented, predicting landscapes that are similar to those obtained by the semistochastic model. Application to life history strategies are discussed.     

Reciprocal sign epistasis between frequently experimentally evolved adaptive mutations causes a rugged fitness landscape

The fitness landscape captures the relationship between genotype and evolutionary fitness and is a pervasive metaphor used to describe the possible evolutionary trajectories of adaptation. However, little is known about the actual shape of fitness landscapes, including whether valleys of low fitness create local fitness optima, acting as barriers to adaptive change. Here we provide evidence of a rugged molecular fitness landscape arising during an evolution experiment in an asexual population of Saccharomyces cerevisiae. We identify the mutations that arose during the evolution using whole-genome sequencing and use competitive fitness assays to describe the mutations individually responsible for adaptation. In addition, we find that a fitness valley between two adaptive mutations in the genes MTH1 and HXT6/HXT7 is caused by reciprocal sign epistasis, where the fitness cost of the double mutant prohibits the two mutations from being selected in the same genetic background. The constraint enforced by reciprocal sign epistasis causes the mutations to remain mutually exclusive during the experiment, even though adaptive mutations in these two genes occur several times in independent lineages during the experiment. Our results show that epistasis plays a key role during adaptation and that inter-genic interactions can act as barriers between adaptive solutions. These results also provide a new interpretation on the classic Dobzhansky-Muller model of reproductive isolation and display some surprising parallels with mutations in genes often associated with tumors.     

Adaptive walks by the fittest among finite random mutants on a Mt. Fuji-type fitness landscape II. Effect of small non-additivity

We examined properties of adaptive walks by the fittest on “rough Mt. Fuji-type” fitness landscapes, which are modeled by superposing small uncorrelated random component on an additive fitness landscape. A single adaptive walk is carried out by repetition of the evolution cycle composed of (1) mutagenesis process that produces random d-fold point mutants of population size N and (2) selection process that picks out the fittest mutant among them. To comprehend trajectories of the walkers, the fitness landscape is mapped into a (x, y, z)-space, where x, y and z represent, respectively, normalized Hamming distance from the peak on the additive fitness landscape, scaled additive fitness and scaled non-additive fitness. Thus a single adaptive walk is expressed as the dynamics of a particle in this space. We drew the “hill-climbing” vector field, where each vector represents the most probable step for a walker in a single step. Almost all of the walkers are expected to move along streams of vectors existing on a particular surface that overlies the (x, y)-plane, toward the neighborhood of a characteristic point at which a mutation-selection-random drift balance is reached. We could theoretically predict this reachable point in the case of random sampling search strategy. Received: 1 March 2000 / Published online: 3 August 2000     

Genome structure and the benefit of sex

We examine the behavior of sexual and asexual populations in modular multipeaked fitness landscapes and show that sexuals can systematically reach different, higher fitness adaptive peaks than asexuals. Whereas asexuals must move against selection to escape local optima, sexuals reach higher fitness peaks reliably because they create specific genetic variants that "skip over" fitness valleys, moving from peak to peak in the fitness landscape. This occurs because recombination can supply combinations of mutations in functional composites or "modules," that may include individually deleterious mutations. Thus when a beneficial module is substituted for another less-fit module by sexual recombination it provides a genetic variant that would require either several specific simultaneous mutations in an asexual population or a sequence of individual mutations some of which would be selected against. This effect requires modular genomes, such that subsets of strongly epistatic mutations are tightly physically linked. We argue that such a structure is provided simply by virtue of the fact that genomes contain many genes each containing many strongly epistatic nucleotides. We briefly discuss the connections with "building blocks" in the evolutionary computation literature. We conclude that there are conditions in which sexuals can systematically evolve high-fitness genotypes that are essentially unevolvable for asexuals.     

Thermodynamical interpretation of an adaptive walk on a Mt. Fuji-type fitness landscape: Einstein relation-like formula holds in a stochastic evolution

We have theoretically studied the statistical properties of adaptive walks (or hill-climbing) on a Mt. Fuji-type fitness landscape in the multi-dimensional sequence space through mathematical analysis and computer simulation. The adaptive walk is characterized by the "mutation distance" d as the step-width of the walker and the "population size" N as the number of randomly generated d-fold point mutants to be screened. In addition to the fitness W, we introduced the following quantities analogous to thermodynamical concepts: "free fitness" G(W) is identical with W+T x S(W), where T is the "evolutionary temperature" T infinity square root of d/lnN and S(W) is the entropy as a function of W, and the "evolutionary force" X is identical with d(G(W)/T)/dW, that is caused by the mutation and selection pressure. It is known that a single adaptive walker rapidly climbs on the fitness landscape up to the stationary state where a "mutation-selection-random drift balance" is kept. In our interpretation, the walker tends to the maximal free fitness state, driven by the evolutionary force X. Our major findings are as follows: First, near the stationary point W*, the "climbing rate" J as the expected fitness change per generation is described by J approximately L x X with L approximately V/2, where V is the variance of fitness distribution on a local landscape. This simple relationship is analogous to the well-known Einstein relation in Brownian motion. Second, the "biological information gain" (DeltaG/T) through adaptive walk can be described by combining the Shannon's information gain (DeltaS) and the "fitness information gain" (DeltaW/T).     

Evolutionary advantage of small populations on complex fitness landscapes

Recent experimental and theoretical studies have shown that small asexual populations evolving on complex fitness landscapes may achieve a higher fitness than large ones due to the increased heterogeneity of adaptive trajectories. Here, we introduce a class of haploid three-locus fitness landscapes that allow the investigation of this scenario in a precise and quantitative way. Our main result derived analytically shows how the probability of choosing the path of the largest initial fitness increase grows with the population size. This makes large populations more likely to get trapped at local fitness peaks and implies an advantage of small populations at intermediate time scales. The range of population sizes where this effect is operative coincides with the onset of clonal interference. Additional studies using ensembles of random fitness landscapes show that the results achieved for a particular choice of three-locus landscape parameters are robust and also persist as the number of loci increases. Our study indicates that an advantage for small populations is likely whenever the fitness landscape contains local maxima. The advantage appears at intermediate time scales, which are long enough for trapping at local fitness maxima to have occurred but too short for peak escape by the creation of multiple mutants.     

Development of simple fitness landscapes for peptides by artificial neural filter systems

The applicability of artificial neural filter systems as fitness functions for sequence-oriented peptide design was evaluated. Two example applications were selected: classification of dipeptides according to their hydrophobicity and classification of proteolytic cleavage-sites of protein precursor sequences according to their mean hydrophobicities and mean side-chain volumes. The cleavage-sites covered 12 residues. In the dipeptide experiments the objective was to separate a selected set of molecules from all other possible dipeptide sequences. Perceptrons, feedforward networks with one hidden layer, and a hybrid network were applied. The filters were trained by a (1,) evolution strategy. Two types of network units employing either a sigmoidal or a unimodal transfer function were used in the feedforward filters, and their influence on classification was investigated. The two-layer hybrid network employed gaussian activation functions. To analyze classification of the different filter systems, their output was plotted in the two-dimensional sequence space. The diagrams were interpreted as fitness landscapes qualifying the markedness of a characteristic peptide feature which can be used as a guide through sequence space for rational peptide design. It is demonstrated that the applicability of neural filter systems as a heuristic method for sequence optimization depends on both the appropriate network architecture and selection of representative sequence data. The networks with unimodal activation functions and the hybrid networks both led to a number of local optima. However, the hybrid networks produced the best prediction results. In contrast, the filters with sigmoidal activation produced good reclassification results leading to fitness landscapes lacking unreasonable local optima. Similar results were obtained for classification of both dipeptides and cleavage-site sequences.     

Adaptation in Tunably Rugged Fitness Landscapes: The Rough Mount Fuji Model

Much of the current theory of adaptation is based on Gillespie’s mutational landscape model (MLM), which assumes that the fitness values of genotypes linked by single mutational steps are independent random variables. On the other hand, a growing body of empirical evidence shows that real fitness landscapes, while possessing a considerable amount of ruggedness, are smoother than predicted by the MLM. In the present article we propose and analyze a simple fitness landscape model with tunable ruggedness based on the rough Mount Fuji (RMF) model originally introduced by Aita et al. in the context of protein evolution. We provide a comprehensive collection of results pertaining to the topographical structure of RMF landscapes, including explicit formulas for the expected number of local fitness maxima, the location of the global peak, and the fitness correlation function. The statistics of single and multiple adaptive steps on the RMF landscape are explored mainly through simulations, and the results are compared to the known behavior in the MLM model. Finally, we show that the RMF model can explain the large number of second-step mutations observed on a highly fit first-step background in a recent evolution experiment with a microvirid bacteriophage.     

Possible human impacts on adaptive radiation: beak size bimodality in Darwin's finches

Adaptive radiation is facilitated by a rugged adaptive landscape, where fitness peaks correspond to trait values that enhance the use of distinct resources. Different species are thought to occupy the different peaks, with hybrids falling into low-fitness valleys between them. We hypothesize that human activities can smooth adaptive landscapes, increase hybrid fitness and hamper evolutionary diversification. We investigated this possibility by analysing beak size data for 1755 Geospiza fortis measured between 1964 and 2005 on the island of Santa Cruz, Galápagos. Some populations of this species can display a resource-based bimodality in beak size, which mirrors the greater beak size differences among species. We first show that an historically bimodal population at one site, Academy Bay, has lost this property in concert with a marked increase in local human population density. We next show that a nearby site with lower human impacts, El Garrapatero, currently manifests strong bimodality. This comparison suggests that bimodality can persist when human densities are low (Academy Bay in the past, El Garrapatero in the present), but not when they are high (Academy Bay in the present). Human activities may negatively impact diversification in 'young' adaptive radiations, perhaps by altering adaptive landscapes.     

Multidimensional Epistasis and the Transitory Advantage of Sex

Identifying and quantifying the benefits of sex and recombination is a long-standing problem in evolutionary theory. In particular, contradictory claims have been made about the existence of a benefit of recombination on high dimensional fitness landscapes in the presence of sign epistasis. Here we present a comparative numerical study of sexual and asexual evolutionary dynamics of haploids on tunably rugged model landscapes under strong selection, paying special attention to the temporal development of the evolutionary advantage of recombination and the link between population diversity and the rate of adaptation. We show that the adaptive advantage of recombination on static rugged landscapes is strictly transitory. At early times, an advantage of recombination arises through the possibility to combine individually occurring beneficial mutations, but this effect is reversed at longer times by the much more efficient trapping of recombining populations at local fitness peaks. These findings are explained by means of well-established results for a setup with only two loci. In accordance with the Red Queen hypothesis the transitory advantage can be prolonged indefinitely in fluctuating environments, and it is maximal when the environment fluctuates on the same time scale on which trapping at local optima typically occurs.