COMMUNICATIONS

COMMUNICATIONS BIOLOGY ARTICLE DOI: 10.1038/s42003.018-0078.7 OPEN Construction of arbitrarily strong amplifiers of natural selection using evolutionary graph theory Andreas Pavlogiannisl, Josef Tkadlecl, Krishnendu Chatterjeel & Martin A. Nowaku 2 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. 1IST Austria, A-3400 Klosterneuburg. Austria. 2 Program for Evolutionary Dynamics. Department of Organismic and Evolutionary Biology, Department of Mathematics, Harvard University, Cambridge, MA 02138, USA. These authors contributed equally: Andreas Pavlogiannis, Josef Tkadlec. Correspondence and requests for materials should be addressed to M.A.N. (email: martin_noviak@han•ard.edu) COMMUNICAIIONS BIOLOGY I (2018)1:71100110.1038/542003.016.0078.7 I wiwynalurecornkommsbto 1 EFTA00811287 ARTICLE COMMUNICATIONS BIOLOGY I DOI: 10.1038/s42003.018-0078.7 I n the evolutionary process, mutation generates new variants, while selection chooses between mutants that have different reproductive rates. Any new mutant is initially present at very low frequency and can easily be eliminated by random drift. The probability that the lineage of a new mutant eventually takes over the entire population is called the fixation probability. It is a key quantity of evolutionary dynamics and characterizes the rate of evolutiots. Consider a population, in which at each time step an individual is chosen for reproduction with probability proportional to fit- ness, and the offspring replaces another individual'. In a well- mixed population, each offspring is equally likely to replace any individual. If the new mutant has relative fitness r, then its fixa- tion probability is (1 — 1 /r)/(1 — 1/rw), where N is the popu- lation sizes. For advantageous mutants, which have r>l, the fixation probability converges to 1 — lir in the limit of large population size. Population structure can affect evolutionary and ecological dynamics7-16. In evolutionary graph theory, the structure of a population is described by a graph17-24: each individual occupies a vertex; the edges mark the neighboring sites where a reprodu- cing individual can place an offspring. The edge weights represent the proportional preference to make such a choice. If each neighbor is chosen uniformly at random, then the outgoing edges of every vertex have identical weights. 'This is modeled by an unweighted graph. A self-loop represents the possibility that an offspring does not migrate but instead replaces its parent35. The classical well-mixed population is described by an unweighted, complete graph with self-loops. In general, the fixation probability depends not only on the graph, but also on the initial placement of the invading mutants2e,, 27. The two most natural cases are the following. First, mutation is independent of reproduction and occurs at all loca- tions at a constant rate per unit time. 'Thus, mutants arise with equal probability in each location. This is called unifonn initi- alization. Second, mutation happens during reproduction. In this case, mutants are more likely to occur in locations that have a higher turnover. This is called temperature initialization. Our approach also allows us to study any combination of the two cases: some mutants arise spontaneously while others occur during reproduction. For a wide class of population structures", which include symmetric ones28, the fixation probability is the same as for the well-mixed population. A population structure is an amplifier if it exaggerates the fitness difference between the invading mutant and the resident when compared to the well-mixed population"- 27. 29. A population structure is an arbitrarily strong amplifier (for brevity hereafter also called "strong ampli- fier") if it ensures a fixation probability arbitrarily dose to one for any advantageous mutant, r> 1. Strong amplifiers can only exist in the limit of large population size. Numerical studies3° suggest that for spontaneously arising mutants and small population size, many unweighted graphs amplify for some values of r. But for a large population size, randomly constructed, unweighted graphs do not amplifym. Moreover, proven amplifiers for all values of r are rare. For spontaneously arising mutants (uniform initialization): (i) the Star has fixation probability of -1 - 1/r2 in the limit of large N, and is thus an amplifier17. 32' 33; (ii) the Superstar (introduced in ref. 17, see also ref. 31 and the Incubator (introduced in refs. 35. 36), which are graphs with unbounded degree, are strong amplifiers. The mathematical proofs of these assertions are intricate37. For mutants that arise during reproduction (temperature initialization), neither the Star nor the Superstar amplify27. The Star can be modified with self-loops and edge weights to obtain the Looping Star, which has fixation probability 1 — lir2 in the limit of large N both for mutants that arise during reproduction and for mutants that arise spontaneously. The Looping Star is the only known amplifier for both uniform and temperature initi- alization27, but it is not an arbitrarily strong amplifier. In fact, no strong amplifier for temperature initialization had been known. In this work we resolve several open questions regarding strong amplification under uniform and temperature initialization. First, we show that there exists a vast variety of graphs with self-loops and weighted edges that are arbitrarily strong amplifiers for both uniform and temperature initialization. Moreover, many of those strong amplifiers are structurally simple, therefore they might be realizable in natural or laboratory setting. Second, we show that both self-loops and weighted edges are key features of strong amplification. Namely, we show that without either self-loops or weighted edges, no graph is a strong amplifier under temperature initialization, and no simple graph is a strong amplifier under uniform initialization. Results Results overview. Our contribution comes in two parts. First, we give an explicit construction of a wide range of strong amplifiers. Second, we identify features of population structures that are necessary for amplification. See Fig. 1 for the illustration of the model and Supplementary Table 1 for the summary of our results. Construction of strong amplifiers. We prove that almost all families of connected graphs with self-loops can be turned into arbitrarily strong amplifiers of natural selection by assigning suitable edge weights. The resulting structures are arbitrarily strong amplifiers for both types of mutants: those that arise during reproduction and those that arise spontaneously, or any combination of the two. Our result proves not only the existence of those structures, but provides an explicit procedure for their construction. Note that by assigning small (or even zero) weight to an edge, we can effectively erase it. Hence, our construction is particularly interesting for sparse graphs. The construction first specifies certain subset of vertices that we call a "hub". The remaining vertices are split by the hub into a number of short "branches". The construction guarantees that the combined population size of all the branches is much larger than that of the hub. Therefore, with high probability, the first mutant arises on a branch. The weights of all edges are then defined so that each of the following steps happens with high probability (Fig. 2). First, the mutants spread on the branch until they reach a vertex that is connected to the hub. Second, the mutants repeatedly invade the hub and eventually fixate there. Third, one by one the mutants spread from the hub to all branches and fixate. Intuitively, the weight assignment creates a sense of global flow in the branches, directed toward the hub. This guarantees that the first two steps happen with high probability. For the third step, we show that once the mutants fixate in the hub, they are extremely likely to resist all resident invasion attempts and instead they will invade and take over the branches one by one thereby fixating on the whole graph. For more detailed description, see "Methods" section "Construction of strong amplifiers". Simulation results. Note that simple structures such as Stars, Grids, or Sunflowers can be turned into arbitrarily strong amplifiers using our construction (Fig. 3). The explicit weight construction is described in Supplementary Figure 1. In Fig. 3, we show the results of numerical experiments on the fixation prob- abilities of advantageous mutants, comparing the weighted structures to their unweighted counterparts. The experiments 2 COMMUNICATIONS BIOLOGY I (2018)1:71IDOL 10.1038/s42003-018-0078-7I www.naturecom/comnabio EFTA00811288 COMMUNICATIONS BIOLOGY I DOI: 10.1038/s42003.018 0078.7 ARTICLE a Extinction A new mutant d e Fixation 0 • • • 0.0 ••• 0 0 • • f Fig.1 Evolutionary dynamics in structured populations. Residents (yellow) and mutants (purple) differ in their reproductive rate. a A single mutant appears. The lineage of the mutant becomes extinct or re ches fixation. The probability that the mutant takes over the population is called "fixation probability". b The classical, well-mixed population is described by a complete graph with self-loops. (Self-loops are not shown here.) (c) Isothermal structures do not change the fixation probability compared to the w Il-mixed population. d The Star is an amplifier for uniform initialization. e A self-loop means the offspring can replace the parent. Self-loops are a mathematical tool to assign different reproduction rates to different places. f The Superstar, which has unbounded degree in the limit of large population size, is a strong amplifier for uniform initialization. Its edges (shown as arrows) are directed which means that the connections are one-way Fig. 2 Steps to fixation in strong amplifiers. Residents are shown in yellow, mutants in purpl . a Our construction partitions a graph into a "hub" (orange) and a number of "branches" (blue) in such a way that the first mutant appears in one of the branches. The fixation of advantageous mutants is then reached in three stages. b The mutant lineage reaches the vertex of the branch adjacent to the hub. c, d Next, the mutants place offspring into the hub several times and eventually fixate there. In the worst case, the initial branch can become all residents again. e, f Finally, the mutants fixate in the branches one after the other and thereby occupy the whole population COMMUNICAtiONS BIOLOGY I (2018)1:71I DOI 10.1038/x42003.018.0078.71 www_nature_com/commsbco 3 EFTA00811289 ARTICLE COMMUNICATIONS BIOLOGY 1001: 10.1038/s42003.018'0078.7 a b C • • • • Weighted Unweighted — (-1.05 — rx1.1 — r-1.2 1.0 z. 0.8 0.6 € 0.4 II! 0.2 0.0 ........... ........... .'s . _.." ........... ................ ..... a 1.0 u- 0.2 0.0 1.0 • 0.8 <ti • 0.6 0 g 0.4 LL 0.2 100 200 300 400 500 Population size, N • • • . . • • • • • • • • • • • ••.. • • . • • 20 40 60 80 100 Population size. N 50 100 150 Population size, N Fig. 3 Almost any topology can be turned into a strong amplifier. We illustrate the construction using the topology of a Star (a), a Grid (b), and a Sunflower (c). The hub is shown in orange, the branches in blue. Thin edges are assigned negligibly small (or zero) weights. For each graph, we compare the fixation probability of the unweighted (lines) and the weighted version (dots) as function of the population size, N for uniform initialization (for temperature initialization, see Supplementary Figure 2). A Sunflower graph consists of a well-mixed population of size n in the center surrounded by n petals, which are local well-mixed populations. Each petal is connected to a unique vertex of the center. For details, see Supplementary Note 1, Section 6 simulate the evolutionary dynamics on each population structure. We vary the population size and the fitness advantages for the mutant. For each such case, we simulate the evolutionary dynamics many times to obtain an accurate value for the average fixation probability. We observe that although the unweighted structures have small (or no) amplification properties, our con- struction turns them into strong amplifiers, where advantageous mutants fixate with high probability. Specifically, in Fig. 3a, we consider Star graphs SN with N = 10, 20...., 500. For the unweighted Star, there is an exact formula for fixation probability under both uniform and temperature initialization32. The values for weighted Star were computed by numerically solving large systems of linear equations. In Fig. 3b, we consider n x n and n x (n+ I) Grid graphs of sizes N = 9,12,16,20, ... .100. In order to avoid boundary, conditions, the grid "wraps around" that is the vertices in the first row are connected to the vertices in the last row and the same holds for columns. The unweighted Grid with N vertices is isothermal so the fixation probability under both uniform and temperature initialization is given by (1 — 1/r)/(1 — 1/rw). In Fig. 3c, we consider Sunflower graphs. An n-centered Sunflower graph is a graph consisting of a well-mixed population of size n in the center and n surrounding petals, which are well-mixed population themselves. Each petal is connected with all its vertices to a unique vertex from the center. Specifically, we consider n- centered Sunflower graphs where all petals have the 4 COMMUNICATIONS BIOLOGY I (2018)1:711001: KI1038/542033-018-0078-7 wwwAatutecom/comrrabio EFTA00811290 COMMUNICATIONS BIOLOGY I DOI: 10.1038/542003.018.0078.7 ARTICLE d Fig. 4 Infinite variety of strong amplifiers. Many topologies can be turned into arbitrarily strong amplifiers (Wheel (a). Triangular grid (b), Concentric circles (c), and Tree (d)). Each graph is partitioned into hub (orange) and branches (blue). The weights can be then assigned to the edges so that we obtain arbitrarily strong amplifiers. Thick edges receive large weights, whereas thin edges receive small (or zero) weights same size (either n — 1 or n — 2). The total population size is N = 6,9, 12, 16, ... , 182. Recall that strong amplifiers can only exist in the limit of large population size. The above simulations illustrate that our weight assignment substantially increases the fixation probability even for graphs with small population size. An illustration of a wide variety of strong amplifiers for different topologies is presented in Fig. 4. Necessary conditions for amplification. Our main result shows that a large variety of population structures can provide strong amplification. A natural follow-up question concerns the features of population structures under which amplification can emerge. We complement our main result by proving that both weights and self-loops are essential for strong amplification. Thus, we establish a strong dichotomy. Without either weights or self- loops, no graph can be a strong amplifier under temperature initialization, and no simple graph can be a strong amplifier under uniform initialization. On the other hand, if we allow both weights and self-loops, strong amplification is ubiquitous. Under temperature initialization, we prove that on every graph without self-loops (but possibly with weighted edges), the fixation probability is at most 1 — 1/(r 1). Similarly, on every graph without weighted edges (but possibly with self-loops), the fixation probability is at most 1 — 1/(4r+2). Hence, if the population structure lacks either self-loops or weights, strong amplification under temperature initialization is impossible. Under uniform initialization, we prove two analogous results for families of graphs that have bounded degree. Here, a family {GI, G2. } of graphs has bounded degree if there exists a constant c such that every vertex of every graph in the family has at most c adjacent edges. An example of bounded degree graphs are Grid graphs: every vertex in a rectangular Grid of any size has degree at most 4 (or 8 for Moore neighborhood). We prove that on every graph without self-loops (but possibly with weighted edges), the fixation probability is at most 1 — 1/(c + cr2). Similarly, on every graph without weighted edges (but possibly with self-loops), the fixation probability is at most 1 — 1/(1 + rc). It follows that with either of the two restrictions, there exist no strong amplifiers under uniform initialization. Discussion Prior to our finding, strong amplifiers of natural selection have been elusive. Only very few examples of strong amplifiers have been described for spontaneously arising mutants. No strong amplifiers have been known for mutants that arise during reproduction. But here we show that many population structures can be turned into arbitrarily strong amplifiers, for both types of mutants, by choosing suitable edge weights. Consequently, there exists an unlimited variety of population structures that are strong amplifiers of natural selection (Fig. 4). We present an algorithm for their construction. We note that our structures can be remarkably simple. It is now conceivable that amplifiers of natural selection could be built in the lab. Modem microfluidics technology is capable of building population structures (or, so called "metapopulations"", which control the topology of interactions and migration38-1 . These metapopulations are typically arranged in microscale pat- ches of habitat, and migration flows between neighboring patches are created asymmetrically, using one-way barriers such us fun- nels41. Most realized topologies are simple, e.g., forming two- dimensional grids. Our work is the first to show that even such simple structures can lead to strong amplification by controlling the migration rates between patches. Amplifiers of natural selection could become important tools for in vitro evolution42-15, because they can greatly boost the ability to find advantageous mutants. Amplifiers could aid the discovery of optimized protein or nucleotide sequences for any COMMUNICATIONS BIOLOGY I (2018)1:71100110.1038/x42003.016.0078.71 www.nathrecetry,cominsbe 5 EFTA00811291 ARTICLE COMMUNICATIONS BIOLOGY I DOI: 10.1038/s42003.018-0078.7 a Weights: Edge usage per generation: — 10% 40% 8_8_8 0.8 0.8 1.5 02 1 20% 50% Stage 3 C Stage 1 branch O—re hub \\\\\V OAP -* tick \ -> hub reached Stage 2 hub b in -I Ration in the hub hub Drano4 4 an the branch S Details of steps to fixation. a Assigning different weights to edges and self-loops changes the frequency with which each edge is used in each direction. Thicker arrows indicate edges that are used more frequently. b Our weight assignment creates a global sense of flow in the branches, directed toward the hub. The hub itself is almost isothermal and evolves fast. c Three stages to fixation illustrated on a single branch and the connecting vertex in the hub. After fixating on the hub at the end of Stage 2 (hub becomes dark orange), mutants spread to all the branches and fixate on the whole graph medical or industrial purpose. They could also be a highly sen- sitive diagnostic tool for screening populations of replicating cells or viruses for the presence of faster growing (pathological) var- iants. Amplifiers should be especially useful in situations where the rate-limiting step is the discovery and evaluation of margin- ally advantageous mutants. Some naturally occurring population structures could be amplifiers of natural selection. For example, the germinal centers of the immune system might constitute amplifiers for the affinity maturation process of adaptive immunity4°. Habitats of animals that are divided into multiple islands with a central breeding location could potentially also act as amplifiers of selection. Our theory helps to identify those structures in natural settings. Our study also establishes structural features that are necessary for amplification. For example, under temperature initialization. amplification cannot arise from the topology alone, but crucially depends on the migration rates between neighboring sites. Similarly, any search for natural amplifiers must focus on struc- tures where the effect of self-loops is present, meaning that the offspring of reproducing individuals occasionally remains local and does not migrate to neighboring locations. Most of the research in the field, including the current work. has focused on the populations that evolve according to the standard birth-death updating. An interesting direction for future research is to study if similar results can be achieved for death-birth updating. Methods Here we describe the bask model and outline the mathematical methods. Further details are given in Supplementary Note 1. Model. Population structure Is captured by a graph G with N vertices and directed edges that are possibly weighted and include self-loops. The vertices represent individuals. the edges represent interactions (Fig. I). The weight of an edge between vertices i and j Ls denoted by ivy. and captures the rate at which vertex i interacts with). Alternatively. the rates can be captured by allowing multiple edges between vertices, in which case the structure is modeled by an unweighted multigraph. The degree of a vertex is the number of edges adjacent to it. Individuals are of two types: residents with fitness I and (advantageous) mutants with fitness r>I. The fitness of individual occupying vertex i Is denoted by The population evolves according to birth-death updating. In each step. one individual is chosen for reproduction randomly and proportionally to its fitness. and then one of the adjacent edges is chosen randomly and proportionally to the edge weight. The selected individual produces a copy of itself (birth) and sends this copy along the selected edge to replace the individual at the other end of the edge (death). That is, Individual 7 is selected for reproduction with probability fl E, f, and its adjacent edge (7. I') ls then selected with probability wg/ E, leg. The individual at vertex I then becomes the same type as individual at vertex i. Note that due to different degrees and weights. an edge between Individuals i and I' an be used more frequently in direction "from i to e" than in direction 'from i' to C. The state of the process is given by vector (sr ay ....4.), where ; =1 represents that the individual occupying vertex i Is a mutant and x, = 0 for a resident. The process starts with a single mutant on one vertex and stops either when all the individuals become mutants (fixation) or residents (extinction) (Fig. la). Initialization scheme. In the beginning, the position of the single mutant can be chosen either uniformly at random (uniform initialization. L) or proportionally to the temperature of the vertex (temperature initialization. 7). The temperature h, of vertex h is defined as ea - EZ^ w and corresponds to how frequently each vertex is being replaced by reproduction events happening in the neighboring vertices. Amplifiers. The probability of fixation for a single mutant with relative fitness appearing on graph G according to initialization scheme U (or 7) is denoted by p(G. r. U) (or p(G.e. 7)). Denoting by Kg the complete graph on N vertices, we have I — p(K. r. U) = p(Kr. (2) as N co. Graphs for which the fixation probability is greater than this for any 6 COMMUNICATIONS BIOLOGY I (2018)1:71lDOI: 10.1038/s42003-01B-0078-7 I xymnaturecorn/temrrabo EFTA00811292 COMMUNICATIONS BIOLOGY I DOI: 10.1038/x42003.018.0078.7 ARTICLE r> I are called unif-amplifiers or temp-amplifiers based on the initialization scheme. The most well-known unif-amplifiers are Star graphs SN (see Fig. Id) for which p(SN. r. U) — 1 — 1/,>1 — 1/r as N — oc. However. Star graphs are not temp- amplifiers, since p(Sm. O. We are interested in the behavior for large population sizes. A sequence of graphs G,. G„ ... of increasing size is called a strong unif-amplifier if, in the limit. the fixation probability under uniform Initialization tends to I for arbitrary. fixed r> I (that is. if for any r> 1, we have lima..., r. U) — I). Strong temp- amplifiers are defined analogously. requiring that lira,—: p(G,r.T) — 1. Fundamental questions. Despite the rich interest in amplifiers of natural selection. many basic questions have remained unanswered. The fundamental open questions are the following. First. are there strong amplifiers for temperature initialization? More generally. are there population structures that function as strong amplifiers for both uniform and temperature initialization? Second. similarly to the Star. does three exist a graph without self-loops and/or without weights that is an amplifier for temperature initialization. achieving fixation probability at least 1 — I& for large N? Third. are there simple structures, such as graphs with bounded degree. that are strong amplifiers for uniform initialization? Construction of strong amplifiers. In our positive result. we answer the first fundamental question by proving that almost every family of graphs of increasing population size can be turned into a strong amplifier (both strong unif-amplifier and strong temp-amplifier) by allowing self-loops and assigning weights to edges. Self-loops are natural. They indicate that the offspring can replace the parent °. The standard Moran process is given by a complete graph with self-loops. In the proof1°. we start by defining a subset of vertices called a hub and partitioning the remaining vertices into subsets called branches in such a way that each branch connects to the hub. The partitioning has the property that the hub is larger than each branch individually. but smaller than all of them combined. Such a partitioning is possible for all graphs that have diameter polynomially smaller than N(i.e.. the distance between every pair of nodes is at most N". where c >0 is fixed and independent of PI). Once we construct the partitioning with the required properties, we proceed by assigning weights in such a way that. intuitively. (I) in each branch. there is a sense of global flow directed toward the hub: and (h) the hub is isothermal and evolves faster than the rest of the graph. The success of the construction then relies on the following two principles. First. the weights create a sense of global flow. The weight assignment in the branches guarantees that every edge is used more frequently in the direction toward the hub than an the direction away from the hub. Moreover. by assigning suitable weights to the self-loops. we achieve that edges closer to the hub are used more frequently then edges further away from the hub. See Fig. 5a for a small numerical illustration. These two facts imply that a mutant arising in a branch will propagate toward the hub and repeatedly try to invade it. Second. there is an important asymmetry between mutants and residents on a cal-mixed population. For large population size N. the fixation probability of a single mutant with fitness r >I Invading a well-mixed population of N residents tends to the positive constant 1 — Ur. On the other hand, the probability that a single resident takes over a large well-axed population of advantageous mutants is —r 'v. Le., exponentially small in N. The weight assignment within the hub makes the hub behave approximately like a well-mixed population. Therefore once the mutants fixate in the hub, they are extremely likely to resist the upcoming invasion attempts of the residents. With these two principles in mind. we can informally argue as follows. Since the hub occupies only a small portion of the graph, the first mutant most likely appears in some branch. We focus on that branch and the hub (see Fig. 5b) and prove that due to the biased flow toward the hub. the mutants spread all the way to the hub (see Fig. 5c. Stage 1). Once in the hub, the mutants have a constant chance to fixate there. If the first invading mutant lineage falls in the hub, another such lineage will be generated from the branch. Eventually. the mutants take over the hub (see Fig. 5c. Stage 2). From that point on, it is extremely unlikely that the residents could win the hub back In order to fixate on the branch. the mutants have to proceed against the natural direction of the flow. which is. in absolute terns. fairly improbable. However, the alternative of residents taking over the hub is much more improbable. Thus. with high probability, the mutants will succeed in fixating on the branch (see Fig. Sc. Stage 3). Similarly. they fixate on all the other branches. Foe details, see Supplementary Note I. Section 5, and the references therein. Necessary conditions for ampilkatkm. In our negative results. we answer the second and the third fundamental question by proving that both self-loops and weighted edges are essential for existence of strong amplifiers. First. in order to address the second fundamental question, we consider temperature initialization on an arbitrary graph. In order to prove that self-loops are necessary features for strong amplification. we consider a graph without self-loops (possibly with weighted edges). Them given any possible starting position i of the mutant. we find that the probability. p,. that the mutant is replaced by one of its resident neighbors before it reproduces even once equals p, = rat(r, + r). where t is the temperature of vertex s. Therefore. the fixation probability starting from a state with single mutant at vertex i is at most 1 - L/(t, + r). Taking all possible starting positions into account. we establish an upper bound 1 - 1/(r + I) on the fixation probability using Cauchy-Schwarz inequality. This implies that without self-loops. strong amplification under temperature initialisation is not possible. In order to prove that weighted edges are also necessary, we consider an unweighted graph (possibly with self-loops). We argue similarly and establish an upper bound 1 - 1/(4r + 2) on the fixation probability. Thus. the second fundamental question is answered in negative. Second. in order to address the thud fundamental question. we consider uniform initialization on graphs with bounded degree. As above. we first consider a graph without self-loops (possibly with weighted edges). Given any such graph G. we single out a subset 0 of vertices with high temperature that we call hot vertices. Formally. V' consists of vertices that are replaced by at least one of their neighbors with rate at least lie. where e is the constant that bounds the degtee. We prove that the subset V" is large (namely. 'VI > N/c) and that the fixation probability starting from a single hot vertex is small (namely. smaller than re/(1 + re)). Accounting of all hot vertices, we establish that p(G. r. < 1 — 1/(e + er2). The case of unweighted graphs (that possibly have self-loops) follows similarly. by noticing that under bounded degree. all vertices are sufficiently hot. The bound we obtain is p(G. r U) < 1 — 1/(1 + rc). Altogether. this answers the third fundamental question in negative. For details. see Supplementary Note I. Section 4. and the references therein. Data and code ayaBablity. The data sets generated and analyzed dating the current study and the related computer code are available in the Figshareu repository. hoprfidoLorg/10.6084/m9.figshare.6323240.v1. Received: 28 March 2018 Accepted: 25 May 2018 Published online: 14 June 2018 References I. Ewers, W. Mathematical Population Genetics 2: Theoretical Introduction. Interdisciplinary Applied Mathematics (Springer. New York, 2004). 2. Kimura. M. Evolutionary rate at the molecular level Nature 217. 624-626 (1968). 3. Desai, M. M.. Fisher. D. S. & Murray. A. W. The speed of evolution and maintenance of variation in asexual populations. Carr. Biol. 17, 385-394 (2007). 4. McCandlish. D. M.. Epstein. C. L & Plotkin. I. B. Formal properties of the probability of fixation: identities, inequalities and approximations. Them. Poput Blot 99, 98-113 (2015). 5. Nowak, M. A. Evolutionary Dynamics (Harvard University Press, Cambridge, MA. 2006). 6. Moran, P. A. P. The Statistical Processes of Evolutionary Theory (Oxford University Press, Oxford. 1962). 7. Stain, M. Fixation probabilities and fixation times in a subdivided population. Evolution 35.477-488 (1981). 8. Nowak, M. A. & May. R. M. Evolutionary games and spatial chaos. Nature 359. 826429 (1992). 9. Durrett. It & Levi,.. S. A. Stochastic spatial models: a user's guide to ecological applications. Philos. Trans. R. Soc. Lond. Ser. B Blot Set 343.329-350 (1994). 10. Whitlock, M. Fixation probability and time in subdivided populations. Genetics 779,767-779 (2003). II. /butte C. & Doeba. M. Spatial structure often inhibits the evolution of cooperation In the snowdrift game. Nature 428,643-646 (2000. 12. Komarova, N. L Spatial stochastic models for cancer initiation and progression. Bull. Math. Biol. 68. 1573-1599 (2006). 13. Pere. M. & SzolnokL A. Social diversity and promotion of cooperation in the spatial prisoner's dilemma game. Phys. Rev. E 77, 011904 (2008). 14. Houchmandzadeh. B. & Manacle. M. The fixation probability of a beneficial mutation in a geographically structured population. New Phys. 13.073020 (2011). 15. Frean. M.. Rainey. P. B. & Traulsen, A. The effect of population structure on the rate of evolution. Proc. R. Soc. B Blot. Sc,. 280. 20130211 (2013). 16. Komarova, N. L. Shahtiyari, L. & Wodarz, D. Complex role of space in the crossing of fitness valleys by asexual populations. I. R. Soc. Interface 11. 20140014 (2014). 17. Lieberman, E. Hawn. C & Nowak. M. A. Evolutionary dynamics on graphs. Nature 433,312-316 (2005). 18. Broom. M. & Rychtlt.1. An analysis of the fixation probability of a mutant on special classes of non-directed graphs. Proc. k Soc. A Math. Phys. Eng. Sci. 464. 2609-2627 (2008). COMMUNICATIONS BIOLOGY I (2018)1:71100110.1038/142003.016.0078.7 I www.natureacturroamenstro 7 EFTA00811293 ARTICLE COMMUNICATIONS BIOLOGY I DOE 10.1038/x42003.018.0078.7 19. StokeIcL A. & Pesci M. Reward and cooperation in the spatial public goods game. Europks Len 92. 38003 (2010). 20. Broom. M.. Ryan/. J. & Stadler. B. Evolutionary dynamics on graphs -- the effect of graph structure and initial placement on mutant spread. J. Stat. Theory Pratt 5. 369-381 (2011). 21. Shakarian. P., Roos. P. & Johnson, A. A review of evolutionary graph theory with applications to game theory. Biosystems 107, 66-80 (2012). 22. Dibarre. F.. Haunt. C. & Doebeli. M. Social evolution in structured populations. Nat. Commun. 5. 3409 (2014). 23. Allen. B. et al. Evolutionary dynamics on any population structure. Nature 544. 227-230 (2017). 24. Pavlogiannis. A.. Tkadlec. L. Chatterjee. K. & Nowak. M. A. Amplification on undirected population structures: comets beat stars. Set. Rep. 7. 82 (2017). 25. Pattni. K.. Broom. M., Rychtit. 1. & Silvers• L I. Evolutionary graph theory revisited: when is an evolutionary process equivalent to the moran process? Proc. R. Soc. A Math. Phys. Eng. Set 471. 20150334 (2015). 26. Antal. T.. Redner. S. & Seed. V. Evolutionary dynamics on degree- heterogeneous graphs. Phys. Rev. Lett 96. 188104 (2006). 27. Adlam. B., Chatterjee. K. & Nowak. M. Amplifiers of selection. Proc. R. Sec. A Math. Phys. Eng. Sea. 471. 20150114 (2015). 28. Maruyama. T. A Markov process of gene frequency change in a geographically structured population. Genetics 76. 367-377 (1974). 29. Kaveh. IC. Komareva, N. L & ICohandel, M. The duality of spatial death-birth and birth-death processes and limitations of the isothermal theorem. k Sec. Open Sci. 2, 140465 (2015). 30. Hindersin. L & Traulsen. A. Most undirected random graphs are amplifiers of selection for birth-death dynamics. but suppressors of selection for death-birth dynamics. PloS Comput Biol. 11. e1004437 (2015). 31. Adlam. B. & Nowak, M. A. Universality of fixation probabilities in randomly structured populations Sea. Rep. 4. 6692 (2014). 32. Monk. T., Green, P. & Paulin. M. Martingales and fixation probabilities of evolutionary graphs. Prot. P. Soc. A Math. M. Eng. Set 470. 20130730 (2014). 33. Chalub, F. A. C. C. An asymptotic expression for the fixation probability of a mutant in star graphs. J. Then. Games 3. 217-223 (2016). 34. Jamieson-Lane. A. & Hauer- C. Fixation probabilities on superstars. revisited and revised. I. Theor. Biol. 382. 44-56 (2015). 35. Goldberg. L A. et al. Asymptotically optimal amplifies for the moran process. Preprint at httpdfarXiv:1611.04209 (2016). 36. Giakkoupis. G. Amplifiers and suppressors of selection for the moran process on undirected graphs. Preprint at httpdfarXiv:1611.01585 (2016). 37. Galanis, A.. (Abet A.. Goldberg. L A.. Lipinskas. ). & Richerby, D. Amplifiers for the moran process. I ACM 64.5 (2017). 38. Keymer. ). E. Galanda. P.. Muldoon. C. Park. S. & Austin. R. H. Bacterial metapopulations in nanefatiticated landscapes. Prot. Natl. Acad. Set USA 103. 17290-17295 (2006). 39. Ge/ajda. P.. Keymer. L. Chaikin, P. & Austin. It A wall of funnels concentrates swimming bacteria. I. Bacterial. 189. 8704-8707 (2007). 40. Mannik. L. Thiessen. It. Galeda. P.. Keymer. I. E. & Dekker• C. Bacterial growth and motility in sub-micron constrictions. Proc. Nati. Acad. Set USA 106. 14861-14866 (2009). 41. Ruston. It. Garen. M. & Stocker. It Nficrofluidics expanding the frontiers of microbial ecology. Anna. Rev. Biophys. 43. 65-91 (2014). PNIID: 24773019. 42. Mitchell. A. et aL Adaptive prediction of environmental changes by microorganisms. Nature 460. 220-224 (2009). 43. Berk*. I. E. et al. Genome evolution and adaptation in a long-term experiment with escherichia coli. Nature 461. 1243-1247 (2009). 44. D.J. L. Vonelen. D., Korolev, K. S. & Gore, p. Generk indicators for loss of resilience before a tipping point leading to population collapse. Science 336• 1175-1177 (2012). 45. Lang. G. 1. et al. Pervasive genetic hitchhiking and clonal interference in forty evolving yeast populations. Nature 500. 571-574 (2013). 46. Victors. G. D. & Nussenzweig, M. C Germinal centers. Anna. Rev. Iminunot 30. 429-457 (2012). 47. Pavlogiannis. A.. Tkadlec, L. Chatterjee. K. & Nowak. M. A. Strong amplifiers of natural selection: proofs. Preprint at httpdfarXiv:1802.02509 (2018). 48. Tkadlec. L. Data for Fig. 3 in Construction of arbitrarily strong amplifiers of natural selection using evolutionary graph theory. (2018). httpufidoLorgf 10.6084fm9.figshare.6323240.v1. Acknowledgements A.P.. I.T.. and K.C. acknowledge support from ERG Stan (grant no. 279307: Graph Games). Austrian Science Fund (EWE) grant nos. P23499.N23 and SI1407-N23 (RLSE). MAN. acknowledges support from Office of Naval Research grant N00014.16.1.2914 and from the John Templeton Foundation. The Program fin Evolutionary Dynamics is supported in part by a gift from B Wu and E. Larson. Author contributions A.P.. IT.. K.C.. and M.A.N. performed the research and wrote and reviewed the manuscript. Additional information Supplementary Information accompanies this paper at lutps://doi.org/I0.103&fs42003. 018.0378.7. Competing interests: The authors declare no competing interests. Reprints and permission information is available online at http://npg.nature.comf remmtsandper missions/ Publishees note:Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License. which permits use. sharing. adaptation. distribution and reproduction in any medium or format. as long as you give appropriate credit to the original author(s) and the source. provide a link to the Creative Commons license. and indicate if changes were made. The images or other third party material in this article are included in the ankles Creative Commons license. unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use. you will need to obtain permUsson directly from the copyright holder. To view a copy el this license. Vint hupdfcreativecommons.org/ licenseeby74.0f. e The Autism(%) 2018 COMMUNICATIONS BIOLOGY I (2018)1:71Pa 10.103&/x42003.018-0078-7l xviwnMurecorti/comnabio EFTA00811294