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

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.

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 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.

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.

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.

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.

Counterintuitive properties of evolutionary measures: A stochastic process study in cyclic population structures with periodic environments

Local environmental interactions are a major factor in determining the success of a new mutant in structured populations. Spatial variations in the concentration of genotype-specific resources change the fitness of competing strategies locally and thus can drastically change the outcome of evolutionary processes in unintuitive ways. The question is how such local environmental variations in network population structures change the condition for selection and fixation probability of an advantageous (or deleterious) mutant. We consider linear graph structures and focus on the case where resources have a spatial periodic pattern. This is the simplest model with two parameters, length scale and fitness scales, representing heterogeneity. We calculate fixation probability and fixation times for a constant population birth-death process as fitness heterogeneity and period vary. Fixation probability is affected by not only the level of fitness heterogeneity but also spatial scale of resources variations set by period of distribution T. We identify conditions for which a previously a deleterious mutant (in a uniform environment) becomes beneficial as fitness heterogeneity is increased. We observe cases where the fixation probability of both mutant and resident types are more than their neutral value, 1/N, simultaneously. This coincides with exponential increase in time to fixation which points to potential coexistence of resident and mutant types. Finally, we discuss the effect of the 'fitness shift' where the fitness function of two types has a phase difference. We observe significant increases (or decreases) in the fixation probability of the mutant as a result of such phase shift.

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.

Evolution of cooperation with asymmetric social interactions

How cooperation emerges in human societies is both an evolutionary enigma and a practical problem with tangible implications for societal health. Population structure has long been recognized as a catalyst for cooperation because local interactions facilitate reciprocity. Analysis of population structure typically assumes bidirectional social interactions. But human social interactions are often unidirectional-where one individual has the opportunity to contribute altruistically to another, but not conversely-as the result of organizational hierarchies, social stratification, popularity effects, and endogenous mechanisms of network growth. Here we expand the theory of cooperation in structured populations to account for both uni- and bidirectional social interactions. Even though unidirectional interactions remove the opportunity for reciprocity, we find that cooperation can nonetheless be favored in directed social networks and that cooperation is provably maximized for networks with an intermediate proportion of unidirectional interactions, as observed in many empirical settings. We also identify two simple structural motifs that allow efficient modification of interaction directions to promote cooperation by orders of magnitude. We discuss how our results relate to the concepts of generalized and indirect reciprocity.

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.

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.

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.

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.

Normal tissue architecture determines the evolutionary course of cancer

Cancer growth can be described as a caricature of the renewal process of the tissue of origin, where the tissue architecture has a strong influence on the evolutionary dynamics within the tumor. Using a classic, well-studied model of tumor evolution (a passenger-driver mutation model) we systematically alter spatial constraints and cell mixing rates to show how tissue structure influences functional (driver) mutations and genetic heterogeneity over time. This approach explores a key mechanism behind both inter-patient and intratumoral tumor heterogeneity: competition for space. Time-varying competition leads to an emergent transition from Darwinian premalignant growth to subsequent invasive neutral tumor growth. Initial spatial constraints determine the emergent mode of evolution (Darwinian to neutral) without a change in cell-specific mutation rate or fitness effects. Driver acquisition during the Darwinian precancerous stage may be modulated en route to neutral evolution by the combination of two factors: spatial constraints and limited cellular mixing. These two factors occur naturally in ductal carcinomas, where the branching topology of the ductal network dictates spatial constraints and mixing rates.

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.

The Moran process on 2-chromatic graphs

Resources are rarely distributed uniformly within a population. Heterogeneity in the concentration of a drug, the quality of breeding sites, or wealth can all affect evolutionary dynamics. In this study, we represent a collection of properties affecting the fitness at a given location using a color. A green node is rich in resources while a red node is poorer. More colors can represent a broader spectrum of resource qualities. For a population evolving according to the birth-death Moran model, the first question we address is which structures, identified by graph connectivity and graph coloring, are evolutionarily equivalent. We prove that all properly two-colored, undirected, regular graphs are evolutionarily equivalent (where “properly colored” means that no two neighbors have the same color). We then compare the effects of background heterogeneity on properly two-colored graphs to those with alternative schemes in which the colors are permuted. Finally, we discuss dynamic coloring as a model for spatiotemporal resource fluctuations, and we illustrate that random dynamic colorings often diminish the effects of background heterogeneity relative to a proper two-coloring.

Heterogeneity in environmental conditions can have profound effects on long-term evolutionary outcomes in structured populations. We consider a population evolving on a colored graph, wherein the color of a node represents the resources at that location. Using a combination of analytical and numerical methods, we quantify the effects of background heterogeneity on a population’s dynamics. In addition to considering the notion of an “optimal” coloring with respect to mutant invasion, we also study the effects of dynamic spatial redistribution of resources as the population evolves. Although the effects of static background heterogeneity can be quite striking, these effects are often attenuated by the movement (or “flow”) of the underlying resources.

Topological constraints in early multicellularity favor reproductive division of labor

Reproductive division of labor (e.g. germ-soma specialization) is a hallmark of the evolution of multicellularity, signifying the emergence of a new type of individual and facilitating the evolution of increased organismal complexity. A large body of work from evolutionary biology, economics, and ecology has shown that specialization is beneficial when further division of labor produces an accelerating increase in absolute productivity (i.e. productivity is a convex function of specialization). Here we show that reproductive specialization is qualitatively different from classical models of resource sharing, and can evolve even when the benefits of specialization are saturating (i.e. productivity is a concave function of specialization). Through analytical theory and evolutionary individual-based simulations, we demonstrate that reproductive specialization is strongly favored in sparse networks of cellular interactions that reflect the morphology of early, simple multicellular organisms, highlighting the importance of restricted social interactions in the evolution of reproductive specialization.

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.

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.

Computational Complexity as an Ultimate Constraint on Evolution

Experiments show that evolutionary fitness landscapes can have a rich combinatorial structure due to epistasis. For some landscapes, this structure can produce a computational constraint that prevents evolution from finding local fitness optima-thus overturning the traditional assumption that local fitness peaks can always be reached quickly if no other evolutionary forces challenge natural selection. Here, I introduce a distinction between easy landscapes of traditional theory where local fitness peaks can be found in a moderate number of steps, and hard landscapes where finding local optima requires an infeasible amount of time. Hard examples exist even among landscapes with no reciprocal sign epistasis; on these semismooth fitness landscapes, strong selection weak mutation dynamics cannot find the unique peak in polynomial time. More generally, on hard rugged fitness landscapes that include reciprocal sign epistasis, no evolutionary dynamics-even ones that do not follow adaptive paths-can find a local fitness optimum quickly. Moreover, on hard landscapes, the fitness advantage of nearby mutants cannot drop off exponentially fast but has to follow a power-law that long-term evolution experiments have associated with unbounded growth in fitness. Thus, the constraint of computational complexity enables open-ended evolution on finite landscapes. Knowing this constraint allows us to use the tools of theoretical computer science and combinatorial optimization to characterize the fitness landscapes that we expect to see in nature. I present candidates for hard landscapes at scales from single genes, to microbes, to complex organisms with costly learning (Baldwin effect) or maintained cooperation (Hankshaw effect). Just how ubiquitous hard landscapes (and the corresponding ultimate constraint on evolution) are in nature becomes an open empirical question.

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.