Adaptation dynamics of the quasispecies model

We study the adaptation dynamics of an initially maladapted population evolving via the elementary processes of mutation and selection. The evolution occurs on rugged fitness landscapes which are defined on the multi-dimensional genotypic space and have many local peaks separated by low fitness valleys. We mainly focus on the Eigen’s model that describes the deterministic dynamics of an infinite number of self-replicating molecules. In the stationary state, for small mutation rates such a population forms a quasispecies which consists of the fittest genotype and its closely related mutants. The quasispecies dynamics on rugged fitness landscape follow a punctuated (or steplike) pattern in which a population jumps from a low fitness peak to a higher one, stays there for a considerable time before shifting the peak again and eventually reaches the global maximum of the fitness landscape. We calculate exactly several properties of this dynamical process within a simplified version of the quasispecies model.      

Dynamic fitness landscapes: expansions for small mutation rates

We study the evolution of asexual microorganisms with small mutation rate in fluctuating environments, and develop techniques that allow us to expand the formal solution of the evolution equations to first order in the mutation rate. Our method can be applied to both discrete time and continuous time systems. While the behavior of continuous time systems is dominated by the average fitness landscape for small mutation rates, in discrete time systems it is instead the geometric mean fitness that determines the system's properties. In both cases, we find that in situations in which the arithmetic (resp. geometric) mean of the fitness landscape is degenerate, regions in which the fitness fluctuates around the mean value present a selective advantage over regions in which the fitness stays at the mean. This effect is caused by the vanishing genetic diffusion at low mutation rates. In the absence of strong diffusion, a population can stay close to a fluctuating peak when the peak's height is below average, and take advantage of the peak when its height is above average.     

Self-organized critical model of biological evolution

A punctuated equilibrium model of biological evolution with relative fitness between different species being the fundamental driving force of evolution is introduced. Mutation is modeled as a fitness updating cellular automation process where the change in fitness after mutation follows a Gaussian distribution with mean x > 0 and standard deviation σ. Scaling behaviors are observed in our numerical simulation, indicating that the model is self-organized critical. Besides, the numerical experiment suggests that models with different x and σ belongs to the same universality class.     

Four-State Quantum Chain as a Model of Sequence Evolution

A variety of selection-mutation models for DNA (or RNA) sequences, well known in molecular evolution, can be translated into a model of coupled Ising quantum chains. This correspondence is used to investigate the genetic variability and error threshold behaviour in dependence of possible fitness landscapes. In contrast to the two-state models treated hitherto, the model explicitly takes the four-state nature of the nucleotide alphabet into account and allows for the distinction of mutation rates for the different base substitutions, as given by standard mutation schemes of molecular phylogeny. As a consequence of this refined treatment, new phase diagrams for the error threshold behaviour are obtained, with appearance of a novel phase in which the nucleotide ordering of the wildtype sequence is only partially conserved. Explicit analytical and numerical results are presented for evolution dynamics and equilibrium behaviour in a number of accessible situations, such as quadratic fitness landscapes and the Kimura 2 parameter mutation scheme.     

A Family of Fitness Landscapes Modeled through Gene Regulatory Networks

Fitness landscapes are a powerful metaphor for understanding the evolution of biological systems. These landscapes describe how genotypes are connected to each other through mutation and related through fitness. Empirical studies of fitness landscapes have increasingly revealed conserved topographical features across diverse taxa, e.g., the accessibility of genotypes and “ruggedness”. As a result, theoretical studies are needed to investigate how evolution proceeds on fitness landscapes with such conserved features. Here, we develop and study a model of evolution on fitness landscapes using the lens of Gene Regulatory Networks (GRNs), where the regulatory products are computed from multiple genes and collectively treated as phenotypes. With the assumption that regulation is a binary process, we prove the existence of empirically observed, topographical features such as accessibility and connectivity. We further show that these results hold across arbitrary fitness functions and that a trade-off between accessibility and ruggedness need not exist. Then, using graph theory and a coarse-graining approach, we deduce a mesoscopic structure underlying GRN fitness landscapes where the information necessary to predict a population’s evolutionary trajectory is retained with minimal complexity. Using this coarse-graining, we develop a bottom-up algorithm to construct such mesoscopic backbones, which does not require computing the genotype network and is therefore far more efficient than brute-force approaches. Altogether, this work provides mathematical results of high-dimensional fitness landscapes and a path toward connecting theory to empirical studies.     

Error thresholds for quasispecies on dynamic fitness landscapes

