Stochastic slowdown in evolutionary processes

Fixation times on directed graphs

Computing the rate of evolution in spatially structured populations is difficult. A key quantity is the fixation time of a single mutant with relative reproduction rate r which invades a population of residents. We say that the fixation time is "fast" if it is at most a polynomial function in terms of the population size N. Here we study fixation times of advantageous mutants (r > 1) and neutral mutants (r = 1) on directed graphs, which are those graphs that have at least some one-way connections. We obtain three main results. First, we prove that for any directed graph the fixation time is fast, provided that r is sufficiently large. Second, we construct an efficient algorithm that gives an upper bound for the fixation time for any graph and any r ≥ 1. Third, we identify a broad class of directed graphs with fast fixation times for any r ≥ 1. This class includes previously studied amplifiers of selection, such as Superstars and Metafunnels. We also show that on some graphs the fixation time is not a monotonically declining function of r; in particular, neutral fixation can occur faster than fixation for small selective advantages.

The speed of neutral evolution on graphs

The speed of evolution on structured populations is crucial for biological and social systems. The likelihood of invasion is key for evolutionary stability. But it makes little sense if it takes long. It is far from known what population structure slows down evolution. We investigate the absorption time of a single neutral mutant for all the 112 non-isomorphic undirected graphs of size 6. We find that about three-quarters of the graphs have an absorption time close to that of the complete graph, less than one-third are accelerators, and more than two-thirds are decelerators. Surprisingly, determining whether a graph has a long absorption time is too complicated to be captured by the joint degree distribution. Via the largest sojourn time, we find that echo-chamber-like graphs, which consist of two homogeneous graphs connected by few sparse links, are likely to slow down absorption. These results are robust for large graphs, mutation patterns as well as evolutionary processes. This work serves as a benchmark for timing evolution with complex interactions, and fosters the understanding of polarization in opinion formation.

Self-loops in evolutionary graph theory: Friends or foes?

Evolutionary dynamics in spatially structured populations has been studied for a long time. More recently, the focus has been to construct structures that amplify selection by fixing beneficial mutations with higher probability than the well-mixed population and lower probability of fixation for deleterious mutations. It has been shown that for a structure to substantially amplify selection, self-loops are necessary when mutants appear predominately in nodes that change often. As a result, for low mutation rates, self-looped amplifiers attain higher steady-state average fitness in the mutation-selection balance than well-mixed populations. But what happens when the mutation rate increases such that fixation probabilities alone no longer describe the dynamics? We show that self-loops effects are detrimental outside the low mutation rate regime. In the intermediate and high mutation rate regime, amplifiers of selection attain lower steady-state average fitness than the complete graph and suppressors of selection. We also provide an estimate of the mutation rate beyond which the mutation-selection dynamics on a graph deviates from the weak mutation rate approximation. It involves computing average fixation time scaling with respect to the population sizes for several graphs.

Multi-strategy evolutionary games: A Markov chain approach

Interacting strategies in evolutionary games is studied analytically in a well-mixed population using a Markov chain method. By establishing a correspondence between an evolutionary game and Markov chain dynamics, we show that results obtained from the fundamental matrix method in Markov chain dynamics are equivalent to corresponding ones in the evolutionary game. In the conventional fundamental matrix method, quantities like fixation probability and fixation time are calculable. Using a theorem in the fundamental matrix method, conditional fixation time in the absorbing Markov chain is calculable. Also, in the ergodic Markov chain, the stationary probability distribution that describes the Markov chain’s stationary state is calculable analytically. Finally, the Rock, scissor, paper evolutionary game are evaluated as an example, and the results of the analytical method and simulations are compared. Using this analytical method saves time and computational facility compared to prevalent simulation methods.

Wald’s martingale and the conditional distributions of absorption time in the Moran process

