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 graph theory beyond single mutation dynamics: on how network-structured populations cross fitness landscapes

Spatially resolved datasets are revolutionizing knowledge in molecular biology, yet are under-utilized for questions in evolutionary biology. To gain insight from these large-scale datasets of spatial organization, we need mathematical representations and modeling techniques that can both capture their complexity, but also allow for mathematical tractability. Evolutionary graph theory utilizes the mathematical representation of networks as a proxy for heterogeneous population structure and has started to reshape our understanding of how spatial structure can direct evolutionary dynamics. However, previous results are derived for the case of a single new mutation appearing in the population and the role of network structure in shaping fitness landscape crossing is still poorly understood. Here we study how network-structured populations cross fitness landscapes and show that even a simple extension to a two-mutational landscape can exhibit complex evolutionary dynamics that cannot be predicted using previous single-mutation results. We show how our results can be intuitively understood through the lens of how the two main evolutionary properties of a network, the amplification and acceleration factors, change the expected fate of the intermediate mutant in the population and further discuss how to link these models to spatially resolved datasets of cellular organization.

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.

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.

Amplifiers of selection for the Moran process with both Birth-death and death-Birth updating

Populations evolve by accumulating advantageous mutations. Every population has some spatial structure that can be modeled by an underlying network. The network then influences the probability that new advantageous mutations fixate. Amplifiers of selection are networks that increase the fixation probability of advantageous mutants, as compared to the unstructured fully-connected network. Whether or not a network is an amplifier depends on the choice of the random process that governs the evolutionary dynamics. Two popular choices are Moran process with Birth-death updating and Moran process with death-Birth updating. Interestingly, while some networks are amplifiers under Birth-death updating and other networks are amplifiers under death-Birth updating, so far no spatial structures have been found that function as an amplifier under both types of updating simultaneously. In this work, we identify networks that act as amplifiers of selection under both versions of the Moran process. The amplifiers are robust, modular, and increase fixation probability for any mutant fitness advantage in a range r ∈ (1, 1.2). To complement this positive result, we also prove that for certain quantities closely related to fixation probability, it is impossible to improve them simultaneously for both versions of the Moran process. Together, our results highlight how the two versions of the Moran process differ and what they have in common.

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.

Symmetry in models of natural selection

Symmetry arguments are frequently used-often implicitly-in mathematical modelling of natural selection. Symmetry simplifies the analysis of models and reduces the number of distinct population states to be considered. Here, I introduce a formal definition of symmetry in mathematical models of natural selection. This definition applies to a broad class of models that satisfy a minimal set of assumptions, using a framework developed in previous works. In this framework, population structure is represented by a set of sites at which alleles can live, and transitions occur via replacement of some alleles by copies of others. A symmetry is defined as a permutation of sites that preserves probabilities of replacement and mutation. The symmetries of a given selection process form a group, which acts on population states in a way that preserves the Markov chain representing selection. Applying classical results on group actions, I formally characterize the use of symmetry to reduce the states of this Markov chain, and obtain bounds on the number of states in the reduced chain.

Fixation probability in evolutionary dynamics on switching temporal networks

Population structure has been known to substantially affect evolutionary dynamics. Networks that promote the spreading of fitter mutants are called amplifiers of selection, and those that suppress the spreading of fitter mutants are called suppressors of selection. Research in the past two decades has found various families of amplifiers while suppressors still remain somewhat elusive. It has also been discovered that most networks are amplifiers of selection under the birth-death updating combined with uniform initialization, which is a standard condition assumed widely in the literature. In the present study, we extend the birth-death processes to temporal (i.e., time-varying) networks. For the sake of tractability, we restrict ourselves to switching temporal networks, in which the network structure deterministically alternates between two static networks at constant time intervals or stochastically in a Markovian manner. We show that, in a majority of cases, switching networks are less amplifying than both of the two static networks constituting the switching networks. Furthermore, most small switching networks, i.e., networks on six nodes or less, are suppressors, which contrasts to the case of static networks.

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.

Fixation dynamics on hypergraphs