In this paper we investigate error thresholds on dynamic fitness landscapes. We show that there exists both a lower and an upper threshold, representing limits to the copying fidelity of simple replicators. The lower bound can be expressed as a correction term to the error threshold present on a static landscape. The upper error threshold is a new limit that only exists on dynamic fitness landscapes. We also show that for long genomes and/or highly dynamic fitness landscapes there exists a lower bound on the selection pressure required for the effective selection of genomes with superior fitness independent of mutation rates, i.e. there are distinct nontrivial limits to evolutionary parameters in dynamic environments.     

Evolutionary Accessibility in Tunably Rugged Fitness Landscapes

The adaptive evolution of a population under the influence of mutation and selection is strongly influenced by the structure of the underlying fitness landscape, which encodes the interactions between mutations at different genetic loci. Theoretical studies of such landscapes have been carried out for several decades, but only recently experimental fitness measurements encompassing all possible combinations of small sets of mutations have become available. The empirical studies have spawned new questions about the accessibility of optimal genotypes under natural selection. Depending on population dynamic parameters such as mutation rate and population size, evolutionary accessibility can be quantified through the statistics of accessible mutational pathways (along which fitness increases monotonically), or through the study of the basin of attraction of the optimal genotype under greedy (steepest ascent) dynamics. Here we investigate these two measures of accessibility in the framework of Kauffman’s LK-model, a paradigmatic family of random fitness landscapes with tunable ruggedness. The key parameter governing the strength of genetic interactions is the number K of interaction partners of each of the L sites in the genotype sequence. In general, accessibility increases with increasing genotype dimensionality L and decreases with increasing number of interactions K. Remarkably, however, we find that some measures of accessibility behave non-monotonically as a function of K, indicating a special role of the most sparsely connected, non-trivial cases K=1 and 2. The relation between models for fitness landscapes and spin glasses is also addressed.     

Evolution of a population of random Boolean networks

We investigate the evolution of populations of random Boolean networks under selection for robustness of the dynamics with respect to the perturbation of the state of a node. The fitness landscape contains a huge plateau of maximum fitness that spans the entire network space. When selection is so strong that it dominates over drift, the evolutionary process is accompanied by a slow increase in the mean connectivity and a slow decrease in the mean fitness. Populations evolved with higher mutation rates show a higher robustness under mutations. This means that even though all the evolved populations exist close to the plateau of maximum fitness, they end up in different regions of network space.     

Anderson Localization, Non-linearity and Stable Genetic Diversity

In many models of genotypic evolution, the vector of genotype populations satisfies a system of linear ordinary differential equations. This system of equations models a competition between differential replication rates (fitness) and mutation. Mutation operates as a generalized diffusion process on genotype space. In the large time asymptotics, the replication term tends to produce a single dominant quasi-species, unless the mutation rate is too high, in which case the asymptotic population becomes de-localized. We introduce a more macroscopic picture of genotypic evolution wherein a random fitness term in the linear model produces features analogous to Anderson localization. When coupled with density dependent non-linearities, which limit the population of any given genotype, we obtain a model whose large time asymptotics display stable genotypic diversity.Research partially supported by DARPA under the FUNBIO program and the Francis J. Carey Term Chair.     

Speeding up Evolutionary Search by Small Fitness Fluctuations

We consider a fixed size population that undergoes an evolutionary adaptation in the weak mutation rate limit, which we model as a biased Langevin process in the genotype space. We show analytically and numerically that, if the fitness landscape has a small highly epistatic (rough) and time-varying component, then the population genotype exhibits a high effective diffusion in the genotype space and is able to escape local fitness minima with a large probability. We argue that our principal finding that even very small time-dependent fluctuations of fitness can substantially speed up evolution is valid for a wide class of models.     

Ising Quantum Chain and Sequence Evolution

A sequence space model which describes the interplay of mutation and selection in molecular evolution is shown to be equivalent to an Ising quantum chain. Observable quantities tailored to match the biological situation are then employed to treat three fitness landscapes exactly.     

Solution of the Crow-Kimura and Eigen Models for Alphabets of Arbitrary Size by Schwinger Spin Coherent States

To represent the evolution of nucleic acid and protein sequence, we express the parallel and Eigen models for molecular evolution in terms of a functional integral representation with an h-letter alphabet, lifting the two-state, purine/pyrimidine assumption often made in quasi-species theory. For arbitrary h and a general mutation scheme, we obtain the solution of this model in terms of a maximum principle. Euler’s theorem for homogeneous functions is used to derive this ‘thermodynamic’ formulation of evolution. The general result for the parallel model reduces to known results for the purine/pyrimidine h=2 alphabet and the nucleic acid h=4 alphabet for the Kimura 3 ST mutation scheme. Examples are presented for the h=4 and h=20 cases. We also derive the maximum principle for the Eigen model for general h. The general result for the Eigen model reduces to a known result for h=2. Examples are presented for the nucleic acid h=4 and the amino acid h=20 alphabet. An error catastrophe phase transition occurs in these models, and the order of the phase transition changes from second to first order for smooth fitness functions when the alphabet size is increased beyond two letters to the generic case. As examples, we analyze the general analytic solution for sharp peak, linear, quadratic, and quartic fitness functions.     

