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.     

Towards a general theory of adaptive walks on rugged landscapes

Adaptive evolution, to a large extent, is a complex combinatorial optimization process. In this article we take beginning steps towards developing a general theory of adaptive "walks" via fitter variants in such optimization processes. We introduce the basic idea of a space of entities, each a 1-mutant neighbor of many other entities in the space, and the idea of a fitness ascribed to each entity. Adaptive walks proceed from an initial entity, via fitter neighbors, to locally or globally optimal entities that are fitter than their neighbors. We develop a general theory for the number of local optima, lengths of adaptive walks, and the number of alternative local optima accessible from any given initial entity, for the baseline case of an uncorrelated fitness landscape. Most fitness landscapes are correlated, however. Therefore we develop parts of a universal theory of adaptation on correlated landscapes by adaptive processes that have sufficient numbers of mutations per individual to "jump beyond" the correlation lengths in the underlying landscape. In addition, we explore the statistical character of adaptive walks in two independent complex combinatorial optimization problems, that of evolving a specific cell type in model genetic networks, and that of finding good solutions to the traveling salesman problem. Surprisingly, both show similar statistical features, encouraging the hope that a general theory for adaptive walks on correlated and uncorrelated landscapes can be found. In the final section we explore two limits to the efficacy of selection. The first is new, and surprising: for a wide class of systems, as the complexity of the entities under selection increases, the local optima that are attainable fall progressively closer to the mean properties of the underlying space of entities. This may imply that complex biological systems, such as genetic regulatory systems, are "close" to the mean properties of the ensemble of genomic regulatory systems explored by evolution. The second limit shows that with increasing complexity and a fixed mutation rate, selection often becomes unable to pull an adapting population to those local optima to which connected adaptive walks via fitter variants exist. These beginning steps in theory development are applied to maturation of the immune response, and to the problem of radiation and stasis. Despite the limitations of the adaptive landscape metaphor, we believe that further development along the lines begun here will prove useful.     

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.     

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.     

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.     

Simulated Evolutionary Optimization and Local Search: Introduction and Application to Tree Search

Tree search and its more complicated variant, tree search and simultaneous multiple DNA sequence alignment, are difficult NP-complete optimization problems, which require the application of advanced computational techniques, if large data sets are to be solved within reasonable computation times. Traditionally tree search has been attacked with a search strategy that is best described as multistart hill-climbing; local search by branch swapping has been performed on several different starting trees. Recently a different tree search strategy was tested in the Parsigal parsimony program, which used a combination of evolutionary optimization and local search. Evolutionary optimization algorithms use principles adopted from biological evolution to solve technical optimization tasks. Evolutionary optimization is a stochastic global search method, which means that the method is able to escape local optima, and is in principle able to produce any solution in the search space (although this may take a long time). Local search techniques, such as branch swapping, employ a completely different search strategy; they exploit local information maximally in order to achieve quick improvement in the value of the objective function. However, local search algorithms lack the ability to escape from local optima, which is a fundamental requirement for any search algorithm that aims to be able to discover the global optimum of a multimodal optimization problem. Hence it seems that an optimization strategy combining the good properties of both evolutionary algorithms and local search would be ideal. In this study, aspects of global optimization and local search are discussed, and the method of simulated evolutionary optimization is reviewed in detail. The application of simulated evolutionary optimization to tree search in Parsigal is then reviewed briefly.     

Natural selection fails to optimize mutation rates for long-term adaptation on rugged fitness landscapes

The rate of mutation is central to evolution. Mutations are required for adaptation, yet most mutations with phenotypic effects are deleterious. As a consequence, the mutation rate that maximizes adaptation will be some intermediate value. Here, we used digital organisms to investigate the ability of natural selection to adjust and optimize mutation rates. We assessed the optimal mutation rate by empirically determining what mutation rate produced the highest rate of adaptation. Then, we allowed mutation rates to evolve, and we evaluated the proximity to the optimum. Although we chose conditions favorable for mutation rate optimization, the evolved rates were invariably far below the optimum across a wide range of experimental parameter settings. We hypothesized that the reason that mutation rates evolved to be suboptimal was the ruggedness of fitness landscapes. To test this hypothesis, we created a simplified landscape without any fitness valleys and found that, in such conditions, populations evolved near-optimal mutation rates. In contrast, when fitness valleys were added to this simple landscape, the ability of evolving populations to find the optimal mutation rate was lost. We conclude that rugged fitness landscapes can prevent the evolution of mutation rates that are optimal for long-term adaptation. This finding has important implications for applied evolutionary research in both biological and computational realms.     

