Martingales and the fixation probability of high-dimensional evolutionary graphs

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.

Evolutionary dynamics of mutants that modify population structure

Natural selection is usually studied between mutants that differ in reproductive rate, but are subject to the same population structure. Here we explore how natural selection acts on mutants that have the same reproductive rate, but different population structures. In our framework, population structure is given by a graph that specifies where offspring can disperse. The invading mutant disperses offspring on a different graph than the resident wild-type. We find that more densely connected dispersal graphs tend to increase the invader's fixation probability, but the exact relationship between structure and fixation probability is subtle. We present three main results. First, we prove that if both invader and resident are on complete dispersal graphs, then removing a single edge in the invader's dispersal graph reduces its fixation probability. Second, we show that for certain island models higher invader's connectivity increases its fixation probability, but the magnitude of the effect depends on the exact layout of the connections. Third, we show that for lattices the effect of different connectivity is comparable to that of different fitness: for large population size, the invader's fixation probability is either constant or exponentially small, depending on whether it is more or less connected than the resident.

Spectral dynamics of guided edge removals and identifying transient amplifiers for death-Birth updating

The paper deals with two interrelated topics: (1) identifying transient amplifiers in an iterative process, and (2) analyzing the process by its spectral dynamics, which is the change in the graph spectra by edge manipulation. Transient amplifiers are networks representing population structures which shift the balance between natural selection and random drift. Thus, amplifiers are highly relevant for understanding the relationships between spatial structures and evolutionary dynamics. We study an iterative procedure to identify transient amplifiers for death-Birth updating. The algorithm starts with a regular input graph and iteratively removes edges until desired structures are achieved. Thus, a sequence of candidate graphs is obtained. The edge removals are guided by quantities derived from the sequence of candidate graphs. Moreover, we are interested in the Laplacian spectra of the candidate graphs and analyze the iterative process by its spectral dynamics. The results show that although transient amplifiers for death-Birth updating are generally rare, a substantial number of them can be obtained by the proposed procedure. The graphs identified share structural properties and have some similarity to dumbbell and barbell graphs. We analyze amplification properties of these graphs and also two more families of bell-like graphs and show that further transient amplifiers for death-Birth updating can be found. Finally, it is demonstrated that the spectral dynamics possesses characteristic features useful for deducing links between structural and spectral properties. These feature can also be taken for distinguishing transient amplifiers among evolutionary graphs in general.

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.

Suppressors of fixation can increase average fitness beyond amplifiers of selection

Evolutionary dynamics on graphs has remarkable features: For example, it has been shown that amplifiers of selection exist that-compared to an unstructured population-increase the fixation probability of advantageous mutations, while they decrease the fixation probability of disadvantageous mutations. So far, the theoretical literature has focused on the case of a single mutant entering a graph-structured population, asking how the graph affects the probability that a mutant takes over a population and the time until this typically happens. For continuously evolving systems, the more relevant case is that mutants constantly arise in an evolving population. Typically, such mutations occur with a small probability during reproduction events. We thus focus on the low mutation rate limit. The probability distribution for the fitness in this process converges to a steady state at long times. Intuitively, amplifiers of selection are expected to increase the population's mean fitness in the steady state. Similarly, suppressors of selection are expected to decrease the population's mean fitness in the steady state. However, we show that another set of graphs, called suppressors of fixation, can attain the highest population mean fitness. The key reason behind this is their ability to efficiently reject deleterious mutants. This illustrates the importance of the deleterious mutant regime for the long-term evolutionary dynamics, something that seems to have been overlooked in the literature so far.

Martingales and the fixation time of evolutionary graphs with arbitrary dimensionality

Evolutionary graph theory (EGT) investigates the Moran birth-death process constrained by graphs. Its two principal goals are to find the fixation probability and time for some initial population of mutants on the graph. The fixation probability of graphs has received considerable attention. Less is known about the distribution of fixation time. We derive clean, exact expressions for the full conditional characteristic functions (CCFs) of a close proxy to fixation and extinction times. That proxy is the number of times that the mutant population size changes before fixation or extinction. We derive these CCFs from a product martingale that we identify for an evolutionary graph with any number of partitions. The existence of that martingale only requires that the connections between those partitions are of a certain type. Our results are the first expressions for the CCFs of any proxy to fixation time on a graph with any number of partitions. The parameter dependence of our CCFs is explicit, so we can explore how they depend on graph structure. Martingales are a powerful approach to study principal problems of EGT. Their applicability is invariant to the number of partitions in a graph, so we can study entire families of graphs simultaneously.

Martingales and the characteristic functions of absorption time on bipartite graphs