Many models of evolution are stochastic processes, where some quantity of interest fluctuates randomly in time. One classic example is the Moranbirth–death process, where that quantity is the number of mutants in a population. In such processes, we are often interested in their absorption (i.e. fixation) probabilities and the conditional distributions of absorption time. Those conditional time distributions can be very difficult to calculate, even for relatively simple processes like the Moran birth–death model. Instead of considering the time to absorption, we consider a closely related quantity: the number of mutant population size changes before absorption. We use Wald’s martingale to obtain the conditional characteristic functions of that quantity in the Moran process. Our expressions are novel, analytical and exact, and their parameter dependence is explicit. We use our results to approximate the conditional characteristic functions of absorption time. We state the conditions under which that approximation is particularly accurate. Martingales are an elegant framework to solve principal problems of evolutionary stochastic processes. They do not require us to evaluate recursion relations, so when they are applicable, we can quickly and tractably obtain absorption probabilities and times of evolutionary models.

Time scales and wave formation in non-linear spatial public goods games

The co-evolutionary dynamics of competing populations can be strongly affected by frequency-dependent selection and spatial population structure. As co-evolving populations grow into a spatial domain, their initial spatial arrangement and their growth rate differences are important factors that determine the long-term outcome. We here model producer and free-rider co-evolution in the context of a diffusive public good (PG) that is produced by the producers at a cost but evokes local concentration-dependent growth benefits to all. The benefit of the PG can be non-linearly dependent on public good concentration. We consider the spatial growth dynamics of producers and free-riders in one, two and three dimensions by modeling producer cell, free-rider cell and public good densities in space, driven by the processes of birth, death and diffusion (cell movement and public good distribution). Typically, one population goes extinct, but the time-scale of this process varies with initial conditions and the growth rate functions. We establish that spatial variation is transient regardless of dimensionality, and that structured initial conditions lead to increasing times to get close to an extinction state, called ε-extinction time. Further, we find that uncorrelated initial spatial structures do not influence this ε-extinction time in comparison to a corresponding well-mixed (non-spatial) system. In order to estimate the ε-extinction time of either free-riders or producers we derive a slow manifold solution. For invading populations, i.e. for populations that are initially highly segregated, we observe a traveling wave, whose speed can be calculated. Our results provide quantitative predictions for the transient spatial dynamics of cooperative traits under pressure of extinction.

Evolutionary public good (PG) games capture the essence of production of growth-beneficial factors that are vulnerable to exploitation by free-riders who do not carry the cost of production. PGs emerge in cellular populations, for example in growing bacteria and cancer cells. We study the eco-evolutionary dynamics of a PG in populations that grow in space. In our model, PG-producer cells and free-rider cells can grow according to their own birth and death rates. Co-evolution occurs due to public good-driven surplus in the intrinsic growth rates at a cost to producers. A net growth rate-benefit to free-riders leads to the well-known tragedy of the commons in which producers go extinct. What is often omitted from discussions is the time scale on which this extinction can occur, especially in spatial populations. Here, we derive analytical estimates of the ε-extinction time in different spatial settings. As we do not consider a stochastic process, the ε-extinction time captures the time needed to approach an extinction state. We identify spatial scenarios in which extinction takes long enough such that the tragedy of the commons never occurs within a meaningful lifetime of the system. Using numerical simulations we analyze the deviations from our analytical predictions.

Computation and Simulation of Evolutionary Game Dynamics in Finite Populations

The study of evolutionary dynamics increasingly relies on computational methods, as more and more cases outside the range of analytical tractability are explored. The computational methods for simulation and numerical approximation of the relevant quantities are diverging without being compared for accuracy and performance. We thoroughly investigate these algorithms in order to propose a reliable standard. For expositional clarity we focus on symmetric 2 × 2 games leading to one-dimensional processes, noting that extensions can be straightforward and lessons will often carry over to more complex cases. We provide time-complexity analysis and systematically compare three families of methods to compute fixation probabilities, fixation times and long-term stationary distributions for the popular Moran process. We provide efficient implementations that substantially improve wall times over naive or immediate implementations. Implications are also discussed for the Wright-Fisher process, as well as structured populations and multiple types.

Evolutionary game dynamics of the Wright-Fisher process with different selection intensities