Hypergraphs have been a useful tool for analyzing population dynamics such as opinion formation and the public goods game occurring in overlapping groups of individuals. In the present study, we propose and analyze evolutionary dynamics on hypergraphs, in which each node takes one of the two types of different but constant fitness values. For the corresponding dynamics on conventional networks, under the birth-death process and uniform initial conditions, most networks are known to be amplifiers of natural selection; amplifiers by definition enhance the difference in the strength of the two competing types in terms of the probability that the mutant type fixates in the population. In contrast, we provide strong computational evidence that a majority of hypergraphs are suppressors of selection under the same conditions by combining theoretical and numerical analyses. We also show that this suppressing effect is not explained by one-mode projection, which is a standard method for expressing hypergraph data as a conventional network. Our results suggest that the modeling framework for structured populations in addition to the specific network structure is an important determinant of evolutionary dynamics, paving a way to studying fixation dynamics on higher-order networks including hypergraphs.

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.

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.

Bernoulli and binomial proliferation on evolutionary graphs

In this paper we introduce random proliferation models on graphs. We consider two types of particles: type-1/mutant/invader/red particles proliferates on a population of type-2/wild-type/resident/blue particles. Unlike the well-known Moran model on graphs -as introduced in Lieberman et al. (2005)-, type-1 particles can occupy in a single iteration several neighbouring sites previously occupied by type-2 particles. Two variants are considered, depending on the random distribution involving the proliferation mechanism: Bernoulli and binomial proliferation. By comparison with fixation probability of type-1 particles in the Moran process, critical parameters are introduced. Properties of proliferation are studied and some particular cases are analytically solved. Finally, by updating the parameters that drive the processes through a density-dependent mechanism, it is possible to capture additional relevant features as fluctuating waves of type-1 particles over long periods of time. In fact, the models can be adapted to tackle more general, complex and realistic situations.

Toward a Universal Model for Spatially Structured Populations

A key question in evolution is how likely a mutant is to take over. This depends on natural selection and on stochastic fluctuations. Population spatial structure can impact mutant fixation probabilities. We introduce a model for structured populations on graphs that generalizes previous ones by making migrations independent of birth and death. We demonstrate that by tuning migration asymmetry, the star graph transitions from amplifying to suppressing natural selection. The results from our model are universal in the sense that they do not hinge on a modeling choice of microscopic dynamics or update rules. Instead, they depend on migration asymmetry, which can be experimentally tuned and measured.

Fast and strong amplifiers of natural selection

Selection and random drift determine the probability that novel mutations fixate in a population. Population structure is known to affect the dynamics of the evolutionary process. Amplifiers of selection are population structures that increase the fixation probability of beneficial mutants compared to well-mixed populations. Over the past 15 years, extensive research has produced remarkable structures called strong amplifiers which guarantee that every beneficial mutation fixates with high probability. But strong amplification has come at the cost of considerably delaying the fixation event, which can slow down the overall rate of evolution. However, the precise relationship between fixation probability and time has remained elusive. Here we characterize the slowdown effect of strong amplification. First, we prove that all strong amplifiers must delay the fixation event at least to some extent. Second, we construct strong amplifiers that delay the fixation event only marginally as compared to the well-mixed populations. Our results thus establish a tight relationship between fixation probability and time: Strong amplification always comes at a cost of a slowdown, but more than a marginal slowdown is not needed.

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 evolutionary dynamics under weak selection

In evolutionary dynamics, a key measure of a mutant trait's success is the probability that it takes over the population given some initial mutant-appearance distribution. This "fixation probability" is difficult to compute in general, as it depends on the mutation's effect on the organism as well as the population's spatial structure, mating patterns, and other factors. In this study, we consider weak selection, which means that the mutation's effect on the organism is small. We obtain a weak-selection perturbation expansion of a mutant's fixation probability, from an arbitrary initial configuration of mutant and resident types. Our results apply to a broad class of stochastic evolutionary models, in which the size and spatial structure are arbitrary (but fixed). The problem of whether selection favors a given trait is thereby reduced from exponential to polynomial complexity in the population size, when selection is weak. We conclude by applying these methods to obtain new results for evolutionary dynamics on graphs.

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.

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.

Environmental spatial and temporal variability and its role in non-favoured mutant dynamics