Evolutionary graph theory investigates how spatial constraints affect processes that model evolutionary selection, e.g. the Moran process. Its principal goals are to find the fixation probability and the conditional distributions of fixation time, and show how they are affected by different graphs that impose spatial constraints. Fixation probabilities have generated significant attention, but much less is known about the conditional time distributions, even for simple graphs. Those conditional time distributions are difficult to calculate, so we consider a close proxy to it: the number of times the mutant population size changes before absorption. We employ martingales to obtain the conditional characteristic functions (CCFs) of that proxy for the Moran process on the complete bipartite graph. We consider the Moran process on the complete bipartite graph as an absorbing random walk in two dimensions. We then extend Wald's martingale approach to sequential analysis from one dimension to two. Our expressions for the CCFs are novel, compact, exact, and their parameter dependence is explicit. We show that our CCFs closely approximate those of absorption time. Martingales provide an elegant framework to solve principal problems of evolutionary graph theory. It should be possible to extend our analysis to more complex graphs than we show here.

Fixation probabilities in network structured meta-populations

The effect of population structure on evolutionary dynamics is a long-lasting research topic in evolutionary ecology and population genetics. Evolutionary graph theory is a popular approach to this problem, where individuals are located on the nodes of a network and can replace each other via the links. We study the effect of complex network structure on the fixation probability, but instead of networks of individuals, we model a network of sub-populations with a probability of migration between them. We ask how the structure of such a meta-population and the rate of migration affect the fixation probability. Many of the known results for networks of individuals carry over to meta-populations, in particular for regular networks or low symmetric migration probabilities. However, when patch sizes differ we find interesting deviations between structured meta-populations and networks of individuals. For example, a two patch structure with unequal population size suppresses selection for low migration probabilities.

Spectral analysis of transient amplifiers for death-birth updating constructed from regular graphs

A central question of evolutionary dynamics on graphs is whether or not a mutation introduced in a population of residents survives and eventually even spreads to the whole population, or becomes extinct. The outcome naturally depends on the fitness of the mutant and the rules by which mutants and residents may propagate on the network, but arguably the most determining factor is the network structure. Some structured networks are transient amplifiers. They increase for a certain fitness range the fixation probability of beneficial mutations as compared to a well-mixed population. We study a perturbation method for identifying transient amplifiers for death–birth updating. The method involves calculating the coalescence times of random walks on graphs and finding the vertex with the largest remeeting time. If the graph is perturbed by removing an edge from this vertex, there is a certain likelihood that the resulting perturbed graph is a transient amplifier. We test all pairwise nonisomorphic regular graphs up to a certain order and thus cover the whole structural range expressible by these graphs. For cubic and quartic regular graphs we find a sufficiently large number of transient amplifiers. For these networks we carry out a spectral analysis and show that the graphs from which transient amplifiers can be constructed share certain structural properties. Identifying spectral and structural properties may promote finding and designing such networks.

Graph-structured populations and the Hill-Robertson effect

The Hill-Robertson effect describes how, in a finite panmictic diploid population, selection at one diallelic locus reduces the fixation probability of a selectively favoured allele at a second, linked diallelic locus. Here we investigate the influence of population structure on the Hill-Robertson effect in a population of size N. We model population structure as a network by assuming that individuals occupy nodes on a graph connected by edges that link members who can reproduce with each other. Three regular networks (fully connected, ring and torus), two forms of scale-free network and a star are examined. We find that (i) the effect of population structure on the probability of fixation of the favourable allele is invariant for regular structures, but on some scale-free networks and a star, this probability is greatly reduced; (ii) compared to a panmictic population, the mean time to fixation of the favoured allele is much greater on a ring, torus and linear scale-free network, but much less on power-2 scale-free and star networks; (iii) the likelihood with which each of the four possible haplotypes eventually fix is similar across regular networks, but scale-free populations and the star are consistently less likely and much faster to fix the optimal haplotype; (iv) increasing recombination increases the likelihood of fixing the favoured haplotype across all structures, whereas the time to fixation of that haplotype usually increased, and (v) star-like structures were overwhelmingly likely to fix the least fit haplotype and did so significantly more rapidly than other populations. Last, we find that small (N < 64) panmictic populations do not exhibit the scaling property expected from Hill & Robertson (1966 Genet. Res. 8, 269-294. (doi:10.1017/S0016672300010156)).

Fixation probabilities in graph-structured populations under weak selection