Evolutionary game dynamics in finite populations can be described by a frequency-dependent, stochastic Wright-Fisher process. The fitness of individuals in a population is not only linked to environmental conditions but also tightly coupled to the types and frequencies of competitors, leading to different types of individuals with different selection intensities. We studied a 2 × 2 symmetric game in a finite population and established a dynamic model of the Wright-Fisher process by introducing different selection intensities for different strategies. Thus, we provided another effective way to study the evolutionary dynamics of a finite population and obtained the analytical expressions of fixation probabilities under weak selection. The fixation probability of a strategy is not only related to a game matrix but also to different selection intensities. The conditions required for natural selection to favor one strategy and for that strategy to be an evolutionary stable strategy (ESS_N) are specified in our model. We compared our results with those of a Moran dynamic process with different selection intensities to explore these two processes better. In the two processes, the conditions conducive to the strategy's taking fixation are the same. By simulation analysis, the dynamic relationships between the fixation probabilities and selection intensities were intuitively observed in the prisoner's dilemma, coordination, and coexistence games. The fixation probability of the cooperative strategy in the prisoner's dilemma decreases with the increase of its own selection intensity. In the coexistence and coordination games, the fixation probability of the cooperative strategy increases with its own selection intensity. For the three types of games, the fixation probability of the cooperative strategy decreases with the increase of the selection intensity of the defection strategy.

Promotion of cooperation in evolutionary game dynamics with local information

In this paper, we propose a strategy-updating rule driven by local information, which is called Local process. Unlike the standard Moran process, the Local process does not require global information about the strategic environment. By analyzing the dynamical behavior of the system, we explore how the local information influences the fixation of cooperation in two-player evolutionary games. Under weak selection, the decreasing local information leads to an increase of the fixation probability when natural selection does not favor cooperation replacing defection. In the limit of sufficiently large selection, the analytical results indicate that the fixation probability increases with the decrease of the local information, irrespective of the evolutionary games. Furthermore, for the dominance of defection games under weak selection and for coexistence games, the decreasing of local information will lead to a speedup of a single cooperator taking over the population. Overall, to some extent, the local information is conducive to promoting the cooperation.

Allele Age Under Non-Classical Assumptions is Clarified by an Exact Computational Markov Chain Approach

Determination of the age of an allele based on its population frequency is a well-studied problem in population genetics, for which a variety of approximations have been proposed. We present a new result that, surprisingly, allows the expectation and variance of allele age to be computed exactly (within machine precision) for any finite absorbing Markov chain model in a matter of seconds. This approach makes none of the classical assumptions (e.g., weak selection, reversibility, infinite sites), exploits modern sparse linear algebra techniques, integrates over all sample paths, and is rapidly computable for Wright-Fisher populations up to N_e = 100,000. With this approach, we study the joint effect of recurrent mutation, dominance, and selection, and demonstrate new examples of “selective strolls” where the classical symmetry of allele age with respect to selection is violated by weakly selected alleles that are older than neutral alleles at the same frequency. We also show evidence for a strong age imbalance, where rare deleterious alleles are expected to be substantially older than advantageous alleles observed at the same frequency when population-scaled mutation rates are large. These results highlight the under-appreciated utility of computational methods for the direct analysis of Markov chain models in population genetics.

Extinction rates in tumour public goods games

Cancer evolution and progression are shaped by cellular interactions and Darwinian selection. Evolutionary game theory incorporates both of these principles, and has been proposed as a framework to understand tumour cell population dynamics. A cornerstone of evolutionary dynamics is the replicator equation, which describes changes in the relative abundance of different cell types, and is able to predict evolutionary equilibria. Typically, the replicator equation focuses on differences in relative fitness. We here show that this framework might not be sufficient under all circumstances, as it neglects important aspects of population growth. Standard replicator dynamics might miss critical differences in the time it takes to reach an equilibrium, as this time also depends on cellular turnover in growing but bounded populations. As the system reaches a stable manifold, the time to reach equilibrium depends on cellular death and birth rates. These rates shape the time scales, in particular, in coevolutionary dynamics of growth factor producers and free-riders. Replicator dynamics might be an appropriate framework only when birth and death rates are of similar magnitude. Otherwise, population growth effects cannot be neglected when predicting the time to reach an equilibrium, and cell-type-specific rates have to be accounted for explicitly.

Evolutionary games on cycles with strong selection

