key: cord-0775398-hzu4c8ls authors: Martens, Erik A.; Hallatschek, Oskar title: Interfering Waves of Adaptation Promote Spatial Mixing date: 2011-11-03 journal: Genetics DOI: 10.1534/genetics.111.130112 sha: 3cdfc63c3790d0bc50c45fe33b2b7ca304641a5d doc_id: 775398 cord_uid: hzu4c8ls A fundamental problem of asexual adaptation is that beneficial substitutions are not efficiently accumulated in large populations: Beneficial mutations often go extinct because they compete with one another in going to fixation. It has been argued that such clonal interference may have led to the evolution of sex and recombination in well-mixed populations. Here, we study clonal interference, and mechanisms of its mitigation, in an evolutionary model of spatially structured populations with uniform selection pressure. Clonal interference is much more prevalent with spatial structure than without, due to the slow wave-like spread of beneficial mutations through space. We find that the adaptation speed of asexuals saturates when the linear habitat size exceeds a characteristic interference length, which becomes shorter with smaller migration and larger mutation rate. The limiting speed is proportional to μ(1/2) and μ(1/3) in linear and planar habitats, respectively, where the mutational supply μ is the product of mutation rate and local population density. This scaling and the existence of a speed limit should be amenable to experimental tests as they fall far below predicted adaptation speeds for well-mixed populations (that scale as the logarithm of population size). Finally, we show that not only recombination, but also long-range migration is a highly efficient mechanism of relaxing clonal competition in structured populations. Our conservative estimates of the interference length predict prevalent clonal interference in microbial colonies and biofilms, so clonal competition should be a strong driver of both genetic and spatial mixing in those contexts. O NE of the most basic questions of evolutionary biology that can be studied in controlled evolution experiments is: How fast do microbial populations adapt to new environments by the accumulation of beneficial mutations? Traditionally, it was thought that the accumulation process is limited by the supply of beneficial mutations (Novick and Szilard 1950; Atwood et al. 1951) . If a rare beneficial mutation arises and becomes sufficiently frequent, it will expand rapidly until it is present in all individuals of the population. After the completion of such a selective sweep, the population is stationary again until the next beneficial mutation arises. The accumulation rate of beneficial mutation should thus be controlled by the appearance of new beneficial mutations, which is proportional to the population size and the mutation rate (Sniegowski and Gerrish 2010) . This scenario of "periodic selection" crucially rests on the assumption that mutation rates are so small that beneficial mutations occur strictly sequentially. Evolution experiments of the last decade have shown, however, that beneficial mutation rates in microbes can be as large as 5 · 10 25 per genome per generation in the bacterium Escherichia coli with typical fitness effects in the range of a few percent Perfeito et al. 2007; Sniegowski and Gerrish 2010) . These high mutation rates have severely restricted the parameter range of periodic selection. Multiple selective sweeps, simultaneously in progress, are characteristic of a well-mixed microbial population containing .10 4 cells (see, e.g., estimates in Appendix D). In the past, most evolution experiments had effective population sizes exceeding this threshold, including the Lenski experiment, in which the bacterium E. coli was evolved for .50,000 generations to adapt to minimal medium (De Visser et al. 1999; Miralles et al. 1999 ; Barrick et al. 2009 ). Accordingly, these experiments did not reveal a linear relation between adaptation speed and population size, but instead a much weaker dependence indicative of a mechanism of "diminishing returns" (De Visser et al. 1999; Shaver et al. 2002) . The reason for this behavior is that multiple beneficial mutations arise on different genetic backgrounds simultaneously and compete with one another for sweeping through the population. As a consequence, only a small number of arising beneficial mutations can go to fixation, and most of them are lost in the competition between clones. It was first noted by Fisher (1930) and Muller (1932) that sex relaxes clonal competition and speeds up the process of adaptation as it allows beneficial mutations to be combined in a single genome even if they first appeared in different lineages. Today, this Fisher-Muller advantage of sex is one of the most important explanation for why most organisms engage in some form of genetic exchange. In recent years, extensive research efforts have been invested in modeling clonal interference (Rouzine et al. 2003; Park and Krug 2007; Hallatschek 2011) with the goal to quantitatively explain adaptation speeds and genetic diversities measured for well-mixed microbial populations (Gerrish and Lenski 1998; . Although theoretical models depend on largely unknown effect distributions of beneficial mutations, they all predict that key quantities of interest, including the speed of adaptation and the genetic diversity, depend only weakly (logarithmically) on population size and mutation rates. While these predictions shape our current view of adaptation in large asexual populations, they primarily apply to well-mixed test tube populations of microbes. Many naturally occurring microbial populations attach to surfaces in the form of biofilms exhibiting a pronounced spatial structure (Tolker-Nielsen and Molin 2000; Watnick and Kolter 2000) . Even in laboratories microbes are routinely grown on agar plates by which they acquire spatial structure. More complicated spatial structure is relevant to the evolution of viral populations such as influenza and severe acute respiratory syndrome (SARS), which spread in space via human transportation networks (Hufnagel et al. 2004; Eggo et al. 2011) . Moreover, there is increasing evidence that spatial structure is also important to the evolutionary processes involved in cancer progression (Greaves et al. 2006; Merlo et al. 2006; Salk et al. 2009 ). One might thus wonder whether clonal interference is relevant to spatially extended populations and, if so, whether its effect on adaptation differs from that in well-mixed populations. Although some simulation studies have considered the case of structured populations with one individual per deme (Gordo and Campos 2006; Gonçalves et al. 2007) , a crucial fact about spatially continuous populations has been ignored so far: Beneficial mutations spread in the form of waves, first described by Fisher (1937) and Kolmogorov et al. (1937) . Since these adaptation waves spread at a constant speed, mutant clones grow linearly with time and hence much slower than they would if they grew in well-mixed populations. The slowness of selective sweeps has the consequence that growing clones are much more likely to interfere than in well-mixed populations. The link between slow adaptive waves and the potential importance of clonal interference was in fact anticipated by Fisher (1937) in his seminal article on "The wave of advance of advantageous genes." Therein, he considers the concrete example of a mutation with selective advantage s = 1% spreading along a continuously occupied shoreline. He estimates that spreading over 100 miles might take 10,000-100,000 generations and concludes that ". . . at any one time, the number of such waves of selective advance, simultaneously in progress, must be large" (Fisher 1937, p. 367) . This suggests to consider a scenario of clonal interference characterized by many interfering adaptation waves, as illustrated in Figure 1B . In the following, we will use simulations and analytical arguments to answer the following key questions: What is the effect of interfering Fisher waves on the speed of adaptation and the genetic diversity in an asexual population? Are there simple mechanisms of mitigating clonal interference and thus accelerating adaptation? Are these effects relevant to microbial colonies and biofilms, and perhaps measurable in evolution experiments? Figure 1 Simulations of asexual adaptation in a spatially extended population with absorbing boundary conditions. Stars denote the spatial location (horizontal axis) and the instant of time (vertical axis) at which new beneficial mutations become established. These events give rise to new mutant subpopulations ("clones"), which expand by waves traveling at a constant mean speed. Two drastically different adaptation scenarios are shown: (A) Periodic selection. When beneficial mutations arise sufficiently rarely, mutations sweep strictly sequentially because the waiting time for a new beneficial mutation exceeds the "fixation" time needed for a mutation to spread through the entire population. (B) Clonal interference. When the waiting time for beneficial mutations is much smaller than the fixation time, different clones compete for fixation. As a consequence, beneficial mutations are wasted (gray) unless they happen to arrive on the winning clone. Simulations were carried out with parameters L = 100, s 0 = 0.25, and m = 10 25 in A and m = 10 24 in B; with exponentially distributed selective coefficients; and with deterministic adaptation waves. To investigate clonal interference in spatially extended populations, our model is set up to allow for an efficient simulation of many adaptation waves simultaneously in progress. The habitat is modeled by a lattice with periodic boundary conditions and is always fully populated. Each lattice site records the genetic identity of the locally dominating clone in a subpopulation. This approximate description of the gene pool of the whole population, which accelerates our simulations, is appropriate if subpopulations are strongly dominated by single clones; see Appendix A and Discussion for an explicit range of validity. We first consider a linear habitat, where the genetic state of the population is represented by a lattice of length L. Natural selection is implemented so that adaptation waves run across sites and shift the spatial extent of different clones: In each generation, the clone at site i is replaced by the neighboring clone at site j with a probability proportional to 1 + sgn(DW)c(|DW|), where c is the speed of a Fisher wave driven by a fitness difference DW = W j 2 W i , where the sign of DW defines the direction of the wave. In effect, the replacement rule generates adaptation waves traveling at an average velocity given by c = c(DW). The function c(DW) is chosen to represent the classical Fisher wave speed cðDWÞ ¼ 2 ffiffiffiffiffiffiffiffiffiffiffiffi mDW p (with migration rate m = 1 4 ), valid for large populations with negligible genetic drift (Fisher 1937; Kolmogorov et al. 1937) . Alternatively, we use the wave speed given by c $ 2rmDW for strong noise (Doering et al. 2003; Hallatschek and Korolev 2009) with rm = 1, where r represents the population density (see Appendix A for further details). To simulate planar habitats, we represent the population on a hexagonal lattice of size L · L. Natural selection is implemented such that the clone at site i is replaced by one of the neighboring clones j with a probability proportional to its fitness, W j (normalized by the fitness summed over all neighbors). This replacement rule generates adaptation waves traveling at an average velocity c ¼ 2 ffiffiffiffiffiffiffiffiffiffiffiffi mDW p with a migration rate of m = 1 4 , consistent with the classical Fisher-Kolmogorov wave theory (see also Appendix A). New beneficial mutations appear at a rate m per site (m thus represents the product of population density r and beneficial mutation rate per genome) and survive genetic drift with probability 2s (Maruyama 1974) , where s is the selective fitness advantage. When a mutation becomes established at position i, the fitness W i of the i-th clone is updated according to W i (t) = W i (t 2 1) Á (1 + s). Effects of epistasis are absent, and the habitat is homogeneous such that selective pressures are the same throughout the habitat. The selective fitness advantage s of a mutation is chosen to be either constant s 0 or drawn from a distribution with mean value s 0 . We choose either an exponential distribution or a hump-shaped gamma distribution with shape parameter k = 2, which are both frequently used in theoretical evolu-tion models (Eyre-Walker and Keightley 2007) . See inset in Figure 3 for the shape of these distributions. In our simulations of interfering Fisher waves, we vary the following parameters: the beneficial mutation rate m per site, the habitat size L, the relation between speed c of traveling waves and fitness differences (linear habitat only), and the mean selective fitness advantage s 0 . Starting from a population devoid of genetic variation, our model generates a population of genotypes that differ in the amount and type of beneficial mutations they carry. After a transient period, in which genetic diversity builds up, the mean fitness in the population increases at a steady pace by the fixation of beneficial mutations. We quantify the speed V of adaptation by the mean fitness increase per generation. Figure 2 shows the adaptation speed as a function of the habitat size L for various mutation rates and selection coefficients. For small habitat sizes, the adaptation speed is linear in the habitat size, which indicates that adaptation is limited by the occurrence of mutations: Doubling the habitat size, and thus the influx of beneficial mutations, doubles the adaptation speed. We thus recover the classical regime of periodic selection, in which beneficial mutations sweep strictly sequentially, as illustrated in Figure 1A . In this regime, the dynamics of individual sweeps are irrelevant, and the mean fitness increase per generation is given by 2NU b s 2 0 , just as in the corresponding well-mixed case. However, as the habitat size exceeds a characteristic length scale L c , we observe that the adaptation speed begins to saturate due to clonal interference. For very large systems, the adaptation speed approaches a limiting value V max . These results call for an explanation of the "interference" scale L c at which clonal interference sets in and of how the magnitude of the "speed limit" V max depends on the parameters, in particular mutation rates and Fisher wave speed. It turns out that-for constant fitness effects-relatively simple estimations can be given for both quantities. The condition for clonal interference, and hence the characteristic scale L c , can be determined by comparing two important timescales. The first timescale estimates how long it takes for a single adaptation wave to run across the length L of the habitat. This fixation time is given by t fix % L/c 0 , where the traveling speed c 0 depends on the selection coefficient s 0 . The second timescale is the waiting time t mut for a new beneficial mutation to become established, which is inversely proportional to both the establishment probability 2s and the rate m b L d at which beneficial mutations appear. The latter depends on the dimension d of the habitat (d = 1 and d = 2 for a linear and a planar habitat, respectively). We thus obtain the mutation waiting time t mut % (2s 0 L d m) 21 . Now, the mode of adaptation depends on the relative size of t fix and t mut : If the fixation time is smaller than the mutation waiting time (t mut , t fix ), we expect periodic selection. In the opposite case, we expect clonal competition. The crossover from periodic selection to clonal interference occurs just when t fix $ t mut , implying a characteristic "interference scale" of Next, we use this estimate to find an approximate expression for the adaptation speed limit V max observed in Figure 2 . To this end, it is convenient to express the adaptation speed in the following general form: The factor 2s 2 0 L d m on the right-hand side is the rate at which beneficial mutations accumulate in the absence of clonal interference. The function F represents the probability that a mutation reaches fixation once established. When mutations arise sequentially, each established mutation also reaches fixation; hence F $ 1 for small habitats, L > L c . On the other hand, for large habitats (L ? L c ) clones interfere and F becomes very small. How small? Given that the adaptation speed saturates at large system sizes, as inferred from our simulation results in Figure 2 , we must require that the habitat length L drops out of Equation 2 for large habitats. This can occur only if F(L/L c ) $ (L c /L) d for large L. Hence, we estimate the speed limit for large systems by It can be seen from Equation 2 that the scaled adaptation speed V/V 0 with V 0 = s 0 c 0 /L should be a unique function of the scaled mutation rate m/m 0 with m 0 = c 0 /(2s 0 L d+1 ). Therefore, if we plot our data sets for different parameters in one figure using axes V/V 0 and m/m 0 , they should all collapse on a single master curve. The resulting scaling plots for linear and planar habitats are shown in Figure 3 . Data corresponding to constant selection coefficients (Figure 3 , black line) do indeed collapse on a single master curve, even though we varied m, s 0 , and the type of adaptation wave (weak/strong genetic drift). Note also the transition from a linear regime to the sublinear regimes with power law exponents 1 2 and 1 3 in one and two dimensions, respectively. These exponents are consistent with our prediction in Equation 3. Moreover, Figure 3 displays results for simulations in which the fitness effects of new mutations were drawn from an exponential and a gamma distribution (with shape parameter k = 2), respectively. Note that although data for the different distributions follow our scaling predictions individually, they are slightly shifted with respect to each other. This indicates that the prefactors of the adaptation speed depend on the tails of the distribution. Broader distributions tend to yield larger adaptation speeds, apparently because they will more frequently give rise to the sampling of unusually large-s clones that outcompete average-s clones. As a consequence, fixations are more frequent and the adaptation speed is higher (see also Appendix F). The effect is stronger in the clonal interference than in the periodic selection regime. Both the existence of a speed limit V max for large habitats and its dependence on mutation rates contrast with the well-mixed case, where the adaptation speed depends logarithmically on both population size and mutation rates (see Discussion). To further characterize the clonal interference regime, we have measured fixation times and fitness correlations in linear habitats as a function of habitat size; see Appendixes B and C. We find that t fix $ L 3/2 for clonal interference and that the fitness variance scales linearly with the size of the habitat. Both observations suggest that our model shares some universal features with certain types of crystal growth models that have been extensively studied in physics (Kardar et al. 1986 ). We investigate two strategies of mitigating clonal interference and increasing adaptation speeds. The classical solution to clonal interference is recombination, which allows us to combine beneficial mutations arising on different genetic backgrounds. For well-mixed populations, it has been predicted that the adaptation speed increases with the Figure 2 The speed of adaptation in a linearly extended population. For small habitat sizes, the adaptation speed V (mean fitness increase per generation) grows linearly with the habitat size L, as expected for the periodic selection regime. As the habitat exceeds a characteristic size L c , the adaptation speed saturates at a limiting value V max . Both the crossover scale and the adaptation speed limit depend on the selection advantage s 0 of beneficial mutations and the mutation supply rate m. The simulations were run assuming a constant selection coefficient and deterministic adaptation waves. The same saturation behavior is observed when selection coefficients are distributed (exponential distribution and gamma distribution). Data represent the average over $2000 fixation events. recombination rate as V } r 2 for large populations where clones interfere (Neher et al. 2010 ). This result demonstrates that increasing recombination rates can strongly speed up evolution. The effectiveness of this strategy can be appreciated from Figure 4A , which displays the adaptation speed as a function of habitat size for various recombination rates. To generate these data, we have incorporated recombination in our simulations as follows. Recombinants are produced at a rate r per site from two (haploid) individuals randomly selected from the nearest neighborhood in the parent generation (selfing is allowed). Recombinant genotypes are formed from the parental genotypes by onepoint recombination: The parent chromosomes are paired and a point is randomly chosen by which both chromosomes are split. The mutations to both sides of the recombination point are then exchanged between the two chromosomes, forming the recombinant genotype (see Appendix A for further details). Next, we study spatial mixing as an alternative way of mitigating clonal interference. Spatial mixing is implemented so that any given clone competes at a small rate m l with a randomly chosen clone rather than with its immediate neighbor (see Appendix A for details of the implementation). The effect of these long-range jumps on the adaptation speed is shown in Figure 4B . Long-range migration has no effect on the periodic selection regime, because it does not change the limiting supply of beneficial mutations. In the clonal interference regime, however, adaptation speeds are continually increasing as a function of jump rate. The effect is large: Allowing for long-range jumps only every 1000 generations approximately yields a fivefold increased adaptation speed in the clonal interference regime. Scaling plots summarizing simulation data. The rescaled adaptation speed V/V 0 is shown as a function of the rescaled mutation rate m/m 0 (see text for the characteristic speed V 0 and mutation rate m 0 ). For the periodic selection regime (small m), we observe a linear relation between the adaptation and mutation rate; for clonal interference (large m), we find the power laws V $ m 1/2 in linear habitats (A) and V $ m 1/3 in planar habitats (B). Simulations were carried out for mean selection coefficients s 0 ¼ 0.025, 0.05, and 0.1 and mutation supply rates m ¼ 5 · 10 26 , 1.25 · 10 26 , and 3.125 · 10 27 . We also varied the type of adaptation wave (deterministic/noisy) and the distribution of fitness effects (black, constant selection coefficients; red, exponential distribution; blue, gamma distribution with shape parameter k ¼ 2). Note that data for each type of fitness distributions fall on a single master curve, consistent with our scaling argument. Genetic and spatial mixing speed up adaptation. (A) Effect of recombination on the adaptation speed in a linear habitat. Simulation runs are shown with various recombination rates (see inset). Note that the adaptation speed is positively correlated with recombination rate r in the regime of clonal interference, consistent with the Fisher-Muller hypothesis. Simulations were carried out with s ¼ const., s 0 ¼ 0.25, m ¼ 3.125 · 10 25 , and deterministic adaptation waves. (B) Adaptation speeds vs. habitat size for varying rates m l of long-range jumps. The adaptation speed in the periodic selection regime is unchanged, but even a small rate 0.001 of long-range jumps led to fivefold increased adaptation speeds in the clonal interference regime. Simulations were carried out for s ¼ const., s 0 ¼ 0.1, m ¼ 5 · 10 26 , and deterministic adaptation waves. Long-range migration seems to be an efficient way to mitigate clonal interference, which has significant consequences for evolution (see Discussion). The basic mechanism can be understood as follows: Long-range migration allows clones to replicate themselves at different locations, which enables them to effectively grow at a faster rate. In other words, a clone that has led to a second "seed" by means of long-range migration will grow twice as fast as a clone with only one seed. A third seed triples the growth rate, etc. In effect, when clonal interference is absent, one obtains exponential growth with the rate which depends on the selection coefficient through the wave velocity relation c 0 = c(s 0 ). A derivation for this rate is given in Appendix E. Note that the resulting exponential growth of mutants mirrors selective sweeps in well-mixed populations, however, with a quite different effective selection coefficient s e (see also Discussion). Importantly, the resulting fast Malthusian growth accelerates the fixation process of beneficial mutations. As a consequence, mutations that would interfere without long-range migration are now more likely to arise sequentially. Consistent with this view, Figure 4 shows that the linear regime of periodic selection is extended to a larger parameter range as the long-range migration rate is increased. Of course, for sufficiently large habitat sizes, clonal interference also occurs in the presence of long-range migration. However, the number of simultaneously competing clones is reduced due to the faster sweeps. This leads to generally larger adaptation rates than for clonal interference without long-range migration, as seen in Figure 4 . A crucial feature of adaptation in spatially extended populations is that advantageous mutations spread through the population by means of traveling waves (Fisher 1937; Kolmogorov et al. 1937 ). This wave-like motion implies that clones grow at a constant speed, in strong contrast to the accelerating logistic growth characteristic of well-mixed populations. We have established a model of adaptation by waves to investigate the rate at which beneficial mutations are accumulated in spatially extended populations. Our model represents the gene pool of local subpopulations by the locally dominating genotype. This representation is appropriate when clonal interference is absent within these subpopulations. This sets an upper bound to the beneficial . When the beneficial mutation rate is still larger, one obtains a hybrid scenario of clonal interference on a local well-mixed scale and clonal interference by adaptation waves (E. A. Martens and O. Hallatschek, unpublished results) . With the assumptions of a homogeneous habitat (constant selection pressure), short-range migration, and negligible epistasis, our model is a first step toward understanding clonal interfer-ence in spatially structured populations, such as microbial colonies or biofilms. We expect that similar phenomena to those reported here may be observed in other rapidly evolving populations. Many natural populations are, however, characterized by more complex migration patterns than the stepping-stone model used in our work, for instance, influenza or SARS (Hufnagel et al. 2004; Kaluza et al. 2010; Eggo et al. 2011) . For concrete predictions, the existing model needs to be extended to include these migration networks. There is also increasing evidence that spatial structure is relevant in evolutionary processes related to cancer progression (Salk et al. 2009 ), suggesting that similar modeling approaches may apply (Martens et al. 2011 ). In the following, we estimate under which conditions clonal interference might be observable in microbial colonies and discuss our key predictions and how they may be verified in microbial evolution experiments. Clonal interference generally occurs when fixation times are larger than the waiting time for new beneficial mutations to arise in the population. Since adaptation waves travel at a constant speed and thus advance much more slowly than Malthusian sweeps, fixation times are much larger in spatially extended than in well-mixed populations. As a consequence, the regime of clonal interference is inflated in structured populations compared to well-mixed ones. The condition for clonal interference is made explicit by comparing the typical fixation time of a single beneficial mutation with the waiting time for it to arise. We found that clonal interference occurs when the habitat size is larger than a characteristic size L c . The interference scale L c not only defines a crossover, but also measures the typical distance an adaptation wave travels freely before it collides with another wave that arose independently of the first one. The tug-of-war between adaptation waves and the role of the interference scale L c can be discerned from the simulation results in Figure 5 . Our simple quantitative expression in Equation 1 for the interference scale was found to increase with the speed of adaptation waves and decrease with the rate of beneficial mutations per site. A similar characteristic length appears in the context of soft sweeps, where m has to be interpreted as the establishment rate for a particular beneficial mutation (Ralph and Coop 2010) . For L . L c , multiple clones carrying the same mutation collide and subdivide the habitat into patches of size L c (see Figure 5A ). This situation is similar to our case of s = const. when m is interpreted as the occurrence rate of a particular adaptation; in our model, however, waves belonging to different adaptations keep interfering with each other until one clone has reached fixation in the habitat. To see whether clonal interference is relevant to microbial colonies, we estimate the order of magnitude of L c (for details see Appendix D). We assume fitness effects on the order of 1% and mutation rates in the range of 10 26 -10 24 per genome and generation. Given the large variance of the thickness of biofilms and microbial colonies, we consider a range of cell densities between 1 and 1000 per square cell diameter. This yields a mutation supply rate m that lies within the range of 10 26 and 10 21 per square cell diameter. For s = 1%, we estimate a deterministic Fisher wave speed c 0 in the range of 0.1-10 cell diameters per generation by assuming that microbes in dense colonies disperse between 1 and 100 cell diameters per generation. Thus, we estimate L c = (c 0 /(2s 0 m)) 1/3 to lie within 4 and 800 cell diameters. The characteristic interference length scale L c = (c 0 / (2s 0 m)) 1/2 for a linear habitat could be relevant for expanding microcolonies. For instance, it has been shown that the expansion of a colony is driven by a thin layer of pioneer cells (Hallatschek and Nelson 2010; Nadell et al. 2010 ). This pioneer population at the expanding front evolves in an effectively linear habitat. Applying similar estimates to the above to the context of an expanding microbial colony, we estimate an interference scale between 50 and 500 cell diameters. Importantly, the length scales both for planar and for linear habitats are much smaller than typical sizes of microbial colonies or biofilms. We thus expect clonal interference to be a widespread phenomenon-rather than the exception-in growing dense cellular clusters that conserve their spatial structure over time. Our most important predictions for the regime of clonal interference may be summarized as follows: When the habitat size exceeds a characteristic length L c , multiple adaptation waves are simultaneously in progress at any one time because beneficial mutations frequently arise on different genetic backgrounds. Which of the competing clones prevails and reaches fixation depends on a tug-of-war between interfering Fisher waves. Remarkably, we find that in this "frustrated" situation, increasing the habitat size does not only lead to an increased loss of beneficial mutation: The adaptation speed actually even saturates to a limiting value V max , which is seen for both constant and distributed selective coefficients (see Appendix F). This speed limit of adaptation and its dependence on parameters were not revealed in a previous study (Gordo and Campos 2006) , seemingly because too small habitats were simulated. A simple approximate expression for the speed limit is provided by Equation 3. In particular, we found that V max is proportional to m 1/2 and m 1/3 in linear and planar habitats, respectively. This scaling was shown to hold for various distributions of fitness effects, including constant and exponentially distributed fitness effects, for very noisy and for deterministic Fisher waves. We may thus conclude that the predicted power laws are very robust toward details of the underlying model. Both the speed limit and the robust power law scaling with the mutation rate are in stark contrast to well-mixed standard models, which predict that adaptation speeds never saturate and depend logarithmically on both population size and mutation rates. An experimental comparison of adaptation in well-mixed and spatially structured habitats should therefore yield qualitatively and quantitatively different results. Experiments have already found qualitative differences in the adaptation dynamics of well-mixed and structured E. coli populations (Habets et al. 2006 (Habets et al. , 2007 Perfeito et al. 2008) . Our model suggests that the speed limit of adaptation, V max , may be detected and thus quantified by varying the size of the microbial colony. The power law dependence of the limiting adaptation speed on both mutation rate and population density could be tested by comparing wild type with a mutator strain (Shaver et al. 2002) and by manipulating the thickness of the colony, respectively. The prevalence of clonal interference and the associated speed limit raises the question of how clonal interference may be overcome in spatially extended populations. Certainly, genetic exchange [in bacteria through lateral gene transfer (Cooper 2007) ] provides a mechanism that lessens clonal interference as it allows one to bring together beneficial mutations that arose on different genetic backgrounds; see Figure 5B . This hypothesis, originally formulated by Fisher (1930) and Muller (1932) , is corroborated by our simulation results in Figure 4A . However, our simulations also show that spatial mixing is a very efficient alternative mechanism of mitigating clonal interference in structured populations. Spatial mixing increases the growth rate of fitter clones and thus lowers fixation times. Lowering fixation times increases the likelihood for beneficial mutations to occur sequentially on the same background, and therefore clonal interference is attenuated. In our simulations, spatial mixing was introduced by allowing for a small rate of long- Figure 5 How can clonal interference and its deleterious effects on adaptation be overcome in spatially extended populations? (A) Standard clonal interference. The scale L c is the typical distance at which adaptation waves collide in the clonal interference regime. (B) Recombination speeds up adaptation by combining beneficial variants (Fisher-Muller hypothesis) . Two clones (red and blue) share interfaces (highlighted white) until recombination occurs (5), and a more fit recombinant arises (violet); another recombination occurs later (yellow and violet result in the green mutant). (C) An alternative mechanism of mitigating clonal interference is provided by spatial mixing, e.g., through long-range migration. Long-range jumps (arrows) accelerate selective sweeps and therefore increase both the interference scale and the fixation probability of beneficial mutations. If clonal interference is strong, spatial mixing is thus predicted to be under strong selection. Stars denote only mutations that eventually reach fixation. range jumps. These jumps enable clones to replicate themselves at distant locations in the habitat, which was shown to lead to accelerated clonal growth, as illustrated in Figure 5C . When clones do not interfere, the growth is exponential. The rate of this exponential growth, or effective selection coefficient s e , was found to depend on both the actual selection coefficient and the rate of long-range jumps (cf. Equation 4). Importantly, we found that, due to these fast Malthusian sweeps, even very small rates of long-range jumps strongly increased adaptation speeds in the clonal interference regime (cf. Figure 4B) . Thus, long-range migration seems highly beneficial in spatially extended populations with homogeneous selection pressures. Nevertheless, it remains to be seen in future work whether alleles conferring the ability of long-range migration are actually selected, even if large jumps impose a danger (for instance, a longrange jump could be fatal to a cell if the cell is swept away to a harmful environment). This evolutionary mechanism could be relevant for biofilm-forming bacteria and select for occasional switching from the biofilm state to the more efficiently dispersing planctonic phenotype. In summary, we have analyzed a model of interfering waves. Our model suggests that clonal interference is widespread in biofilms and leads to markedly different adaptation dynamics than in well-mixed populations. In particular, the speed limit V max and its power law dependence on mutation rates should be quantifiable in evolving microbial colonies. Finally, we found spatial mixing to be highly beneficial in structured populations as it relaxes clonal interference and speeds up adaptation. We represent the habitat by a linear lattice of length L in one dimension and a planar hexagonal lattice of side length L in two dimensions. In both cases we choose periodic boundary conditions. Each site represents the identity of the dominating clone (represented by one haploid genome). The habitat is homogeneous and the selection pressure is the same everywhere. The habitat is fully populated at any time. Generations are nonoverlapping, such that the genome at site i descends from the genomes of the neighboring sites of the parent generation. The algorithm stores at each lattice site the genotype of the locally dominating clone, which represents a subpopulation of K individuals in a well-mixed deme. This representation is valid when (i) clones within the deme do not interfere and (ii) the growth of a clone within the deme generates expanding clonal waves. These conditions are quantified as follows. If a beneficial mutation becomes established, it grows into an expanding wave after a timescale of t est = O(1/s). During this establishment time, the clone spreads diffusively over a length scale The establishment time t est can be estimated by t est % log (Kjs 0 )/s 0 , which is the time it takes for a beneficial mutation to fix in a well-mixed population of size Kj. As a consequence, the length scale j is determined self-consistently via Up to logarithmic corrections, we thus have t est % 1/s 0 and j $ ffiffiffiffiffiffiffiffiffiffi ffi m=s 0 p , which corresponds to the width of a Fisher wave (Fisher 1937) . For Fisher waves to occur, we have to require that the habitat size L . j and that j ? 1, i.e., that wave fronts are much broader than a single deme size. The representation in terms of locally dominating genotypes at each lattice site is appropriate only when clones do not interfere on the length scale j. In other words, our model is valid when the time between the establishment of two successive beneficial mutations in a habitat region of size j, estimated by (KjU b 2s 0 ) 21 , is larger than the expected establishment time t est . This condition is equivalent to which-up to logarithmic corrections-amounts to K ffiffiffiffiffiffiffiffiffiffiffiffi m= s 0 p U b >1. This condition defines an upper bound for the mutation rate, given by Simulations are started with a population devoid of genetic variation. As time passes, beneficial mutations occur at a constant rate m per site and generation. The selective fitness advantage s of a mutation is chosen to be either constant or drawn from a distribution with mean value s 0 . We choose either an exponential distribution or a humpshaped gamma distribution with shape parameter k = 2, which are both frequently used in theoretical evolution models (Eyre-Walker and Keightley 2007) . Fitness is updated according to W i / W i (1 + s) when a mutation with effect s is drawn at site i (hence epistasis is neglected). To avoid numerical overflow we compute the logarithmic fitness. The speed of adaptation on the population is defined by the rate of change of logarithmic fitness; i.e., V ¼ log½ For the simulation of the linear habitat, we devised an algorithm that enables us to control the speed of advancing clonal waves. This allows us to check the robustness of our scaling hypotheses toward the different wave velocity relations for strong selection, c ¼ 2 ffiffiffiffiffiffiffiffiffiffiffiffi mDW p (Fisher 1937; Kolmogorov et al. 1937 ) (m represents the migration rate between sites), and for weak selection, c $ 2rmDW, respectively (Doering et al. 2003; Hallatschek and Korolev 2009) . Natural selection is implemented such that waves run across sites with the velocity c = c(DW) (DW is the fitness difference between the clones on both sides of the wave front) and alter the spatial extent of different clones. We use an auxiliary lattice every half generation, shifted by half a lattice site, as shown in Figure A1 . As a consequence, an individual at location i in the offspring generation (t + 1 2 ) may descend from only two individuals in the parent generation (t), i.e., the neighbor to the left or to the right (see Figure A1 ). The fitness difference between the left and right sites is then defined as DW = W l 2 W r . The lattice formed by full and half generations forms a hexagonal lattice in space-time coordinates. In Figure A1 , a more advantageous clone is shown on the left (red) and a less fit wild type on the right (white). The fitter clone is more likely to reproduce and therefore, on average, tends to move to the right. The genome to be passed on to site i in the offspring generation t + 1 2 descends from either the left or the right immediate neighbor in the parent generation t, depending on its fitness difference DW. To determine from which site the genome is passed on, we assign two probabilities p l and p r to the left and right parents. The probabilities must sum to unity; i.e., p l + p r = 1. To obtain a resulting motion of the advantageous clone according to a given velocity relation c(DW), we let the difference of the two probabilities be equal to the wave velocity; i.e., |c(DW)| = |p l 2 p r |. As a consequence, the advantageous clone moves with an average velocity of c(DW). To confirm that our algorithm reproduces the correct wave velocity relations, we have measured ensemble averages of Figure A1 Simulation scheme in the linear habitat. Mutant waves advance with a prescribed velocity relation c ¼ c(DW), corresponding to weak or strong selection. The fitness difference DW ¼ W l 2 W r defines a velocity according to the wave velocity relation c(DW) (chosen for either strong or weak selection). The offspring is picked from the two immediate neighbors in the parent generation at t. An auxiliary lattice is used every half generation (t + 1 2 ), shifted by half a lattice site (corresponding to a hexagonal lattice in space-time coordinates). The probabilities of picking either left or right neighbor are defined via |p l 2 p r | ¼ |c(DW)| and p l + p r ¼ 1. Long-range migration occurs at a rate m l (per site and generation), whereas the distances of the jumps are drawn uniformly. Selection occurs in the parent generation between one of the neighboring parent individuals and the randomly chosen distant parent (blue arrow). the wave velocity c in the absence of clonal interference; see Figure A2A . For the deterministic Fisher wave speed the migration rate is m = 1/4, and for the noisy Fisher wave speed the product of migration rate and population density is rm = 1. For the case of nonstructured populations in the absence of clonal interference, it is known that the probability of fixation of a mutant with a small fitness effect s is equal to 2s (Haldane 1927; Kimura 1962) . Maruyama showed that the fixation probability is the same for spatially structured populations (Maruyama 1974) , under the assumptions of a structurally subdivided population with symmetric migration and haploid individuals that evolve according to the Moran process in each subpopulation. This result was later also confirmed in simulations of spatially structured habitats (Gordo and Campos 2006; Gonçalves et al. 2007 ) (see also Drossel 2001 and Patwa and Wahl 2008 for detailed reviews of fixation probabilities). However, when we choose to use the linear wave velocity relation for weak selection, we find that our algorithm yields a fixation probability that deviates from 2s. We therefore made an adjustment to our simulation to compensate for this deviation, such that mutations fixate with probability 2s. To accomplish this, we imposed a survival probability on every new mutation. We first measured the fixation probability for a given velocity, P fix (c). Given that a new mutation must survive with probability 2s, we determine a survival probability via P surv (s, c) = 2s/P fix (c). Accordingly, in the adjusted algorithm, we allow only new mutations to survive the next generation with probability P surv . The resulting fixation probability approximates the re-quired fixation probability of 2s well for small s, as shown in Figure A2B . Spatial mixing is implemented so that any given clone competes at a small rate m l with a randomly chosen clone rather than with its immediate neighbor. Such a long-range migration event is indicated by the blue arrow in Figure A1 . Accordingly, we determine the probabilities for passing on the genomes from the two competing sites by calculating the fitness difference DW between the randomly chosen site and a neighboring site. The implementation of recombination is shown in Figure A3 . Recombinants are produced at a rate r per site from two (haploid) individuals randomly selected from the nearest neighborhood in the parent generation (selfing is allowed) by determining the probabilities p l and p r , according to the rules described above without recombination. Recombinant genotypes are formed from the parental genotypes A and B by one-point recombination: The parent chromosomes are paired and a point x exc is randomly chosen by which both chromosomes are split. The mutations to both sides of the recombination point are then exchanged between the two chromosomes, forming the recombinant genotypes A 1 B 2 and A 2 B 1 . One of these two genomes is chosen randomly and passed on to the offspring generation. To perform recombination of two genomes, we need to keep track of all mutations and any time. Doing so is computationally expensive when many clones are sweeping simultaneously in the population. In this situation, the algorithm exceeds the complexity of O(L) that is expected otherwise and scales also with the number of present clones. As a consequence, simulation times explode when we try to obtain results deep in the clonal interference regime, i.e., for L ? L c . Recombination occurs at a rate r per site and generation. Sites occupied by the wild type are shown in white and sites occupied by advantageous mutations are shown in red. Two parent genomes are selected from the parent generation. Subsequently, their genomes are separated at a random position x exc and the resulting genome parts are swapped to form the recombined genomes A 1 B 2 and A 2 B 1 . One of them is chosen randomly and passed on to the next generation. Figure A4 Planar habitats are represented by a hexagonal lattice. An auxiliary shifted lattice is used every half generation just as in the linear case. The offspring site inherits genomes from the three surrounding sites with probabilities p k ¼ W k /(W 1 + W 2 + W 3 ) with k ¼ 1, 2, 3. For planar habitats we do not directly control the wave velocity relation, but use a simplified scheme. The habitat is represented using a hexagonal planar lattice. As in the simulation of the linear habitat, we use an auxiliary shifted lattice at every half time step (t + 1 2 ), as shown in Figure A4 . Thus we have three sites in the parent generation t surrounding the offspring site at t + 1 2 . Selection is performed such that the offspring site inherits the genome of one of the neighboring sites proportional to their fitness differences. This means that we need to compute three probabilities p k = W k /(W 1 + W 2 + W 3 ) for inheriting the genome from the parent at site k. We measured the velocity relation c(DW) resulting from this algorithm, shown in Figure A5A . The relation matches the behavior expected from a deterministic Fisher wave, , with a prefactor k = 1 4 . We also measured the fixation probabilities, shown Figure A5B . The fixation probability assumes the expected behavior of 2s for small selective coefficients (Maruyama 1974; Gordo and Campos 2006) . The time to fixation in the periodic selection regime is given by t fix $ L/c. For the clonal interference regime, we expect that in general, fixation times should be larger, but it is not obvious how much larger they should be. For the linear habitat we measured the mean fixation time in dependence of the relative habitat size L/L c , shown in Figure B1 . Simulations have been carried out for a large range of habitat sizes L, using the deterministic wave speed c $ 2 ffiffiffiffiffiffiffiffiffiffiffiffi mDW p and s = const. Different data sets for a range of beneficial mutation rates m and selective coefficients s were generated (see Figure B1 legend). Rescaling the fixation time, t fix c/ L c , we find that all data sets collapse on a single master curve and recover the following power law behavior: This result suggests the following fixation scenario: On length scales smaller than L c , the growth of clones is ballistic; that is, they grow linearly in time at a constant speed. As soon as clones reach the size L c , they start to collide with neighboring clones, which may have higher or lower fitness depending on the mutations they have accumulated in the past. As a consequence, the size of a clone follows a random walk on length scales larger than L c . The variance of the size of the winning clones increases over time until it becomes of order L 2 , upon which fixation occurs. Now, if the random walk of the clone size was a normal random walk (similar to, e.g., Brownian motion), we would expect the clone size variance to grow linear with time. Hence, fixation should occur after a time of order L 2 . By contrast, we find much The fixation probability behaves like 2s for small selective coefficients s. The wave velocity was measured for a habitat of N = L · L = 1024 · 1024 sites over two fixation events. The fixation probability was measured in a smaller habitat with L = 256. Measurements of fixation times in a linear habitat. (A) Simulations reveal that fixation times in the clonal interference regime scale like t fix $ L 3/2 . All data collapse when using rescaled variables t fix Á c/L c and L/L c . (B) Standard deviation of the fixation times in dependence of the relative habitat size L/L c . Simulations are carried out with s 0 ¼ 0.25 with m ¼ 3.125 · 10 23 , 5.6 · 10 23 , and 7.8 · 10 24 and s 0 ¼ 0.1 with m ¼ 1.25 · 10 26 , 7.8 · 10 24 , 5.6 · 10 23 , and 3.125 · 10 23 ; clonal waves travel with the deterministic Fisher wave speed c ¼ 2 ffiffiffiffiffiffiffiffiffiffiffiffi ffi mDW p ; and selective coefficients are constant. earlier fixation after a time of order L 3/2 . This indicates that the random walk of the clone size is superdiffusive and (with the dynamical exponent of 3 2 ) belongs to the Kardar-Parisi-Zhang universality class that describes a wide range of surface growth models (Kardar et al. 1986) . Indeed, if fitness as a function of time is interpreted as the height of a crystal, then our asexual model with constant selective advantage s 0 and deterministic adaptation waves maps to the so-called polynuclear growth model (Prähofer and Spohn 2000) . Appendix C: Fitness Correlation Function and Interference Scale L C We also measured the space-dependent mean-squared fitness variance (MSFV), which correlates the log fitness W at a location separated by a distance x. The angle brackets indicate that the average is taken over all positions j in the habitat. As shown in Figure C1 , the MSFV is linear in distance for large habitats and obeys the scaling relation depending on the mean selective fitness advantage s 0 and the interference scale L c . Since Equation C2 predicts GðL c Þ ¼ s 2 0 , it is consistent with the view that clones expand over a characteristic length L c until they collide with neighboring clones, which differ in log fitness (typically) by s 0 . Furthermore, Equation C2 allows us to calculate the global variance in log fitness as in large systems. The fitness variance in large systems is thus proportional to the total habitat size and is inversely proportional to the interference scale L c . While many studies provide estimates for the mutation rates in microbes, fewer results are available regarding the beneficial mutation rate U (per generation and per genome) (Elena et al. 1996; Perfeito et al. 2007) and their selective coefficients. Some results that are relevant to us are compiled in Table D1 (for a review see Sniegowski and Gerrish 2010) . Some studies suggest mutation rates as low as U $ 10 29 or 10 28 per genome per generation (Gerrish and Lenski 1998; Imhof and Schlötterer 2001; Rozen et al. 2002) . How-ever, these studies were carried out for large effective population sizes (N e $ 10 7 ) that had not been previously exposed to the used growth environment (and adapted accordingly). Under such circumstances, one expects that the supply rate NU is rather high; at the same time, effects of clonal interference are predicted to be very strong. In this case, not taking into account effects of genetic drift and clonal interference would lead to an underestimate of m and an overestimate of the average effect of beneficial mutations (Sniegowski and Gerrish 2010) . More recent studies suggest that the rate of beneficial mutations is much higher. Experiments with E. coli (Perfeito et al. 2007) and Saccharomyces cerevisiae find for smaller effective population sizes (N e $ 10 4 )-thus avoiding clonal interference-beneficial mutation rates of U $ 10 25 . Data from previous studies yielding the lower estimates of U $ 10 29 (Elena et al. 1996; Gerrish and Lenski 1998) have been reanalyzed (Sniegowski and Gerrish 2010) by using a likelihood model that accounts for both drift and clonal interference. One then obtains a much higher value of U $ 10 25 , which is in line with recent estimates (Wloch et al. 2001; Perfeito et al. 2007) . Considering an estimate for the rate of all mutations (i.e., including neutral and deleterious mutations) of order 10 23 (Drake et al. 1998 ) means that beneficial mutations make up $1% of the total number of mutations. Still, the matter is not quite that simple. Even if we restrict our attention to habitats on petri dishes, we may expect that different environments may yield different U. Moreover, spatial structure may also play a role. Thus, to estimate L c , we use a range of U $ 10 26 . . . 10 24 for the mutation rate. For the selective coefficient we use s 0 = 0.01, which compares well with the estimates in Table D1 . Figure C1 The distance-dependent mean squared variance G(x) in log fitness for a population in a linear habitat when clonal interference is rampant. Note that the data corresponding to different habitat sizes (asymptotically) approach a straight line (dashed line) with slope of order O(1) for large habitats L > L c . Simulations were carried out for a range of habitat sizes, using the deterministic Fisher wave velocity c ¼ 2 ffiffiffiffiffiffiffiffiffiffiffiffi ffi mDW p ; s ¼ const.; s 0 ¼ 0.1; and m ¼ 10 24 , 5 · 10 25 , and 10 25 and the corresponding values for the interference scales are L c % 89 (red lines), 125 (blue lines), and 281 (black lines). The crossover condition between periodic selection and clonal interference regimes is t fix $ t mut , which allows us to determine a characteristic population size above which clonal interference is expected. For a nonstructured population, the waiting time for successful mutations is t mut $ ðNUpÞ 21 ; (D1) where the fixation probability is p = 2s 0 . In nonstructured populations the fixation time differs from the one in spatial structures and is given by (Crow and Kimura 1970) . The crossover condition becomes the implicit equation 2NU log(Ns/2) $ 1. Using a selective coefficient of order s 0 $ 0.01 and a mutation rate in the range of U = 10 26 . . . 10 24 , we find a lower and an upper bound for the characteristic population size as follows: To estimate the interference scale L c for microbial populations, we are going to need estimates for the population density r and the wave velocity c. In the forthcoming, we measure length in units of cell length, which for the rodshaped E. coli are of order 3 mm and for S. cerevisiae of order 5-10 mm. Provided that cells are packed densely, the absolute lower boundary of the population density must be r = 1 per square cell lengths. To estimate the population density in a planar population of E. coli, we refer to experimental data (Perfeito et al. 2007) , where bacteria are grown on a petri dish as a lawn (diameter 6 cm = 60,000 cell lengths, i.e., a radius of R = 30,000 cell lengths). The area of a petri dish occupies $A = pR 2 $ 10 9 square cell lengths. The population in this experiment grows to a final size of N f = 10 10 . Thus the population density r [ N f /A is in this case r $ 10 per square cell lengths. However, microbial colonies on rich medium can certainly grow to larger thicknesses. For instance, a thickness of 1000 cell diameters is not uncommon for a colony of S. cerevisiae. To account for a range of situations we consider a range of densities bounded by r min $ 1; (D5) r max $ 1000: Estimating the Wave Velocity The wave velocity is a function not only of the selective coefficient s 0 and the population density r, but also of the diffusion constant m. The relevant diffusion constant in two dimensions is given by where DX is the expected dislocation distance to occur per generation. For a densely packed population of bacteria, it is reasonable to assume that DX is at least of the order of 1 cell length and at most of the order of 10 cell lengths (far displacement is possible in street formations of rod-shaped E. coli); i.e., DX = 1 . . . 100 cells. Thus, we expect m = 0.25 . . . 2500 square cell diameters per generation. To estimate the Fisher wave velocity we use the deterministic wave velocity relation c ¼ 2 ffiffiffiffiffiffi sm p . We find a lower bound of c min = 0.1 and for the upper bound c max = 10 cells per generation. In conclusion, we find the following upper and lower bounds for the interference scale L c in a planar habitat: These are the estimates that we provide in the Discussion of the main text. As discussed in the main text, small rates of long-range jumps drastically increase the adaptation speed V. Figure E1 shows the increase of the adaptation speed V relative to the adaptation speed without long-range migration, Vj m l ¼0 . Long-range jumps generate "seeds" with identical genomes far off the ancestral clone and thus multiply the Gerrish and Lenski (1998), Rozen et al. (2002) , and Imhof and Schlötterer (2001) 10 29 . . . 10 28 -E. coli Elena et al. (1996) 2 · 10 29 0.03 E. coli 2.4 · 10 25 0.01 S. cerevisiae Perfeito et al. (2007) 2 · 10 25 0.02 E. coli Sniegowski and Gerrish (2010) (data from Elena et al. 1996) 5.7 · 10 25 0.003 E. coli growth rate of the ancestral clone. Long-range migration has no effect on the periodic selection regime, because it does not change the limiting supply of beneficial mutations. However, generating seeds may reduce the time for the clone to fixate. As a consequence, effects of clonal interference are mitigated (and thus, the adaptation speed is increased). Moreover, the range of parameters over which periodic selection occurs, characterized by t fix > t mut , becomes larger with increasing rates of long-range migration. We briefly investigate a simple model that explains how long-range migration may lead to an exponential growth of a clone. We assume that waves propagate deterministically (i.e., on straight lines) and that jumps occur before the first (ancestral) clone reaches fixation. Furthermore we assume that at any time there is no more than one mutation present in the habitat (i.e., absence of clonal interference). To effectively generate a seed, an individual must jump from a region already occupied by the ancestral clone to an unoccupied region in the habitat. We denote the average number of such clonal seeds, present at time t, by the variable nðtÞ. Furthermore, xðtÞ is the average length in a linear habitat (or the area in a planar habitat) that is occupied by the clone. The growth of a clone follows from the following considerations: First, the rate of change of the number of seeds is given by the product of the spatial occupation of the clone, xðtÞ, and the rate at which long-range migration events occur per site, i.e., m l . Second, the rate at which the spatial occupation increases, i.e., the effective growth rate of the clone, d x=dt, is twice the velocity of a single wave front times the number of waves present in the population. We denote the velocity of the ancestral clone by c 0 . These considerations are summarized in the following ordinary differential equations: At time t = 0, just after a mutation has occurred in the habitat, space is unoccupied, xð0Þ ¼ 0, and the number of clonal waves is nð0Þ ¼ 1. With this initial condition, the exact solution of Equations E1 and E2 is where we define the effective growth rate s e ¼ ffiffiffiffiffiffiffiffiffiffiffiffi 2c 0 m l p : This is Equation 3 in the Results section of the main text. The growth rate s e is related to the time it takes for a second mutation to appear. Solving for the condition n(t 2 ) = 2 yields The growing number of seeds eventually results in fixation of the clone once space is fully occupied by the clone; i.e., xðt fix Þ ¼ L. This condition yields a characteristic timescale for the fixation process, Equation E3 describes exponential growth at rate s e when t?s 21 e . The solution is a reasonable approximation until xðt fix Þ $ L. For larger times, the assumption that new seeds are born into unoccupied regions cannot be maintained. When the seeds start merging, the effective wave velocity d x=dt also slows down because the number of traveling wave fronts decreases until the growth of the clone comes to a complete halt. Figure F1 Saturation of the adaptation speed for large habitats for exponentially distributed selective fitness effects. The adaptation speed saturates for large habitat sizes when fitness effects are distributed, just as in Figure 2 where s = const. Simulations were carried out with m b = 5 · 10 26 and the deterministic wave speed for $2000 fixations. Z N 0 s 2 gðsÞds: The mean value of the distribution is m[ R N 0 s gðsÞds ¼ s 0 : Because of the identity varðsÞ[ R N 0 ðs2mÞ 2 gðsÞds ¼ R N 0 s 2 gðsÞds2m 2 , we have that This implies that a nonzero variance increases the adaptation speed even for the periodic selection regime. When s = const., the variance is zero, but we have varðsÞ ¼ s 2 0 for the exponential and varðsÞ ¼ s 2 0 =k for the gamma distribution (in our simulations, we chose a shape parameter of k = 2). The shifted values of the adaptation speed hVi seen in Figure 3 can thus be explained by the differing variance values of the various selective fitness distributions. Periodic selection in Escherichia coli Genome evolution and adaptation in a long-term experiment with E. coli Recombination speeds adaptation by reducing competition between beneficial mutations in populations of Escherichia coli An Introduction to Population Genetics Theory Beneficial mutation selection balance and the effect of linkage on positive selection The speed of evolution and maintenance of variation in asexual populations Diminishing returns from mutation supply rate in asexual populations Interacting particles, the stochastic FKPP equation, and duality Rates of spontaneous mutation Biological evolution and statistical physics Spatial dynamics of the 1918 influenza pandemic in England, Wales and the United States Punctuated evolution caused by selection of rare beneficial mutations The distribution of fitness effects of new mutations The Genetical Theory of Natural Selection The wave of advance of advantageous genes The fate of competing beneficial mutations in an asexual population Speed of adaptation in structured populations Adaptive evolution in a spatially structured asexual population Mitochondrial DNA mutations are established in human colonic stem cells, and mutated clones expand by crypt fission The effect of population structure on the adaptive radiation of microbial populations evolving in spatially structured environments Spatial structure inhibits the rate of invasion of beneficial mutations in asexual populations A mathematical theory of natural and artificial selection The noisy edge of traveling waves Fisher waves in the strong noise limit Life at the front of an expanding population Forecast and control of epidemics in a globalized world Fitness effects of advantageous mutations in evolving E. coli populations Dynamic scaling of growing interfaces The complex network of global cargo ship movements On the probability of fixation of mutant genes in a population A study of the equation of diffusion with increase in the quantity of matter, and its application to a biological problem Spatial structure increases the waiting for cancer. ar-Xiv:1106.3005 A simple proof that certain quantities are independent of the geographical structure of population Cancer as an evolutionary and ecological process Clonal interference and the evolution of RNA viruses Some genetic aspects of sex Emergence of spatial structure in cell groups and the evolution of cooperation Rate of adaptation in large sexual populations Experiments with the chemostat on spontaneous mutations of bacteria Clonal interference in large populations The fixation probability of beneficial mutations Adaptive mutations in bacteria: high rate and small effects The effect of spatial structure on adaptation in E. coli Universal distributions for growth processes in 1+1 dimensions and random matrices Parallel adaptation: One or many waves of advance of an advantageous allele The solitary wave of asexual evolution Fitness effects of fixed beneficial mutations in microbial populations Clonal expansions in ulcerative colitis identify patients with neoplasia Fitness evolution and the rise of mutator alleles in experimental E. coli populations Beneficial mutations and the dynamics of adaptation in asexual populations Spatial organization of microbial biofilm communities Biofilm, city of microbes Direct estimate of the mutation rate and the distribution of fitness effects in the yeast Saccharomyces cerevisiae We thank P. Sniegowski, A. deVisser, J. Krug, F. Stiewe, S. Boekhoff, and J. Nullmeier for helpful discussions. We have discussed above that the speed of adaptation saturates for large habitats when clones interfere. Figure F1 demonstrates the same saturation phenomenon when the selective fitness is exponentially distributed. We expect that the saturation behavior documented for constant and exponentially distributed selection coefficients occurs for all subexponential fitness effect distributions. At this point, it is unclear how superexponential distributions might affect the adaptation dynamics.Compared to the case of the constant selection coefficient, a nonzero variance of the distribution of fitness effects g(s) increases the speed of adaptation. For periodic selection, this can be easily understood as follows. The expectation value of the adaptation speed is given by hVi = hNU b 2s 2 i or, more precisely, by Figure E1 Relative increase of the adaptation speed V due to long-range migration. Even a small rate m l = 0.001 of long-range migration drastically increases the speed of adaptation by a factor of $5. Simulations are run with s = const. and parameters s 0 = 0.1, m = 5 · 10 26 , and the deterministic wave velocity valid for strong selection.