Two fitness measures for clonal plants and the importance of spatial aspects

The capability of clonal plants to reproduce both sexually and vegetatively and their resulting hierarchical organisation into ramets and genets pose problems for the determination of fitness. We develop ramet-based measures of clonal plant fitness including both modes of reproduction. To this end we use simple population-dynamic equations accounting for limited space, limited dispersal, and disturbance. Neglecting interactions among ramets (r-selection regime) we derive an expression for initial growth rate r as a fitness measure. At higher densities interactions among ramets lead to density control (K-selection regime) and competitive exclusion of genotypes or species may occur. In this case we apply an invasibility criterion to derive an abundance fitness measure: competitiveness C. The optimum of C corresponds to an evolutionary stable strategy. C increases with the proportion of reproductive adults, with inverse module mortality, and with the sum of sexual and vegetative reproduction. The latter are defined as the product of the rate of module production and two correction factors accounting for juvenile mortality before establishment and for the efficiency of space exploitation by propagules. Thus C is equivalent to potential life-time offspring production, in contrast to realized life-time offspring production R₀. Because the correction factor for space exploitation cannot be expressed analytically we obtain it from complementary spatially-explicit individual-based simulations. To illustrate an application of the fitness measure C we predict optimal allocation to vegetative and sexual reproduction. In a homogeneous habitat an intermediate allocation may maximize fitness only if there is a non-linear trade-off between the modes of reproduction. However even if this trade-off is linear, spatially heterogenous disturbances can lead to an intermediate optimum of allocation because seed dispersal with subsequent vegetative spread improves the utilization of available space for recruitment if the spatial extent of single disturbances is much larger than the distance of vegetative dispersal. Thus, our study underlines the importance of spatial features for fitness measures especially of clonal plants.     

Multiple adaptive substitutions during evolution in novel environments

We consider an asexual population under strong selection-weak mutation conditions evolving on rugged fitness landscapes with many local fitness peaks. Unlike the previous studies in which the initial fitness of the population is assumed to be high, here we start the adaptation process with a low fitness corresponding to a population in a stressful novel environment. For generic fitness distributions, using an analytic argument we find that the average number of steps to a local optimum varies logarithmically with the genotype sequence length and increases as the correlations among genotypic fitnesses increase. When the fitnesses are exponentially or uniformly distributed, using an evolution equation for the distribution of population fitness, we analytically calculate the fitness distribution of fixed beneficial mutations and the walk length distribution.     

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.     

Exploring the complexity of the HIV-1 fitness landscape

Although fitness landscapes are central to evolutionary theory, so far no biologically realistic examples for large-scale fitness landscapes have been described. Most currently available biological examples are restricted to very few loci or alleles and therefore do not capture the high dimensionality characteristic of real fitness landscapes. Here we analyze large-scale fitness landscapes that are based on predictive models for in vitro replicative fitness of HIV-1. We find that these landscapes are characterized by large correlation lengths, considerable neutrality, and high ruggedness and that these properties depend only weakly on whether fitness is measured in the absence or presence of different antiretrovirals. Accordingly, adaptive processes on these landscapes depend sensitively on the initial conditions. While the relative extent to which mutations affect fitness on their own (main effects) or in combination with other mutations (epistasis) is a strong determinant of these properties, the fitness landscape of HIV-1 is considerably less rugged, less neutral, and more correlated than expected from the distribution of main effects and epistatic interactions alone. Overall this study confirms theoretical conjectures about the complexity of biological fitness landscapes and the importance of the high dimensionality of the genetic space in which adaptation takes place.     

Landscape encodings enhance optimization