Evolutionary games on graphs describe how strategic interactions and population structure determine evolutionary success, quantified by the probability that a single mutant takes over a population. Graph structures, compared to the well-mixed case, can act as amplifiers or suppressors of selection by increasing or decreasing the fixation probability of a beneficial mutant. Properties of the associated mean fixation times can be more intricate, especially when selection is strong. The intuition is that fixation of a beneficial mutant happens fast in a dominance game, that fixation takes very long in a coexistence game, and that strong selection eliminates demographic noise. Here we show that these intuitions can be misleading in structured populations. We analyze mean fixation times on the cycle graph under strong frequency-dependent selection for two different microscopic evolutionary update rules (death-birth and birth-death). We establish exact analytical results for fixation times under strong selection and show that there are coexistence games in which fixation occurs in time polynomial in population size. Depending on the underlying game, we observe inherence of demographic noise even under strong selection if the process is driven by random death before selection for birth of an offspring (death-birth update). In contrast, if selection for an offspring occurs before random removal (birth-death update), then strong selection can remove demographic noise almost entirely.

Speed of evolution on graphs

The likelihood that a mutant fixates in the wild population, i.e., fixation probability, has been intensively studied in evolutionary game theory, where individuals' fitness is frequency dependent. However, it is of limited interest when it takes long to take over. Thus the speed of evolution becomes an important issue. In general, it is still unclear how fixation times are affected by the population structure, although the fixation times have already been addressed in the well-mixed populations. Here we theoretically address this issue by pair approximation and diffusion approximation on regular graphs. It is shown (i) that under neutral selection, both unconditional and conditional fixation time are shortened by increasing the number of neighbors; (ii) that under weak selection, for the simplified prisoner's dilemma game, if benefit-to-cost ratio exceeds the degree of the graph, then the unconditional fixation time of a single cooperator is slower than that in the neutral case; and (iii) that under weak selection, for the conditional fixation time, limited neighbor size dilutes the counterintuitive stochastic slowdown which was found in well-mixed populations. Interestingly, we find that all of our results can be interpreted as that in the well-mixed population with a transformed payoff matrix. This interpretation is also valid for both death-birth and birth-death processes on graphs. This interpretation bridges the fixation time in the structured population and that in the well-mixed population. Thus it opens the avenue to investigate the challenging fixation time in structured populations by the known results in well-mixed populations.

Random and non-random mating populations: Evolutionary dynamics in meiotic drive

Game theoretic tools are utilized to analyze a one-locus continuous selection model of sex-specific meiotic drive by considering nonequivalence of the viabilities of reciprocal heterozygotes that might be noticed at an imprinted locus. The model draws attention to the role of viability selections of different types to examine the stable nature of polymorphic equilibrium. A bridge between population genetics and evolutionary game theory has been built up by applying the concept of the Fundamental Theorem of Natural Selection. In addition to pointing out the influences of male and female segregation ratios on selection, configuration structure reveals some noted results, e.g., Hardy-Weinberg frequencies hold in replicator dynamics, occurrence of faster evolution at the maximized variance fitness, existence of mixed Evolutionarily Stable Strategy (ESS) in asymmetric games, the tending evolution to follow not only a 1:1 sex ratio but also a 1:1 different alleles ratio at particular gene locus. Through construction of replicator dynamics in the group selection framework, our selection model introduces a redefining bases of game theory to incorporate non-random mating where a mating parameter associated with population structure is dependent on the social structure. Also, the model exposes the fact that the number of polymorphic equilibria will depend on the algebraic expression of population structure.

Selective Strolls: Fixation and Extinction in Diploids Are Slower for Weakly Selected Mutations Than for Neutral Ones

In finite populations, an allele disappears or reaches fixation due to two main forces, selection and drift. Selection is generally thought to accelerate the process: a selected mutation will reach fixation faster than a neutral one, and a disadvantageous one will quickly disappear from the population. We show that even in simple diploid populations, this is often not true. Dominance and recessivity unexpectedly slow down the evolutionary process for weakly selected alleles. In particular, slightly advantageous dominant and mildly deleterious recessive mutations reach fixation slightly more slowly than neutral ones (at most 5%). This phenomenon determines genetic signatures opposite to those expected under strong selection, such as increased instead of decreased genetic diversity around the selected site. Furthermore, we characterize a new phenomenon: mildly deleterious recessive alleles, thought to represent a wide fraction of newly arising mutations, on average survive in a population slightly longer than neutral ones, before getting lost. Consequently, these mutations are on average slightly older than neutral ones, in contrast with previous expectations. Furthermore, they slightly increase the amount of weakly deleterious polymorphisms, as a consequence of the longer unconditional sojourn times compared to neutral mutations.

