Fixation time in evolutionary graphs: A mean-field approach

Effect of the degree of an initial mutant in Moran processes in structured populations

We study effects of the mutant's degree on the fixation probability, extinction, and fixation times in Moran processes on Erdös-Rényi and Barabási-Albert graphs. We performed stochastic simulations and used mean-field-type approximations to obtain analytical formulas. We showed that the initial placement of a mutant has a significant impact on the fixation probability and extinction time, while it has no effect on the fixation time. In both types of graphs, an increase in the degree of an initial mutant results in a decreased fixation probability and a shorter time to extinction. Our results extend previous ones to arbitrary fitness values.

Evolutionary graph theory beyond pairwise interactions: Higher-order network motifs shape times to fixation in structured populations

To design population topologies that can accelerate rates of solution discovery in directed evolution problems or for evolutionary optimization applications, we must first systematically understand how population structure shapes evolutionary outcome. Using the mathematical formalism of evolutionary graph theory, recent studies have shown how to topologically build networks of population interaction that increase probabilities of fixation of beneficial mutations, at the expense, however, of longer fixation times, which can slow down rates of evolution, under elevated mutation rate. Here we find that moving beyond dyadic interactions in population graphs is fundamental to explain the trade-offs between probabilities and times to fixation of new mutants in the population. We show that higher-order motifs, and in particular three-node structures, allow the tuning of times to fixation, without changes in probabilities of fixation. This gives a near-continuous control over achieving solutions that allow for a wide range of times to fixation. We apply our algorithms and analytic results to two evolutionary optimization problems and show that the rate of solution discovery can be tuned near continuously by adjusting the higher-order topology of the population. We show that the effects of population structure on the rate of evolution critically depend on the optimization landscape and find that decelerators, with longer times to fixation of new mutants, are able to reach the optimal solutions faster than accelerators in complex solution spaces. Our results highlight that no one population topology fits all optimization applications, and we provide analytic and computational tools that allow for the design of networks suitable for each specific task.

Categorizing update mechanisms for graph-structured metapopulations

The structure of a population strongly influences its evolutionary dynamics. In various settings ranging from biology to social systems, individuals tend to interact more often with those present in their proximity and rarely with those far away. A common approach to model the structure of a population is evolutionary graph theory. In this framework, each graph node is occupied by a reproducing individual. The links connect these individuals to their neighbours. The offspring can be placed on neighbouring nodes, replacing the neighbours-or the progeny of its neighbours can replace a node during the course of ongoing evolutionary dynamics. Extending this theory by replacing single individuals with subpopulations at nodes yields a graph-structured metapopulation. The dynamics between the different local subpopulations is set by an update mechanism. There are many such update mechanisms. Here, we classify update mechanisms for structured metapopulations, which allows to find commonalities between past work and illustrate directions for further research and current gaps of investigation.

Asymptotic Absorption-Time Distributions in Extinction-Prone Markov Processes

We characterize absorption-time distributions for birth-death Markov chains with an absorbing boundary. For "extinction-prone" chains (which drift on average toward the absorbing state) the asymptotic distribution is Gaussian, Gumbel, or belongs to a family of skewed distributions. The latter two cases arise when the dynamics slow down dramatically near the boundary. Several models of evolution, epidemics, and chemical reactions fall into these classes; in each case we establish new results for the absorption-time distribution. Applications to African sleeping sickness are discussed.

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.

The network structure affects the fixation probability when it couples to the birth-death dynamics in finite population

The study of evolutionary dynamics on graphs is an interesting topic for researchers in various fields of science and mathematics. In systems with finite population, different model dynamics are distinguished by their effects on two important quantities: fixation probability and fixation time. The isothermal theorem declares that the fixation probability is the same for a wide range of graphs and it only depends on the population size. This has also been proved for more complex graphs that are called complex networks. In this work, we propose a model that couples the population dynamics to the network structure and show that in this case, the isothermal theorem is being violated. In our model the death rate of a mutant depends on its number of neighbors, and neutral drift holds only in the average. We investigate the fixation probability behavior in terms of the complexity parameter, such as the scale-free exponent for the scale-free network and the rewiring probability for the small-world network.

In this work, we examine an evolutionary model that considers the effect of competition between the mutated individuals for acquiring more resources. This competition has an effect on the death rate of mutants. The model purposes that the death rate of each mutant depends on the number of its neighbors, while the average death rate in the population is equal to one. The birth rate for all individuals is assumed to be the same and equal to one. This situation is called here the ‘neutral drift in average’. We study the dynamics of the model on complex networks to take into account the non-uniformity of the environment. The results show the fixation probability differs from the Moran model. For the construction of this model, we were biologically motivated by the avascular tumour, which consists of a population of normal and cancer cells. The cancer cells likely need more oxygen than normal cells. There is a competition between cells for consuming oxygen, and cancer cells are far more sensitive to the amount of oxygen in the environment than normal cells. This means the death rate of a cancer cell grows by increasing the number of its neighbors.

Fitness dependence of the fixation-time distribution for evolutionary dynamics on graphs

Evolutionary graph theory models the effects of natural selection and random drift on structured populations of competing mutant and nonmutant individuals. Recent studies have found that fixation times in such systems often have right-skewed distributions. Little is known, however, about how these distributions and their skew depend on mutant fitness. Here we calculate the fitness dependence of the fixation-time distribution for the Moran Birth-death process in populations modeled by two extreme networks: the complete graph and the one-dimensional ring lattice, obtaining exact solutions in the limit of large network size. We find that with non-neutral fitness, the Moran process on the ring has normally distributed fixation times, independent of the relative fitness of mutants and nonmutants. In contrast, on the complete graph, the fixation-time distribution is a fitness-weighted convolution of two Gumbel distributions. When fitness is neutral, the fixation-time distribution jumps discontinuously and becomes highly skewed on both the complete graph and the ring. Even on these simple networks, the fixation-time distribution exhibits a rich fitness dependence, with discontinuities and regions of universality. Extensions of our results to two-fitness Moran models, times to partial fixation, and evolution on random networks are discussed.