Hard combinatorial optimization problems deal with the search for the minimum cost solutions (ground states) of discrete systems under strong constraints. A transformation of state variables may enhance computational tractability. It has been argued that these state encodings are to be chosen invertible to retain the original size of the state space. Here we show how redundant non-invertible encodings enhance optimization by enriching the density of low-energy states. In addition, smooth landscapes may be established on encoded state spaces to guide local search dynamics towards the ground state.     

Fisher'S geometrical model of fitness landscape and variance in fitness within a changing environment

The fitness of an individual can be simply defined as the number of its offspring in the next generation. However, it is not well understood how selection on the phenotype determines fitness. In accordance with Fisher's fundamental theorem, fitness should have no or very little genetic variance, whereas empirical data suggest that is not the case. To bridge these knowledge gaps, we follow Fisher's geometrical model and assume that fitness is determined by multivariate stabilizing selection toward an optimum that may vary among generations. We assume random mating, free recombination, additive genes, and uncorrelated stabilizing selection and mutational effects on traits. In a constant environment, we find that genetic variance in fitness under mutation-selection balance is a U-shaped function of the number of traits (i.e., of the so-called "organismal complexity"). Because the variance can be high if the organism is of either low or high complexity, this suggests that complexity has little direct costs. Under a temporally varying optimum, genetic variance increases relative to a constant optimum and increasingly so when the mutation rate is small. Therefore, mutation and changing environment together can maintain high genetic variance. These results therefore lend support to Fisher's geometric model of a fitness landscape.     

基于改进PSO的洞庭湖水源涵养林空间优化模型

以结构化森林经营思想为理论基础,从与水源林涵养水源、保持水土功能密切相关的林分物种组成(树种混交)、种内及种间竞争、空间分布格局、垂直结构4个方面选择混交度、竞争指数、角尺度、林层指数、空间密度指数、开阔比数作为水源林健康经营和林分空间结构优化的目标函数,建立洞庭湖水源林林分多目标空间优化模型,应用改进的群智能粒子群算法求解林分空间结构优化模型,并针对模型输出的目标树空间结构单元制定周密的经营策略.研究结果表明,优化模型能准确定位林分空间关系的薄弱环节,调控措施能显著改善林分空间结构,有利于促进森林生态系统的正向演替,为恢复洞庭湖水源林生态功能和健康经营提供理论依据和技术支撑.应用优化模型进行水源涵养林健康经营突破了传统森林经营模式,为智能信息技术在森林空间经营中的应用提供了新的思路.     

Limits of Neutral Drift: Lessons From the In Vitro Evolution of Two Ribozymes

The relative contributions of adaptive selection and neutral drift to genetic change are unknown but likely depend on the inherent abundance of functional genotypes in sequence space and how accessible those genotypes are to one another. To better understand the relative roles of selection and drift in evolution, local fitness landscapes for two different RNA ligase ribozymes were examined using a continuous in vitro evolution system under conditions that foster the capacity for neutral drift to mediate genetic change. The exploration of sequence space was accelerated by increasing the mutation rate using mutagenic nucleotide analogs. Drift was encouraged by carrying out evolution within millions of separate compartments to exploit the founder effect. Deep sequencing of individuals from the evolved populations revealed that the distribution of genotypes did not escape the starting local fitness peak, remaining clustered around the sequence used to initiate evolution. This is consistent with a fitness landscape where high-fitness genotypes are sparse and well isolated, and suggests, at least in this context, that neutral drift alone is not a primary driver of genetic change. Neutral drift does, however, provide a repository of genetic variation upon which adaptive selection can act.     

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.     

THE EVOLUTION OF CANALIZATION AND THE BREAKING OF VON BAER'S LAWS: MODELING THE EVOLUTION OF DEVELOPMENT WITH EPISTASIS