Fixation in finite populations evolving in fluctuating environments

The environment in which a population evolves can have a crucial impact on selection. We study evolutionary dynamics in finite populations of fixed size in a changing environment. The population dynamics are driven by birth and death events. The rates of these events may vary in time depending on the state of the environment, which follows an independent Markov process. We develop a general theory for the fixation probability of a mutant in a population of wild-types, and for mean unconditional and conditional fixation times. We apply our theory to evolutionary games for which the payoff structure varies in time. The mutant can exploit the environmental noise; a dynamic environment that switches between two states can lead to a probability of fixation that is higher than in any of the individual environmental states. We provide an intuitive interpretation of this surprising effect. We also investigate stationary distributions when mutations are present in the dynamics. In this regime, we find two approximations of the stationary measure. One works well for rapid switching, the other for slowly fluctuating environments.

Environmental evolutionary graph theory

Understanding the influence of an environment on the evolution of its resident population is a major challenge in evolutionary biology. Great progress has been made in homogeneous population structures while heterogeneous structures have received relatively less attention. Here we present a structured population model where different individuals are best suited to different regions of their environment. The underlying structure is a graph: individuals occupy vertices, which are connected by edges. If an individual is suited for their vertex, they receive an increase in fecundity. This framework allows attention to be restricted to the spatial arrangement of suitable habitat. We prove some basic properties of this model and find some counter-intuitive results. Notably, (1) the arrangement of suitable sites is as important as their proportion, and (2) decreasing the proportion of suitable sites may result in a decrease in the fixation time of an allele.

Evolutionary dynamics in finite populations with zealots

We investigate evolutionary dynamics of two-strategy matrix games with zealots in finite populations. Zealots are assumed to take either strategy regardless of the fitness. When the strategy selected by the zealots is the same, the fixation of the strategy selected by the zealots is a trivial outcome. We study fixation time in this scenario. We show that the fixation time is divided into three main regimes, in one of which the fixation time is short, and in the other two the fixation time is exponentially long in terms of the population size. Different from the case without zealots, there is a threshold selection intensity below which the fixation is fast for an arbitrary payoff matrix. We illustrate our results with examples of various social dilemma games.

The characteristic trajectory of a fixing allele: a consequence of fictitious selection that arises from conditioning

This work is concerned with the historical progression, to fixation, of an allele in a finite population. This progression is characterized by the average frequency trajectory of alleles that achieve fixation before a given time, T. Under a diffusion analysis, the average trajectory, conditional on fixation by time T, is shown to be equivalent to the average trajectory in an unconditioned problem involving additional selection. We call this additional selection "fictitious selection"; it plays the role of a selective force in the unconditioned problem but does not exist in reality. It is a consequence of conditioning on fixation. The fictitious selection is frequency dependent and can be very large compared with any real selection that is acting. We derive an approximation for the characteristic trajectory of a fixing allele, when subject to real additive selection, from an unconditioned problem, where the total selection is a combination of real and fictitious selection. Trying to reproduce the characteristic trajectory from the action of additive selection, in an infinite population, can lead to estimates of the strength of the selection that deviate from the real selection by >1000% or have the opposite sign. Strong evolutionary forces may be invoked in problems where conditioning has been carried out, but these forces may largely be an outcome of the conditioning and hence may not have a real existence. The work presented here clarifies these issues and provides two useful tools for future analyses: the characteristic trajectory of a fixing allele and the force that primarily drives this, namely fictitious selection. These should prove useful in a number of areas of interest including coalescence with selection, experimental evolution, time series analyses of ancient DNA, game theory in finite populations, and the historical dynamics of selected alleles in wild populations.

The effect of population structure on the rate of evolution