Understanding how environmental variability (or randomness) affects evolution is of fundamental importance for biology. The presence of temporal or spatial variability significantly affects the competition dynamics in populations, and gives rise to some counterintuitive observations. In this paper, we consider both birth-death (BD) or death-birth (DB) Moran processes, which are set up on a circular or a complete graph. We investigate spatial and temporal variability affecting division and/or death parameters. Assuming that mutant and wild-type fitness parameters are drawn from an identical distribution, we study mutant fixation probability and timing. We demonstrate that temporal and spatial types of variability possess fundamentally different properties. Under temporal randomness, in a completely mixed system, minority mutants experience (i) higher than neutral fixation probability and a higher mean conditional fixation time, if the division rates are affected by randomness and (ii) lower fixation probability and lower mean conditional fixation time if the death rates are affected. Once spatial restrictions are imposed, however, these effects completely disappear, and mutants in a circular graph experience neutral dynamics, but only for the DB update rule in case (i) and for the BD rule in case (ii) above. In contrast to this, in the case of spatially variable environment, both for BD/DB processes, both for complete/circular graph and both for division/death rates affected, minority mutants experience a higher than neutral probability of fixation. Fixation time, however, is increased by randomness on a circle, while it decreases for complete graphs under random division rates. A basic difference between temporal and spatial kinds of variability is the types of correlations that occur in the system. Under temporal randomness, mutants are spatially correlated with each other (they simply have equal fitness values at a given moment of time; the same holds for wild-types). Under spatial randomness, there are subtler, temporal correlations among mutant and wild-type cells, which manifest themselves by cells of each type 'claiming' better spots for themselves. Applications of this theory include cancer generation and biofilm dynamics.

Motion, fixation probability and the choice of an evolutionary process

Seemingly minor details of mathematical and computational models of evolution are known to change the effect of population structure on the outcome of evolutionary processes. For example, birth-death dynamics often result in amplification of selection, while death-birth processes have been associated with suppression. In many biological populations the interaction structure is not static. Instead, members of the population are in motion and can interact with different individuals at different times. In this work we study populations embedded in a flowing medium; the interaction network is then time dependent. We use computer simulations to investigate how this dynamic structure affects the success of invading mutants, and compare these effects for different coupled birth and death processes. Specifically, we show how the speed of the motion impacts the fixation probability of an invading mutant. Flows of different speeds interpolate between evolutionary dynamics on fixed heterogeneous graphs and well-stirred populations; this allows us to systematically compare against known results for static structured populations. We find that motion has an active role in amplifying or suppressing selection by fragmenting and reconnecting the interaction graph. While increasing flow speeds suppress selection for most evolutionary models, we identify characteristic responses to flow for the different update rules we test. In particular we find that selection can be maximally enhanced or suppressed at intermediate flow speeds.

Whether a mutation spreads in a population or not is one of the most important questions in biology. The evolution of cancer and antibiotic resistance, for example, are mediated by invading mutants. Recent work has shown that population structure can have important consequences for the outcome of evolution. For instance, a mutant can have a higher or a lower chance of invasion than in unstructured populations. These effects can depend on seemingly minor details of the evolutionary model, such as the order of birth and death events. Many biological populations are in motion, for example due to external stirring. Experimentally this is known to be important; the performance of mutants in E. coli populations, for example, depends on the rate of mixing. Here, we focus on simulations of populations in a flowing medium, and compare the success of a mutant for different flow speeds. We contrast different evolutionary models, and identify what features of the evolutionary model affect mutant success for different speeds of the flow. We find that the chance of mutant invasion can be at its highest (or lowest) at intermediate flow speeds, depending on the order in which birth and death events occur in the evolutionary process.

Population structure determines the tradeoff between fixation probability and fixation time

The rate of biological evolution depends on the fixation probability and on the fixation time of new mutants. Intensive research has focused on identifying population structures that augment the fixation probability of advantageous mutants. But these amplifiers of natural selection typically increase fixation time. Here we study population structures that achieve a tradeoff between fixation probability and time. First, we show that no amplifiers can have an asymptotically lower absorption time than the well-mixed population. Then we design population structures that substantially augment the fixation probability with just a minor increase in fixation time. Finally, we show that those structures enable higher effective rate of evolution than the well-mixed population provided that the rate of generating advantageous mutants is relatively low. Our work sheds light on how population structure affects the rate of evolution. Moreover, our structures could be useful for lab-based, medical, or industrial applications of evolutionary optimization.

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.