Phase diagrams of quasispecies theory with recombination and horizontal gene transfer

We consider how transfer of genetic information between individuals influences the phase diagram and mean fitness of both the Eigen and the parallel, or Crow-Kimura, models of evolution. In the absence of genetic transfer, these physical models of evolution consider the replication and point mutation of the genomes of independent individuals in a large population. A phase transition occurs, such that below a critical mutation rate an identifiable quasispecies forms. We show how transfer of genetic information changes the phase diagram and mean fitness and introduces metastability in quasispecies theory, via an analytic field theoretic mapping.     

Scale-free properties of information flux networks in genetic algorithms

In this study, we present empirical analysis of statistical properties of mating networks in genetic algorithms (GAs). Under the framework of GAs, we study a class of interaction network model—information flux network (IFN), which describes the information flow among generations during evolution process. The IFNs are found to be scale-free when the selection operator uses a preferential strategy rather than a random. The topology structure of IFN is remarkably affected by operations used in genetic algorithms. The experimental results suggest that the scaling exponent of the power-law degree distribution is shown to decrease when crossover rate increases, but increase when mutation rate increases, and the reason may be that high crossover rate leads to more edges that are shared between nodes and high mutation rate leads to many individuals in a generation possessing low fitness. The magnitude of the out-degree exponent is always more than the in-degree exponent for the systems tested. These results may provide a new viewpoint with which to view GAs and guide the dissemination process of genetic information throughout a population.     

Relaxation Property and Stability Analysis of the Quasispecies Models

The relaxation property of both Eigen model and Crow-Kimura model with a single peak fitness landscape is studied from phase transition point of view. We first analyze the eigenvalue spectra of the replication mutation matrices. For sufficiently long sequences, the almost crossing point between the largest and second-largest eigenvalues locates the error threshold at whichcritical slowing down behavior appears. We calculate the critical exponent in the limit of infinite sequence lengths and compare it with the result from numerical curve fittings at sufficiently long sequences. We find that for both models the relaxation time diverges with exponent 1 at the error (mutation) threshold point. Results obtained from both methods agree quite well. From the unlimited correlation length feature, the first order phase transition isfurther confirmed. Finally with linear stability theory, we show that the two model systems are stable for all ranges of mutation rate. The Eigen model is asymptotically stable in terms of mutant classes, and the Crow-Kimura model is completely stable.     

Temporal and dimensional effects in evolutionary graph theory

The spread in time of a mutation through a population is studied analytically and computationally in fully connected networks and on spatial lattices. The time t* for a favorable mutation to dominate scales with the population size N as N(D+1)/D in D-dimensional hypercubic lattices and as NlnN in fully-connected graphs. It is shown that the surface of the interface between mutants and nonmutants is crucial in predicting the dynamics of the system. Network topology has a significant effect on the equilibrium fitness of a simple population model incorporating multiple mutations and sexual reproduction.     

Model for mutation in bacterial populations

We describe the evolution of E. coli populations through a Bak-Sneppen-type model which incorporates random mutations. We show that, for a value of the mutation level which coincides with the one estimated from experiments, this model reproduces the measures of mean fitness relative to that of a common ancestor, performed for over 10,000 bacterial generations.     

Bounded fitness landscapes and the evolution of the linguistic diversity

We have recently introduced a simple spatial computer simulation model to study the evolution of the linguistic diversity. The model considers processes of selective geographic colonization, linguistic anomalous diffusion and mutation. In the approach, we ascribe to each language a fitness function which depends on the number of people that speak that language. Here, we extend the aforementioned model to examine the role of saturation of the fitness on the language dynamics. We found that the dependence of the linguistic diversity on the area after colonization displays a power law regime with a nontrivial exponent in very good agreement with the measured exponent associated with the actual distribution of languages on the Earth.     

基于改进遗传算法的移动机器人路径规划

针对传统遗传算法存在的搜索效率低、易于陷入局部最优解的问题,提出了一种改进的遗传算法。采用简单的一维编码替代复杂的二维编码,节约了存储空间。在遗传算子的设计中,重新定义了交叉算子和变异算子,避免了陷入局部最优。最后将最短路径和免碰撞相结合作为适应度函数进行遗传优化。实验结果表明,改进的算法能够快速、有效的规划出最优路径。