Ecological factors exert a range of effects on the dynamics of the evolutionary process. A particularly marked effect comes from population structure, which can affect the probability that new mutations reach fixation. Our interest is in population structures, such as those depicted by 'star graphs', that amplify the effects of selection by further increasing the fixation probability of advantageous mutants and decreasing the fixation probability of disadvantageous mutants. The fact that star graphs increase the fixation probability of beneficial mutations has lead to the conclusion that evolution proceeds more rapidly in star-structured populations, compared with mixed (unstructured) populations. Here, we show that the effects of population structure on the rate of evolution are more complex and subtle than previously recognized and draw attention to the importance of fixation time. By comparing population structures that amplify selection with other population structures, both analytically and numerically, we show that evolution can slow down substantially even in populations where selection is amplified.

Stochastic formulation of ecological models and their applications

The increasing use of computer simulation by theoretical ecologists started a move away from models formulated at the population level towards individual-based models. However, many of the models studied at the individual level are not analysed mathematically and remain defined in terms of a computer algorithm. This is not surprising, given that they are intrinsically stochastic and require tools and techniques for their study that may be unfamiliar to ecologists. Here, we argue that the construction of ecological models at the individual level and their subsequent analysis is, in many cases, straightforward and leads to important insights. We discuss recent work that highlights the importance of stochastic effects for parameter ranges and systems where it was previously thought that such effects would be negligible.

Stability properties of underdominance in finite subdivided populations

IN ISOLATED populations underdominance leads to bistable evolutionary dynamics: below a certain mutant allele frequency the wildtype succeeds. Above this point, the potentially underdominant mutant allele fixes. In subdivided populations with gene flow there can be stable states with coexistence of wildtypes and mutants: polymorphism can be maintained because of a migration-selection equilibrium, i.e., selection against rare recent immigrant alleles that tend to be heterozygous. We focus on the stochastic evolutionary dynamics of systems where demographic fluctuations in the coupled populations are the main source of internal noise. We discuss the influence of fitness, migration rate, and the relative sizes of two interacting populations on the mean extinction times of a group of potentially underdominant mutant alleles. We classify realistic initial conditions according to their impact on the stochastic extinction process. Even in small populations, where demographic fluctuations are large, stability properties predicted from deterministic dynamics show remarkable robustness. Fixation of the mutant allele becomes unlikely but the time to its extinction can be long.

From genes to games: cooperation and cyclic dominance in meiotic drive

Evolutionary change can be described on a genotypic level or a phenotypic level. Evolutionary game theory is typically thought of as a phenotypic approach, although it is frequently argued that it can also be used to describe population genetic evolution. Interpreting the interaction between alleles in a diploid genome as a two player game leads to interesting alternative perspectives on genetic evolution. Here we focus on the case of meiotic drive and illustrate how meiotic drive can be directly and precisely interpreted as a social dilemma, such as the prisoners dilemma or the snowdrift game, in which the drive allele takes more than its fair share. Resistance to meiotic drive can lead to the well understood cyclic dominance found in the rock-paper-scissors game. This perspective is well established for the replicator dynamics, but there is still considerable ground for mutual inspiration between the two fields. For example, evolutionary game theorists can benefit from considering the stochastic evolutionary dynamics arising from finite population size. Population geneticists can benefit from game theoretic tools and perspectives on genetic evolution.

Universality of weak selection

Weak selection, which means a phenotype is slightly advantageous over another, is an important limiting case in evolutionary biology. Recently, it has been introduced into evolutionary game theory. In evolutionary game dynamics, the probability to be imitated or to reproduce depends on the performance in a game. The influence of the game on the stochastic dynamics in finite populations is governed by the intensity of selection. In many models of both unstructured and structured populations, a key assumption allowing analytical calculations is weak selection, which means that all individuals perform approximately equally well. In the weak selection limit many different microscopic evolutionary models have the same or similar properties. How universal is weak selection for those microscopic evolutionary processes? We answer this question by investigating the fixation probability and the average fixation time not only up to linear but also up to higher orders in selection intensity. We find universal higher order expansions, which allow a rescaling of the selection intensity. With this, we can identify specific models which violate (linear) weak selection results, such as the one-third rule of coordination games in finite but large populations.