Dynamics of multiplayer games on complex networks using territorial interactions

The modeling of evolution in structured populations has been significantly advanced by evolutionary graph theory, which incorporates pairwise relationships between individuals on a network. More recently, a new framework has been developed to allow for multiplayer interactions of variable size in more flexible and potentially changing population structures. While the theory within this framework has been developed and simple structures considered, there has been no systematic consideration of a large range of different population structures, which is the subject of this paper. We consider a large range of underlying graphical structures for the territorial raider model, the most commonly used model in the new structure, and consider a variety of important properties of our structures with the aim of finding factors that determine the fixation probability of mutants. We find that the graphical temperature and the average group size, as previously defined, are strong predictors of fixation probability, while all other properties considered are poor predictors, although the clustering coefficient is a useful secondary predictor when combined with either temperature or group size. The relationship between temperature or average group size and fixation probability is sometimes, however, nonmonotonic, with a directional reverse occurring around the temperature associated with what we term "completely mixed" populations in the case of the hawk-dove game, but not the public goods game.

Environmental fitness heterogeneity in the Moran process

Many mathematical models of evolution assume that all individuals experience the same environment. Here, we study the Moran process in heterogeneous environments. The population is of finite size with two competing types, which are exposed to a fixed number of environmental conditions. Reproductive rate is determined by both the type and the environment. We first calculate the condition for selection to favour the mutant relative to the resident wild-type. In large populations, the mutant is favoured if and only if the mutant's spatial average reproductive rate exceeds that of the resident. But environmental heterogeneity elucidates an interesting asymmetry between the mutant and the resident. Specifically, mutant heterogeneity suppresses its fixation probability; if this heterogeneity is strong enough, it can even completely offset the effects of selection (including in large populations). By contrast, resident heterogeneity has no effect on a mutant's fixation probability in large populations and can amplify it in small populations.

Evolutionary regime transitions in structured populations

The evolutionary dynamics of a finite population where resident individuals are replaced by mutant ones depends on its spatial structure. Usually, the population adopts the form of an undirected graph where the place occupied by each individual is represented by a vertex and it is bidirectionally linked to the places that can be occupied by its offspring. There are undirected graph structures that act as amplifiers of selection increasing the probability that the offspring of an advantageous mutant spreads through the graph reaching any vertex. But there also are undirected graph structures acting as suppressors of selection where this probability is less than that of the same individual placed in a homogeneous population. Here, firstly, we present the distribution of these evolutionary regimes for all undirected graphs with N ≤ 10 vertices. Some of them exhibit transitions between different regimes when the mutant fitness increases. In particular, as it has been already observed for small-order random graphs, we show that most graphs of order N ≤ 10 are amplifiers of selection. Secondly, we describe examples of amplifiers of order 7 that become suppressors from some critical value. In fact, for graphs of order N ≤ 7, we apply computer-aided techniques to symbolically compute their fixation probability and then their evolutionary regime, as well as the critical values for which they change their regime. Thirdly, the same technique is applied to some families of highly symmetrical graphs as a mean to explore methods of suppressing selection. The existence of suppression mechanisms that reverse an amplification regime when fitness increases could have a great interest in biology and network science. Finally, the analysis of all graphs from order 8 to order 10 reveals a complex and rich evolutionary dynamics, with multiple transitions between different regimes, which have not been examined in detail until now.

A mathematical formalism for natural selection with arbitrary spatial and genetic structure

We define a general class of models representing natural selection between two alleles. The population size and spatial structure are arbitrary, but fixed. Genetics can be haploid, diploid, or otherwise; reproduction can be asexual or sexual. Biological events (e.g. births, deaths, mating, dispersal) depend in arbitrary fashion on the current population state. Our formalism is based on the idea of genetic sites. Each genetic site resides at a particular locus and houses a single allele. Each individual contains a number of sites equal to its ploidy (one for haploids, two for diploids, etc.). Selection occurs via replacement events, in which alleles in some sites are replaced by copies of others. Replacement events depend stochastically on the population state, leading to a Markov chain representation of natural selection. Within this formalism, we define reproductive value, fitness, neutral drift, and fixation probability, and prove relationships among them. We identify four criteria for evaluating which allele is selected and show that these become equivalent in the limit of low mutation. We then formalize the method of weak selection. The power of our formalism is illustrated with applications to evolutionary games on graphs and to selection in a haplodiploid population.

