EFTA00811287.pdf

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.7I wiwynalurecornkommsbto 1 EFTA00811287 ARTICLE COMMUNICATIONS BIOLOGY I DOI: 10.1038/s42003.018-0078.7 I n the evolutionary process, mutation generates new variants, the Looping Star, which has fixation probability 1 — lir2 in the while selection chooses between mutants that have different limit of large N both for mutants that arise during reproduction reproductive rates. Any new mutant is initially present at very and for mutants that arise spontaneously. The Looping Star is the low frequency and can easily be eliminated by random drift. The only known amplifier for both uniform and temperature initi- probability that the lineage of a new mutant eventually takes over alization27, but it is not an arbitrarily strong amplifier. In fact, no the entire population is called the fixation probability. It is a key strong amplifier for temperature initialization had been known. quantity of evolutionary dynamics and characterizes the rate of In this work we resolve several open questions regarding strong evolutiots. amplification under uniform and temperature initialization. First, Consider a population, in which at each time step an individual we show that there exists a vast variety of graphs with self-loops is chosen for reproduction with probability proportional to fit- and weighted edges that are arbitrarily strong amplifiers for both ness, and the offspring replaces another individual'. In a well- uniform and temperature initialization. Moreover, many of those mixed population, each offspring is equally likely to replace any strong amplifiers are structurally simple, therefore they might be individual. If the new mutant has relative fitness r, then its fixa- realizable in natural or laboratory setting. Second, we show that tion probability is (1 — 1/r)/(1 — 1/rw), where N is the popu- both self-loops and weighted edges are key features of strong lation sizes. For advantageous mutants, which have r>l, the amplification. Namely, we show that without either self-loops or fixation probability converges to 1 — lir in the limit of large weighted edges, no graph is a strong amplifier under temperature population size. initialization, and no simple graph is a strong amplifier under Population structure can affect evolutionary and ecological uniform initialization. dynamics7-16. In evolutionary graph theory, the structure of a population is described by a graph17-24: each individual occupies Results a vertex; the edges mark the neighboring sites where a reprodu- Results overview. Our contribution comes in two parts. First, we cing individual can place an offspring. The edge weights represent give an explicit construction of a wide range of strong amplifiers. the proportional preference to make such a choice. If each Second, we identify features of population structures that are neighbor is chosen uniformly at random, then the outgoing edges necessary for amplification. See Fig. 1 for the illustration of the of every vertex have identical weights. 'This is modeled by an model and Supplementary Table 1 for the summary of our results. 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, Construction of strong amplifiers. We prove that almost all complete graph with self-loops. families of connected graphs with self-loops can be turned into In general, the fixation probability depends not only on the arbitrarily strong amplifiers of natural selection by assigning graph, but also on the initial placement of the invading suitable edge weights. The resulting structures are arbitrarily mutants2e,, 27. The two most natural cases are the following. First, strong amplifiers for both types of mutants: those that arise mutation is independent of reproduction and occurs at all loca- during reproduction and those that arise spontaneously, or any tions at a constant rate per unit time. 'Thus, mutants arise with combination of the two. Our result proves not only the existence equal probability in each location. This is called unifonn initi- of those structures, but provides an explicit procedure for their alization. Second, mutation happens during reproduction. In this construction. Note that by assigning small (or even zero) weight case, mutants are more likely to occur in locations that have a to an edge, we can effectively erase it. Hence, our construction is higher turnover. This is called temperature initialization. Our particularly interesting for sparse graphs. approach also allows us to study any combination of the two The construction first specifies certain subset of vertices that we cases: some mutants arise spontaneously while others occur call a "hub". The remaining vertices are split by the hub into a during reproduction. number of short "branches". The construction guarantees that the For a wide class of population structures", which include combined population size of all the branches is much larger than symmetric ones28, the fixation probability is the same as for the that of the hub. Therefore, with high probability, the first mutant well-mixed population. A population structure is an amplifier if it arises on a branch. exaggerates the fitness difference between the invading mutant The weights of all edges are then defined so that each of the and the resident when compared to the well-mixed following steps happens with high probability (Fig. 2). First, the population"- 27. 29. A population structure is an arbitrarily mutants spread on the branch until they reach a vertex that is strong amplifier (for brevity hereafter also called "strong ampli- connected to the hub. Second, the mutants repeatedly invade the fier") if it ensures a fixation probability arbitrarily dose to one for hub and eventually fixate there. Third, one by one the mutants any advantageous mutant, r> 1. Strong amplifiers can only exist spread from the hub to all branches and fixate. in the limit of large population size. Intuitively, the weight assignment creates a sense of global flow Numerical studies3° suggest that for spontaneously arising in the branches, directed toward the hub. This guarantees that the mutants and small population size, many unweighted graphs first two steps happen with high probability. For the third step, we amplify for some values of r. But for a large population size, show that once the mutants fixate in the hub, they are extremely randomly constructed, unweighted graphs do not amplifym. likely to resist all resident invasion attempts and instead they will Moreover, proven amplifiers for all values of r are rare. For invade and take over the branches one by one thereby fixating on spontaneously arising mutants (uniform initialization): (i) the the whole graph. For more detailed description, see "Methods" Star has fixation probability of -1 - 1/r2 in the limit of large N, section "Construction of strong amplifiers". and is thus an amplifier17. 32' 33; (ii) the Superstar (introduced in ref. 17, see also ref. 31 and the Incubator (introduced in refs. Simulation results. Note that simple structures such as Stars, 35. 36), which are graphs with unbounded degree, are strong Grids, or Sunflowers can be turned into arbitrarily strong amplifiers. The mathematical proofs of these assertions are amplifiers using our construction (Fig. 3). The explicit weight intricate37. construction is described in Supplementary Figure 1. In Fig. 3, we For mutants that arise during reproduction (temperature show the results of numerical experiments on the fixation prob- initialization), neither the Star nor the Superstar amplify27. The abilities of advantageous mutants, comparing the weighted Star can be modified with self-loops and edge weights to obtain 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 Fixation 0 • • • 0.0 ••• 0 0 • • d f e Fig.1Evolutionary 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 • • • • Weighted Unweighted — (-1.05 — rx1.1 — r-1.2 a 1.0 ...................... ........... ................ z. 0.8 .'s ..... 0.6 € 0.4 . _.." II! 0.2 0.0 a 100 200 300 400 500 Population size, N b 1.0 • • . . • • • • • • • • • • • • u- 0.2 ••.. • • . • 0.0 • 20 40 60 80 100 Population size. N C 1.0 • 0.8 <ti •0 0.6 g 0.4 LL 0.2 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. In Fig. 3b, we consider n x n and n x (n+ I) Grid graphs of We vary the population size and the fitness advantages for the sizes N = 9,12,16,20, ... .100. In order to avoid boundary, mutant. For each such case, we simulate the evolutionary conditions, the grid "wraps around" that is the vertices in the first dynamics many times to obtain an accurate value for the average row are connected to the vertices in the last row and the same fixation probability. We observe that although the unweighted holds for columns. The unweighted Grid with N vertices is structures have small (or no) amplification properties, our con- isothermal so the fixation probability under both uniform and struction turns them into strong amplifiers, where advantageous temperature initialization is given by (1 — 1/r)/(1 — 1/rw). mutants fixate with high probability. In Fig. 3c, we consider Sunflower graphs. An n-centered Specifically, in Fig. 3a, we consider Star graphs SN with N = 10, Sunflower graph is a graph consisting of a well-mixed population 20...., 500. For the unweighted Star, there is an exact formula for of size n in the center and n surrounding petals, which are fixation probability under both uniform and temperature well-mixed population themselves. Each petal is connected with initialization32. The values for weighted Star were computed by all its vertices to a unique vertex from the center. Specifically, we numerically solving large systems of linear equations. 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 on every graph without self-loops (but possibly with weighted N = 6,9, 12, 16, ... , 182. edges), the fixation probability is at most 1 — 1/(c + cr2). Recall that strong amplifiers can only exist in the limit of large Similarly, on every graph without weighted edges (but possibly population size. The above simulations illustrate that our weight with self-loops), the fixation probability is at most 1 — 1/(1 + rc). assignment substantially increases the fixation probability even It follows that with either of the two restrictions, there exist no for graphs with small population size. An illustration of a wide strong amplifiers under uniform initialization. variety of strong amplifiers for different topologies is presented in Fig. 4. Discussion Prior to our finding, strong amplifiers of natural selection have Necessary conditions for amplification. Our main result shows been elusive. Only very few examples of strong amplifiers have that a large variety of population structures can provide strong been described for spontaneously arising mutants. No strong amplification. A natural follow-up question concerns the features amplifiers have been known for mutants that arise during of population structures under which amplification can emerge. reproduction. But here we show that many population structures We complement our main result by proving that both weights can be turned into arbitrarily strong amplifiers, for both types of and self-loops are essential for strong amplification. Thus, we mutants, by choosing suitable edge weights. Consequently, there establish a strong dichotomy. Without either weights or self- exists an unlimited variety of population structures that are loops, no graph can be a strong amplifier under temperature strong amplifiers of natural selection (Fig. 4). We present an initialization, and no simple graph can be a strong amplifier algorithm for their construction. We note that our structures can under uniform initialization. On the other hand, if we allow both be remarkably simple. weights and self-loops, strong amplification is ubiquitous. It is now conceivable that amplifiers of natural selection could Under temperature initialization, we prove that on every graph be built in the lab. Modem microfluidics technology is capable of without self-loops (but possibly with weighted edges), the fixation building population structures (or, so called "metapopulations"", probability is at most 1 — 1/(r 1). Similarly, on every graph which control the topology of interactions and migration38-1 . without weighted edges (but possibly with self-loops), the fixation These metapopulations are typically arranged in microscale pat- probability is at most 1 — 1/(4r+2). Hence, if the population ches of habitat, and migration flows between neighboring patches structure lacks either self-loops or weights, strong amplification are created asymmetrically, using one-way barriers such us fun- under temperature initialization is impossible. nels41. Most realized topologies are simple, e.g., forming two- Under uniform initialization, we prove two analogous results dimensional grids. Our work is the first to show that even such for families of graphs that have bounded degree. Here, a family simple structures can lead to strong amplification by controlling {GI, G2. } of graphs has bounded degree if there exists a the migration rates between patches. constant c such that every vertex of every graph in the family has Amplifiers of natural selection could become important tools at most c adjacent edges. An example of bounded degree graphs for in vitro evolution42-15, because they can greatly boost the are Grid graphs: every vertex in a rectangular Grid of any size has ability to find advantageous mutants. Amplifiers could aid the degree at most 4 (or 8 for Moore neighborhood). We prove that discovery of optimized protein or nucleotide sequences for any COMMUNICATIONS BIOLOGY I (2018)1:71100110.1038/x42003.016.0078.71www.nathrecetry,cominsbe 5 EFTA00811291 ARTICLE COMMUNICATIONS BIOLOGY I DOI: 10.1038/s42003.018-0078.7 a 8_8_8 0.8 0.8 1.5 Weights: 02 1 20% 50% Edge usage per generation: — 10% 40% C Stage 1 Stage 2 Stage 3 hub hub hub branch \\\\\V O—re b in Drano4 OAP -* tick \ 4 -> hub reached -I Ration in the hub 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- vertices, in which case the structure is modeled by an unweighted multigraph. The sitive diagnostic tool for screening populations of replicating cells degree of a vertex is the number of edges adjacent to it. Individuals are of two types: residents with fitness I and (advantageous) or viruses for the presence of faster growing (pathological) var- mutants with fitness r>I. The fitness of individual occupying vertex i Is denoted by iants. Amplifiers should be especially useful in situations where the rate-limiting step is the discovery and evaluation of margin- The population evolves according to birth-death updating. In each step. one ally advantageous mutants. individual is chosen for reproduction randomly and proportionally to its fitness. Some naturally occurring population structures could be 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 amplifiers of natural selection. For example, the germinal centers copy along the selected edge to replace the individual at the other end of the edge of the immune system might constitute amplifiers for the affinity (death). That is, Individual 7 is selected for reproduction with probability fl E,f, maturation process of adaptive immunity4°. Habitats of animals and its adjacent edge (7. I') ls then selected with probability wg/ E, leg. The that are divided into multiple islands with a central breeding 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 location could potentially also act as amplifiers of selection. Our be used more frequently in direction "from i to e" than in direction 'from i' to C. theory helps to identify those structures in natural settings. The state of the process is given by vector (sr ay ....4.), where ; =1 Our study also establishes structural features that are necessary represents that the individual occupying vertex i Is a mutant and x, = 0 for a for amplification. For example, under temperature initialization. resident. The process starts with a single mutant on one vertex and stops either when all the individuals become mutants (fixation) or residents (extinction) amplification cannot arise from the topology alone, but crucially (Fig. la). depends on the migration rates between neighboring sites. Similarly, any search for natural amplifiers must focus on struc- Initialization scheme. In the beginning, the position of the single mutant can be tures where the effect of self-loops is present, meaning that the chosen either uniformly at random (uniform initialization. L) or proportionally to offspring of reproducing individuals occasionally remains local the temperature of the vertex (temperature initialization. 7). The temperature h, of and does not migrate to neighboring locations. vertex h is defined as Most of the research in the field, including the current work. ea - EZ^ w 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 and corresponds to how frequently each vertex is being replaced by reproduction death-birth updating. events happening in the neighboring vertices. Methods Amplifiers. The probability of fixation for a single mutant with relative fitness Here we describe the bask model and outline the mathematical methods. Further appearing on graph G according to initialization scheme U (or 7) is denoted by details are given in Supplementary Note 1. p(G. r. U) (or p(G.e. 7)). Denoting by Kg the complete graph on N vertices, we have Model. Population structure Is captured by a graph G with N vertices and directed I — edges that are possibly weighted and include self-loops. The vertices represent p(K.r. U) = p(Kr. (2) 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 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 the mutant is replaced by one of its resident neighbors before it reproduces even scheme. once equals p, = rat(r, + r). where t is the temperature of vertex s. Therefore. the The most well-known unif-amplifiers are Star graphs SN (see Fig. Id) for which fixation probability starting from a state with single mutant at vertex i is at most p(SN. r. U) — 1 — 1/,>1 — 1/r as N — oc. However. Star graphs are not temp- 1 - L/(t, + r). Taking all possible starting positions into account. we establish an amplifiers, since p(Sm. O. upper bound 1 - 1/(r + I) on the fixation probability using Cauchy-Schwarz We are interested in the behavior for large population sizes. A sequence of inequality. This implies that without self-loops. strong amplification under graphs G,. G„ ... of increasing size is called a strong unif-amplifier if, in the limit. temperature initialisation is not possible. the fixation probability under uniform Initialization tends to I for arbitrary. fixed In order to prove that weighted edges are also necessary, we consider an r> I (that is. if for any r> 1, we have lima..., r. U) — I). Strong temp- unweighted graph (possibly with self-loops). We argue similarly and establish an amplifiers are defined analogously. requiring that lira,—: p(G,r.T) — 1. 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 Fundamental questions. Despite the rich interest in amplifiers of natural selection. uniform initialization on graphs with bounded degree. As above. we first consider a many basic questions have remained unanswered. The fundamental open questions graph without self-loops (possibly with weighted edges). Given any such graph G. are the following. we single out a subset 0 of vertices with high temperature that we call hot vertices. First. are there strong amplifiers for temperature initialization? More generally. Formally. V' consists of vertices that are replaced by at least one of their neighbors are there population structures that function as strong amplifiers for both uniform with rate at least lie. where e is the constant that bounds the degtee. We prove that and temperature initialization? the subset V" is large (namely. 'VI > N/c) and that the fixation probability Second. similarly to the Star. does three exist a graph without self-loops and/or starting from a single hot vertex is small (namely. smaller than re/(1 + re)). without weights that is an amplifier for temperature initialization. achieving Accounting of all hot vertices, we establish that p(G.r. < 1 — 1/(e + er2). The fixation probability at least 1 — I& for large N? case of unweighted graphs (that possibly have self-loops) follows similarly. by Third. are there simple structures, such as graphs with bounded degree. that are noticing that under bounded degree. all vertices are sufficiently hot. The bound we strong amplifiers for uniform initialization? 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. Construction of strong amplifiers. In our positive result. we answer the first and the references therein. 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 Data and code ayaBablity. The data sets generated and analyzed dating the and strong temp-amplifier) by allowing self-loops and assigning weights to edges. current study and the related computer code are available in the Figshareu Self-loops are natural. They indicate that the offspring can replace the parent°. repository. hoprfidoLorg/10.6084/m9.figshare.6323240.v1. 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 Received: 28 March 2018 Accepted: 25 May 2018 each branch connects to the hub. The partitioning has the property that the hub is Published online: 14 June 2018 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 References 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 I. Ewers, W. Mathematical Population Genetics 2: Theoretical Introduction. faster than the rest of the graph. The success of the construction then relies on the Interdisciplinary Applied Mathematics (Springer. New York, 2004). following two principles. 2. Kimura. M. Evolutionary rate at the molecular level Nature 217. 624-626 First. the weights create a sense of global flow. The weight assignment in the (1968). branches guarantees that every edge is used more frequently in the direction 3. Desai, M. M.. Fisher. D. S. & Murray. A. W. The speed of evolution and toward the hub than an the direction away from the hub. Moreover. by assigning maintenance of variation in asexual populations. Carr. Biol. 17, 385-394 suitable weights to the self-loops. we achieve that edges closer to the hub are used (2007). more frequently then edges further away from the hub. See Fig. 5a for a small 4. McCandlish. D. M.. Epstein. C. L & Plotkin. I. B. Formal properties of the numerical illustration. These two facts imply that a mutant arising in a branch will probability of fixation: identities, inequalities and approximations. Them. propagate toward the hub and repeatedly try to invade it. Poput Blot 99, 98-113 (2015). Second. there is an important asymmetry between mutants and residents on a 5. Nowak, M. A. Evolutionary Dynamics (Harvard University Press, Cambridge, cal-mixed population. For large population size N. the fixation probability of a MA. 2006). single mutant with fitness r >I Invading a well-mixed population of N residents 6. Moran, P. A. P. The Statistical Processes of Evolutionary Theory (Oxford tends to the positive constant 1 — Ur. On the other hand, the probability that a University Press, Oxford. 1962). single resident takes over a large well-axed population of advantageous mutants is 7. Stain, M. Fixation probabilities and fixation times in a subdivided —r 'v. Le., exponentially small in N. The weight assignment within the hub makes population. Evolution 35.477-488 (1981). the hub behave approximately like a well-mixed population. Therefore once the 8. Nowak, M. A. & May. R. M. Evolutionary games and spatial chaos. Nature mutants fixate in the hub, they are extremely likely to resist the upcoming invasion 359. 826429 (1992). attempts of the residents. 9. Durrett. It & Levi,.. S. A. Stochastic spatial models: a user's guide to ecological With these two principles in mind. we can informally argue as follows. Since the applications. Philos. Trans. R. Soc. Lond. Ser. B Blot Set 343.329-350 (1994). hub occupies only a small portion of the graph, the first mutant most likely appears 10. Whitlock, M. Fixation probability and time in subdivided populations. in some branch. We focus on that branch and the hub (see Fig. 5b) and prove that Genetics 779,767-779 (2003). due to the biased flow toward the hub. the mutants spread all the way to the hub II. /butte C. & Doeba. M. Spatial structure often inhibits the evolution of (see Fig. 5c. Stage 1). Once in the hub, the mutants have a constant chance to fixate cooperation In the snowdrift game. Nature 428,643-646 (2000. there. If the first invading mutant lineage falls in the hub, another such lineage will 12. Komarova, N. L Spatial stochastic models for cancer initiation and be generated from the branch. Eventually. the mutants take over the hub (see progression. Bull. Math. Biol. 68. 1573-1599 (2006). Fig. 5c. Stage 2). From that point on, it is extremely unlikely that the residents 13. Pere. M. & SzolnokL A. Social diversity and promotion of cooperation in the could win the hub back In order to fixate on the branch. the mutants have to spatial prisoner's dilemma game. Phys. Rev. E 77, 011904 (2008). proceed against the natural direction of the flow. which is. in absolute terns. fairly 14. Houchmandzadeh. B. & Manacle. M. The fixation probability of a beneficial improbable. However, the alternative of residents taking over the hub is much mutation in a geographically structured population. New Phys. 13.073020 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. (2011). 15. Frean. M.. Rainey. P. B. & Traulsen, A. The effect of population structure on Foe details, see Supplementary Note I. Section 5, and the references therein. 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 Necessary conditions for ampilkatkm. In our negative results. we answer the crossing of fitness valleys by asexual populations. I. R. Soc. Interface 11. second and the third fundamental question by proving that both self-loops and 20140014 (2014). weighted edges are essential for existence of strong amplifiers. 17. Lieberman, E. Hawn. C & Nowak. M. A. Evolutionary dynamics on graphs. First. in order to address the second fundamental question, we consider Nature 433,312-316 (2005). temperature initialization on an arbitrary graph. 18. Broom. M. & Rychtlt.1. An analysis of the fixation probability of a mutant on In order to prove that self-loops are necessary features for strong amplification. special classes of non-directed graphs. Proc. k Soc. A Math. Phys. Eng. Sci. we consider a graph without self-loops (possibly with weighted edges). Them given 464. 2609-2627 (2008). any possible starting position i of the mutant. we find that the probability. p,. that 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 44. D.J. L. Vonelen. D., Korolev, K. S. & Gore, p. Generk indicators for loss of game. Europks Len 92. 38003 (2010). resilience before a tipping point leading to population collapse. Science 336• 20. Broom. M.. Ryan/. J. & Stadler. B. Evolutionary dynamics on graphs -- the 1175-1177 (2012). effect of graph structure and initial placement on mutant spread. J. Stat. 45. Lang. G. 1. et al. Pervasive genetic hitchhiking an