A population's spatial structure affects the rate of genetic change and the outcome of natural selection. These effects can be modeled mathematically using the Birth-death process on graphs. Individuals occupy the vertices of a weighted graph, and reproduce into neighboring vertices based on fitness. A key quantity is the probability that a mutant type will sweep to fixation, as a function of the mutant's fitness. Graphs that increase the fixation probability of beneficial mutations, and decrease that of deleterious mutations, are said to amplify selection. However, fixation probabilities are difficult to compute for an arbitrary graph. Here we derive an expression for the fixation probability, of a weakly-selected mutation, in terms of the time for two lineages to coalesce. This expression enables weak-selection fixation probabilities to be computed, for an arbitrary weighted graph, in polynomial time. Applying this method, we explore the range of possible effects of graph structure on natural selection, genetic drift, and the balance between the two. Using exhaustive analysis of small graphs and a genetic search algorithm, we identify families of graphs with striking effects on fixation probability, and we analyze these families mathematically. Our work reveals the nuanced effects of graph structure on natural selection and neutral drift. In particular, we show how these notions depend critically on the process by which mutations arise.

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.

Limits on amplifiers of natural selection under death-Birth updating

The fixation probability of a single mutant invading a population of residents is among the most widely-studied quantities in evolutionary dynamics. Amplifiers of natural selection are population structures that increase the fixation probability of advantageous mutants, compared to well-mixed populations. Extensive studies have shown that many amplifiers exist for the Birth-death Moran process, some of them substantially increasing the fixation probability or even guaranteeing fixation in the limit of large population size. On the other hand, no amplifiers are known for the death-Birth Moran process, and computer-assisted exhaustive searches have failed to discover amplification. In this work we resolve this disparity, by showing that any amplification under death-Birth updating is necessarily bounded and transient. Our boundedness result states that even if a population structure does amplify selection, the resulting fixation probability is close to that of the well-mixed population. Our transience result states that for any population structure there exists a threshold r^⋆ such that the population structure ceases to amplify selection if the mutant fitness advantage r is larger than r^⋆. Finally, we also extend the above results to δ-death-Birth updating, which is a combination of Birth-death and death-Birth updating. On the positive side, we identify population structures that maintain amplification for a wide range of values r and δ. These results demonstrate that amplification of natural selection depends on the specific mechanisms of the evolutionary process.

Extensive literature exists on amplifiers of natural selection for the Birth-death Moran process, but no amplifiers are known for the death-Birth Moran process. Here we show that if amplifiers exist under death-Birth updating, they must be bounded and transient. Boundedness implies weak amplification, and transience implies amplification for only a limited range of the mutant fitness advantage. These results demonstrate that amplification depends on the specific mechanisms of the evolutionary process.

Transient amplifiers of selection and reducers of fixation for death-Birth updating on graphs

The spatial structure of an evolving population affects the balance of natural selection versus genetic drift. Some structures amplify selection, increasing the role that fitness differences play in determining which mutations become fixed. Other structures suppress selection, reducing the effect of fitness differences and increasing the role of random chance. This phenomenon can be modeled by representing spatial structure as a graph, with individuals occupying vertices. Births and deaths occur stochastically, according to a specified update rule. We study death-Birth updating: An individual is chosen to die and then its neighbors compete to reproduce into the vacant spot. Previous numerical experiments suggested that amplifiers of selection for this process are either rare or nonexistent. We introduce a perturbative method for this problem for weak selection regime, meaning that mutations have small fitness effects. We show that fixation probability under weak selection can be calculated in terms of the coalescence times of random walks. This result leads naturally to a new definition of effective population size. Using this and other methods, we uncover the first known examples of transient amplifiers of selection (graphs that amplify selection for a particular range of fitness values) for the death-Birth process. We also exhibit new families of “reducers of fixation”, which decrease the fixation probability of all mutations, whether beneficial or deleterious.

Natural selection is often thought of as “survival of the fittest”, but random chance plays a significant role in which mutations persist and which are eliminated. The balance of selection versus randomness is affected by spatial structure—how individuals are arranged within their habitat. Some structures amplify the effects of selection, so that only the fittest mutations are likely to persist. Others suppress the effects of selection, making the survival of genes primarily a matter of random chance. We study this question using a mathematical model called the “death-Birth process”. Previous studies have found that spatial structure rarely, if ever, amplifies selection for this process. Here we report that spatial structure can indeed amplify selection, at least for mutations with small fitness effects. We also identify structures that reduce the spread of any new mutation, whether beneficial or deleterious. Our work introduces new mathematical techniques for assessing how population structure affects natural selection.

Exploring and mapping the universe of evolutionary graphs identifies structural properties affecting fixation probability and time

Population structure can be modeled by evolutionary graphs, which can have a substantial influence on the fate of mutants. Individuals are located on the nodes of these graphs, competing to take over the graph via the links. Applications for this framework range from the ecology of river systems and cancer initiation in colonic crypts to biotechnological search for optimal mutations. In all these applications, both the probability of fixation and the associated time are of interest. We study this problem for all undirected and unweighted graphs up to a certain size. We devise a genetic algorithm to find graphs with high or low fixation probability and short or long fixation time and study their structure searching for common themes. Our work unravels structural properties that maximize or minimize fixation probability and time, which allows us to contribute to a first map of the universe of evolutionary graphs.