Invasion and effective size of graph-structured populations

Population structure can strongly affect evolutionary dynamics. The most general way to describe population structures are graphs. An important observable on evolutionary graphs is the probability that a novel mutation spreads through the entire population. But what drives this spread of a mutation towards fixation? Here, we propose a novel way to understand the forces driving fixation by borrowing techniques from evolutionary demography to quantify the invasion fitness and the effective population size for different graphs. Our method is very general and even applies to weighted graphs with node dependent fitness. However, we focus on analytical results for undirected graphs with node independent fitness. The method will allow to conceptually integrate evolutionary graph theory with theoretical genetics of structured populations.

Evolving populations, companies, social circles are networks in which genes, resources and ideas circulate. Imagine a useful novelty is introduced in the network: a favorable mutation, a new product concept or a smart idea. Will this novelty be retained and propagated through the network or rather lost? Using tools originally devised for demographic research, we model the dynamics of the very initial spread of a useful novelty in a network. The network structure has a strong impact on these dynamics by affecting the effective network size through random effects. This effective network size, which correlates with the probability that a novelty spreads and is different from the actual size (i.e. number of nodes), varies with network structure. The effective size can even become independent of the actual network size and thus remain very small even for huge networks.

Construction of arbitrarily strong amplifiers of natural selection using evolutionary graph theory

Because of the intrinsic randomness of the evolutionary process, a mutant with a fitness advantage has some chance to be selected but no certainty. Any experiment that searches for advantageous mutants will lose many of them due to random drift. It is therefore of great interest to find population structures that improve the odds of advantageous mutants. Such structures are called amplifiers of natural selection: they increase the probability that advantageous mutants are selected. Arbitrarily strong amplifiers guarantee the selection of advantageous mutants, even for very small fitness advantage. Despite intensive research over the past decade, arbitrarily strong amplifiers have remained rare. Here we show how to construct a large variety of them. Our amplifiers are so simple that they could be useful in biotechnology, when optimizing biological molecules, or as a diagnostic tool, when searching for faster dividing cells or viruses. They could also occur in natural population structures.

Martingales and the fixation probability of high-dimensional evolutionary graphs

A principal problem of evolutionary graph theory is to find the probability that an initial mutant population will fix on a graph, i.e. that the mutants will eventually replace the indigenous population. This problem is particularly difficult when the dimensionality of a graph is high. Martingales can yield compact and exact expressions for the fixation probability of an evolutionary graph. Crucially, the tractability of martingales does not necessarily depend on the dimensionality of a graph. We will use martingales to obtain the exact fixation probability of graphs with high dimensionality, specifically k-partite graphs (or 'circular flows') and megastars (or 'superstars'). To do so, we require that the edges of the graph permit mutants to reproduce in one direction and indigenous in the other. The resultant expressions for fixation probabilities explicitly show their dependence on the parameters that describe the graph structure, and on the starting position(s) of the initial mutant population. In particular, we will investigate the effect of funneling on the fixation probability of k-partite graphs, as well as the effect of placing an initial mutant in different partitions. These are the first exact and explicit results reported for the fixation probability of evolutionary graphs with dimensionality greater than 2, that are valid over all parameter space. It might be possible to extend these results to obtain fixation probabilities of high-dimensional evolutionary graphs with undirected or directed connections. Martingales are a formidable theoretical tool that can solve fundamental problems in evolutionary graph theory, often within a few lines of straightforward mathematics.

From quasispecies to quasispaces: coding and cooperation in chemical and electronic systems