Evolution can change the developmental processes underlying a character without changing the average expression of the character itself. This sort of change must occur in both the evolution of canalization, in which a character becomes increasingly buffered against genetic or developmental variation, and in the phenomenon of closely related species that show similar adult phenotypes but different underlying developmental patterns. To study such phenomena, I develop a model that follows evolution on a surface representing adult phenotype as a function of underlying developmental characters. A contour on such a “phenotype landscape” is a set of states of developmental characters that produce the same adult phenotype. Epistasis induces curvature of this surface, and degree of canalization is represented by the slope along a contour. I first discuss the geometric properties of phenotype landscapes, relating epistasis to canalization. I then impose a fitness function on the phenotype and model evolution of developmental characters as a function of the fitness function and the local geometry of the surface. This model shows how canalization evolves as a population approaches an optimum phenotype. It further shows that under some circumstances, “decanalization” can occur, in which the expression of adult phenotype becomes increasingly sensitive to developmental variation. This process can cause very similar populations to diverge from one another developmentally even when their adult phenotypes experience identical selection regimes.     

Percolation on fitness landscapes: effects of correlation, phenotype, and incompatibilities

We study how correlations in the random fitness assignment may affect the structure of fitness landscapes, in three classes of fitness models. The first is a phenotype space in which individuals are characterized by a large number n of continuously varying traits. In a simple model of random fitness assignment, viable phenotypes are likely to form a giant connected cluster percolating throughout the phenotype space provided the viability probability is larger than 1/2(n). The second model explicitly describes genotype-to-phenotype and phenotype-to-fitness maps, allows for neutrality at both phenotype and fitness levels, and results in a fitness landscape with tunable correlation length. Here, phenotypic neutrality and correlation between fitnesses can reduce the percolation threshold, and correlations at the point of phase transition between local and global are most conducive to the formation of the giant cluster. In the third class of models, particular combinations of alleles or values of phenotypic characters are "incompatible" in the sense that the resulting genotypes or phenotypes have zero fitness. This setting can be viewed as a generalization of the canonical Bateson-Dobzhansky-Muller model of speciation and is related to K-SAT problems, prominent in computer science. We analyze the conditions for the existence of viable genotypes, their number, as well as the structure and the number of connected clusters of viable genotypes. We show that analysis based on expected values can easily lead to wrong conclusions, especially when fitness correlations are strong. We focus on pairwise incompatibilities between diallelic loci, but we also address multiple alleles, complex incompatibilities, and continuous phenotype spaces. In the case of diallelic loci, the number of clusters is stochastically bounded and each cluster contains a very large sub-cube. Finally, we demonstrate that the discrete NK model shares some signature properties of models with high correlations.     

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.     

Allocation of parental investment among individual offspring in the European beewolf Philanthus triangulum F. (Hymenoptera: Sphecidae)

Optimal allocation of parental resources is an important life history trait. However, it has been rarely investigated empirically. We tested aspects of optimal allocation theory in a digger wasp, the European beewolf. Investment allocation theory assumes (1) a trade‐off between investment per offspring and offspring number and (2) a convex relationship between investment per offspring and fitness returns. From mis relationship an optimum amount of investment per offspring can be derived and parents are predicted to provide each offspring with this optimum amount of investment. We used the number of bees in a brood cell as a measure of parental investment. Offspring fitness was quantified as both survival until emergence and success as adults. There is evidence for a trade‐off between current and future reproduction, suggesting that the first assumption is met. In contradiction to the second assumption, one mortality factor, parasitism, increased proportionally with the number of bees in a brood cell. However, overall mortality until emergence significantly decreased with the number of bees in a brood cell as assumed by the theory. The determination of the optimum amount of investment per offspring is complicated because the sexes possibly differ in their relationship between amount of investment and fitness. Individual males received considerably fewer bees (2.2 ± 0.8) than females (3.8 ± 0.5). Two independent estimates of the investment specific survival suggested that sons with two bees had the highest fitness returns per single bee and, consistent with the prediction, most sons were provisioned with two bees. For daughters, four bees is probably the optimum amount and most daughters were provisioned with this number. In both sexes the variation of investment per offspring was less than expected by a Poisson distribution with the same mean. These findings support the view that parental investment is allocated in a way that optimizes the trade‐off between offspring number and investment per offspring. However, variation contradicting the hypothesis still occurred. This might be explained either by adaptive variation in the amount of investment per offspring, constraints in the adjustment of the optimum amount of investment, or problems in measuring parental investment.