This contribution addresses the physical roles of spatial structures, either externally imposed or generated through self-assembly, either passive or active, on the physical chemistry of evolution. Starting with simple diffusion in closed capillaries, a one-dimensional space, it covers eight aspects of experimental and theoretical research into the interaction of evolution with spatial structures: in various dimensions, including hitherto unexplored ones, spanning from externally defined physical spaces to actively tailored spaces, assembled by the evolving components themselves. As such, it contains some original research by the author as well as tracing how other insights grew over three decades out of the mentorship of Manfred Eigen in the 1980s. Much of the early interest in spatial structures centres on its role in stabilizing higher order cooperative structures involving the coevolution of different molecules, as the genetic coding system exemplifies. Modern nanotechnology enables the design and construction of genetically encoded variants of smart components that can actively control both the proliferation of molecules and the structuring of space. A key role for this article is to show the continuity in this line of enquiry, beginning with quasispecies and projecting to autonomous microparticles with electronic genomes able to form programmable quasispaces.

Effects of motion in structured populations

In evolutionary processes, population structure has a substantial effect on natural selection. Here, we analyse how motion of individuals affects constant selection in structured populations. Motion is relevant because it leads to changes in the distribution of types as mutations march towards fixation or extinction. We describe motion as the swapping of individuals on graphs, and more generally as the shuffling of individuals between reproductive updates. Beginning with a one-dimensional graph, the cycle, we prove that motion suppresses natural selection for death-birth (DB) updating or for any process that combines birth-death (BD) and DB updating. If the rule is purely BD updating, no change in fixation probability appears in the presence of motion. We further investigate how motion affects evolution on the square lattice and weighted graphs. In the case of weighted graphs, we find that motion can be either an amplifier or a suppressor of natural selection. In some cases, whether it is one or the other can be a function of the relative reproductive rate, indicating that motion is a subtle and complex attribute of evolving populations. As a first step towards understanding less restricted types of motion in evolutionary graph theory, we consider a similar rule on dynamic graphs induced by a spatial flow and find qualitatively similar results, indicating that continuous motion also suppresses natural selection.

Suppressors of selection

Inspired by recent works on evolutionary graph theory, an area of growing interest in mathematical and computational biology, we present examples of undirected structures acting as suppressors of selection for any fitness value r > 1. This means that the average fixation probability of an advantageous mutant or invader individual placed at some node is strictly less than that of this individual placed in a well-mixed population. This leads the way to study more robust structures less prone to invasion, contrary to what happens with the amplifiers of selection where the fixation probability is increased on average for advantageous invader individuals. A few families of amplifiers are known, although some effort was required to prove it. Here, we use computer aided techniques to find an exact analytical expression of the fixation probability for some graphs of small order (equal to 6, 8 and 10) proving that selection is effectively reduced for r > 1. Some numerical experiments using Monte Carlo methods are also performed for larger graphs and some variants.

Takeover times for a simple model of network infection

We study a stochastic model of infection spreading on a network. At each time step a node is chosen at random, along with one of its neighbors. If the node is infected and the neighbor is susceptible, the neighbor becomes infected. How many time steps T does it take to completely infect a network of N nodes, starting from a single infected node? An analogy to the classic "coupon collector" problem of probability theory reveals that the takeover time T is dominated by extremal behavior, either when there are only a few infected nodes near the start of the process or a few susceptible nodes near the end. We show that for N≫1, the takeover time T is distributed as a Gumbel distribution for the star graph, as the convolution of two Gumbel distributions for a complete graph and an Erdős-Rényi random graph, as a normal for a one-dimensional ring and a two-dimensional lattice, and as a family of intermediate skewed distributions for d-dimensional lattices with d≥3 (these distributions approach the convolution of two Gumbel distributions as d approaches infinity). Connections to evolutionary dynamics, cancer, incubation periods of infectious diseases, first-passage percolation, and other spreading phenomena in biology and physics are discussed.

Amplification on Undirected Population Structures: Comets Beat Stars

The fixation probability is the probability that a new mutant introduced in a homogeneous population eventually takes over the entire population. The fixation probability is a fundamental quantity of natural selection, and known to depend on the population structure. Amplifiers of natural selection are population structures which increase the fixation probability of advantageous mutants, as compared to the baseline case of well-mixed populations. In this work we focus on symmetric population structures represented as undirected graphs. In the regime of undirected graphs, the strongest amplifier known has been the Star graph, and the existence of undirected graphs with stronger amplification properties has remained open for over a decade. In this work we present the Comet and Comet-swarm families of undirected graphs. We show that for a range of fitness values of the mutants, the Comet and Comet-swarm graphs have fixation probability strictly larger than the fixation probability of the Star graph, for fixed population size and at the limit of large populations, respectively.

Should tissue structure suppress or amplify selection to minimize cancer risk?

Background

It has been frequently argued that tissues evolved to suppress the accumulation of growth enhancing cancer inducing mutations. A prominent example is the hierarchical structure of tissues with high cell turnover, where a small number of tissue specific stem cells produces a large number of specialized progeny during multiple differentiation steps. Another well known mechanism is the spatial organization of stem cell populations and it is thought that this organization suppresses fitness enhancing mutations. However, in small populations the suppression of advantageous mutations typically also implies an increased accumulation of deleterious mutations. Thus, it becomes an important question whether the suppression of potentially few advantageous mutations outweighs the combined effects of many deleterious mutations.

Results

We argue that the distribution of mutant fitness effects, e.g. the probability to hit a strong driver compared to many deleterious mutations, is crucial for the optimal organization of a cancer suppressing tissue architecture and should be taken into account in arguments for the evolution of such tissues.

Conclusion

We show that for systems that are composed of few cells reflecting the typical organization of a stem cell niche, amplification or suppression of selection can arise from subtle changes in the architecture. Moreover, we discuss special tissue structures that can suppress most types of non-neutral mutations simultaneously.

Reviewers

This article was reviewed by Benjamin Allen, Andreas Deutsch and Ignacio Rodriguez-Brenes. For the full reviews, please go to the Reviewers’ comments section.

Computational complexity of ecological and evolutionary spatial dynamics

There are deep, yet largely unexplored, connections between computer science and biology. Both disciplines examine how information proliferates in time and space. Central results in computer science describe the complexity of algorithms that solve certain classes of problems. An algorithm is deemed efficient if it can solve a problem in polynomial time, which means the running time of the algorithm is a polynomial function of the length of the input. There are classes of harder problems for which the fastest possible algorithm requires exponential time. Another criterion is the space requirement of the algorithm. There is a crucial distinction between algorithms that can find a solution, verify a solution, or list several distinct solutions in given time and space. The complexity hierarchy that is generated in this way is the foundation of theoretical computer science. Precise complexity results can be notoriously difficult. The famous question whether polynomial time equals nondeterministic polynomial time (i.e., P = NP) is one of the hardest open problems in computer science and all of mathematics. Here, we consider simple processes of ecological and evolutionary spatial dynamics. The basic question is: What is the probability that a new invader (or a new mutant) will take over a resident population? We derive precise complexity results for a variety of scenarios. We therefore show that some fundamental questions in this area cannot be answered by simple equations (assuming that P is not equal to NP).

Stability of underdominant genetic polymorphisms in population networks

Heterozygote disadvantage is potentially a potent driver of population genetic divergence. Also referred to as underdominance, this phenomena describes a situation where a genetic heterozygote has a lower overall fitness than either homozygote. Attention so far has mostly been given to underdominance within a single population and the maintenance of genetic differences between two populations exchanging migrants. Here we explore the dynamics of an underdominant system in a network of multiple discrete, yet interconnected, populations. Stability of genetic differences in response to increases in migration in various topological networks is assessed. The network topology can have a dominant and occasionally non-intuitive influence on the genetic stability of the system.

Cellular cooperation with shift updating and repulsion

Population structure can facilitate evolution of cooperation. In a structured population, cooperators can form clusters which resist exploitation by defectors. Recently, it was observed that a shift update rule is an extremely strong amplifier of cooperation in a one dimensional spatial model. For the shift update rule, an individual is chosen for reproduction proportional to fecundity; the offspring is placed next to the parent; a random individual dies. Subsequently, the population is rearranged (shifted) until all individual cells are again evenly spaced out. For large population size and a one dimensional population structure, the shift update rule favors cooperation for any benefit-to-cost ratio greater than one. But every attempt to generalize shift updating to higher dimensions while maintaining its strong effect has failed. The reason is that in two dimensions the clusters are fragmented by the movements caused by rearranging the cells. Here we introduce the natural phenomenon of a repulsive force between cells of different types. After a birth and death event, the cells are being rearranged minimizing the overall energy expenditure. If the repulsive force is sufficiently high, shift becomes a strong promoter of cooperation in two dimensions.