## Abstract

We consider an asexual population under strong selection–weak mutation conditions evolving on rugged fitness landscapes with many local fitness peaks. Unlike the previous studies in which the initial fitness of the population is assumed to be high, here we start the adaptation process with a low fitness corresponding to a population in a stressful novel environment. For generic fitness distributions, using an analytic argument we find that the average number of steps to a local optimum varies logarithmically with the genotype sequence length and increases as the correlations among genotypic fitnesses increase. When the fitnesses are exponentially or uniformly distributed, using an evolution equation for the distribution of population fitness, we analytically calculate the fitness distribution of fixed beneficial mutations and the walk length distribution.

ADAPTATION is an evolutionary process during which a population improves its fitness by accumulating beneficial mutations. A population of genotypic sequences produces a suite of mutants and if better mutants become available, a maladapted population may acquire one of the beneficial mutations provided it does not get lost due to genetic drift. The fitter population in turn may acquire another advantageous mutation and the process goes on until the supply of beneficial mutations gets exhausted. A number of models with variable degrees of biological consistency have been proposed and investigated to understand the process of adaptation (Miller *et al.* 2011). One of the simplest mathematical models was introduced by Gillespie in which beneficial mutations arise sequentially and fix rapidly (Gillespie 1991). If the mutation rate is small and the selection coefficient is large (compared to the inverse population size), it is a good approximation to assume that only the one-step mutants are accessible at any time and the population is localized at a single genotype. Such a monomorphic population performs an adaptive walk by moving uphill on a fitness landscape until no more beneficial mutations can be found.

In the last few years, much of the work on Gillespie’s model has focused on the first step in the adaptation process. If the fitnesses of the wild type and its one-mutant neighbors are rank ordered with the fittest sequence at the top, the well established theory of extremes of independent random variables (David and Nagaraja 2003) can be exploited to obtain useful information provided the wild type has a high fitness (rank). For a moderately high-ranked initial fitness, Orr calculated the expected rank at the first step assuming exponential-like fitness distributions (Orr 2002). His prediction has been tested in an experiment using single-stranded DNA and found to be roughly consistent with the experimental data (Rokyta *et al.* 2005). This result has been later generalized for other fitness distributions (Joyce *et al.* 2008) and by including correlations among fitnesses (Orr 2006). However, as the properties of the entire walk are required to design a drug or a biomolecule (Bull and Otto 2005) and as experimental data on multiple adaptive substitutions are becoming available (Rokyta *et al.* 2009; Schoustra *et al.* 2009), it is important to extend the existing theory to address the statistical properties of the entire walk.

With this aim, we study Gillespie’s *mutational landscape model* on rugged fitness landscapes with many local fitness optima. An important difference between our work and the previous ones is that here we start the adaptive walk with low fitness to describe the adaptation process in novel environments such as when antibiotics are introduced (MacLean and Buckling 2009; McDonald *et al.* 2010) whereas the initial fitness is assumed to be high in other studies (Gillespie 1991; Orr 2002, 2006; Joyce *et al.* 2008). Several numerical (Gillespie 1991; Orr 2006) and experimental studies (Rokyta *et al.* 2009; Schoustra *et al.* 2009) have indicated that only a few steps are required to reach a local optimum. In a simple adaptation model that assumes the mutational neighborhood remains unchanged during the entire adaptive walk (Gillespie 1983), the average number of steps to a local fitness peak has been calculated analytically for various fitness distributions and shown to increase logarithmically with the rank of the initial sequence (Neidhart and Krug 2011). However, here we work with a more realistic mutation scheme in which a new suite of mutants is created in each adaptive step. For generic fitness distributions, we argue that the average number of adaptive steps increases logarithmically with sequence length with a prefactor that depends on the choice of fitness distribution. Although our argument does not capture the proportionality constant correctly, the logarithmic dependence is seen to be in excellent agreement with the simulation results. We also present detailed results on the statistical properties of the entire walk for exponentially and uniformly distributed fitnesses as these two distributions lend themselves to an analytic treatment and are also consistent with the experiments (Eyre-Walker and Keightley 2007; Rokyta *et al.* 2008). Following the approach of Flyvbjerg and Lautrup (1992), we write a recursion relation for the fitness distribution of *fixed* beneficial mutations at an adaptive step that is valid for long sequences and fitness distributions with a finite mean. A similar distribution has been calculated in the clonal interference regime in which multiple mutants are produced per generation (Rozen *et al.* 2002) while here we work in the weak mutation regime. For the above-mentioned distributions, we also find the distribution of walk length. The average walk length calculated using this approach gives a prefactor consistent with the numerical results.

Although for most of the article we work with uncorrelated fitnesses and assume that the distribution of the fitness does not change during the course of evolution, the effect of correlations is also discussed. As experiments support an intermediate degree of correlations in fitness landscapes (Carneiro and Hartl 2010; Miller *et al.* 2011) and changing fitness distributions may be modeled by correlated fitnesses (Orr 2006), we calculate the average number of steps to an optimum on a fitness landscape generated by the block model of correlated fitnesses in which a sequence is divided into several independent blocks and correlations arise when two sequences share some blocks (Perelson and Macken 1995). The average walk length has been measured using numerical simulations in a block model in Orr (2006) and it was speculated that the average number of adaptive steps is independent of the underlying fitness distribution and increases linearly with the number of blocks. We show that while the latter result is roughly correct, the average number of steps to a local optimum is not independent of the fitness distribution, which is a consequence of the result discussed above for the uncorrelated fitness landscapes.

## Models and Methods

### Uncorrelated and correlated fitness landscapes

An uncorrelated fitness landscape can be generated by assigning a fitness to a sequence independent of that of other sequences. The fitnesses are sampled from a common distribution *p*(*f*) with support on the interval [*l*, *u*]. Although the full distribution of absolute fitness is unknown, one can obtain an insight into its nature through the distribution of beneficial mutations that has been measured in several theoretical and experimental studies (Eyre-Walker and Keightley 2007). A theoretical argument suggests that since good mutations are rare, their distribution is governed by the upper tail of the fitness distribution *p*(*f*) (Gillespie 1991). It is known from the extreme value theory (EVT) for independent and identically distributed (i.i.d.) random variables that the asymptotic distribution of the extreme value can be one of the following three types (David and Nagaraja 2003): Fréchet for algebraically decaying underlying distributions, Gumbel for unbounded distributions decaying faster than a power law, and Weibull for bounded distributions. To be consistent with this result, we make the following choices for the fitness distributions:The condition δ > 2 in (1) is imposed to keep the transition rate (6) finite (as explained later). The last two fitness functions (2) and (3) are of particular interest as several experimental results on the distribution of beneficial mutations have been found to lie in the Gumbel domain (Imhof and Schlotterer 2001; Sanjuán *et al.* 2004; Rokyta *et al.* 2005; Kassen and Bataillon 2006; MacLean and Buckling 2009) and a recent work finds a best fit for the distribution of beneficial effects to a uniform distribution that lies in the Weibull domain (Rokyta *et al.* 2008).

We also study adaptive walks on correlated fitness landscapes that are generated using a block model (Perelson and Macken 1995) in which a sequence of length *L* is divided into *B* blocks of equal size *L _{B}* =

*L*/

*B*. The block fitness is an i.i.d. random variable chosen from the distribution

*p*(

*f*) and the sequence fitness is obtained by averaging over the fitnesses of the blocks in the sequence. If two sequences share one or more blocks, their fitnesses are correlated. The correlations can be tuned by changing the number of blocks: If the number of blocks

*B*= 1, sequence fitnesses are completely uncorrelated while

*B*=

*L*gives strongly correlated fitnesses. It should be noted that the extreme value distribution of correlated fitnesses may change from the corresponding i.i.d. class even if correlations are weak (Jain

*et al.*2009; Jain 2011). In the following discussion, we assume that the sequence fitnesses are uncorrelated and deal with the correlated fitnesses in the last subsection of next section.

### Adaptive walk model for long sequences

We work with haploid binary sequences of length *L* in the strong selection–weak mutation (SSWM) regime. If *N* is the population size, the SSWM regime corresponds to *Ns* ≫ 1, *N*μ ≪ 1 where *s* is the selection coefficient and μ is the mutation probability per locus per generation. Since the expected number of mutants produced per generation is much smaller than one, mutations occur sequentially and double and higher mutations may be neglected. Thus the mutational neighborhood of a sequence is limited to *L* mutants that are a single mutation away from it. If the fitnesses of the wild-type sequence and its *L* one-mutant neighbors are arranged in a descending order with the best fitness assigned the rank 1, the transition probability that the population moves from the wild type with fitness rank *i* and value *f _{i}* to a mutant with rank

*j*<

*i*and value

*f*is proportional to the fixation probability, which is well approximated by 2(

_{j}*f*−

_{j}*f*)/

_{i}*f*in the strong selection limit (Gillespie 1991). The normalized transition probability from fitness

_{i}*f*to fitness

_{i}*f*is given by(4)Once the population has moved to a mutant sequence with fitness

_{j}*f*with probability

_{j}*T*(

*f*←

_{j}*f*), it produces a set of new mutants that are rank ordered and chosen according to (4) and the process repeats itself until the population reaches a local optimum whose nearest neighbors are all less fit than itself. Note that the parameters

_{i}*N*and μ have dropped out of the picture and the properties of the model depend on the sequence length (or the initial rank) and the distribution of sequence fitnesses.

The model described above has been studied using (4) and EVT in previous works (Gillespie 1991; Orr 2002, 2006; Joyce *et al.* 2008) assuming the initial fitness to be high (small *i*). In contrast, we start with a low fitness and write a recursion relation for the probability *P _{J}*(

*f*) that an adaptive walk has at least

*J*steps and the fitness is

*f*at the

*J*th step, following Flyvbjerg and Lautrup (1992) who studied this distribution for random adaptive walks (see

*Appendix A*). In the following discussion, it is assumed that the sequence length is large, which allows the following two simplifications: First, the events in which a sequence is backtracked can be ignored and second, the transition rates can be written in terms of absolute fitnesses instead of fitness ranks. Consider a population at the

*J*th adaptive step and with fitness

*h*. It can proceed to the next step provided at least one fitter mutant is available. If , this event occurs with a probability 1 −

*q*(

^{L}*h*), where it is assumed that at each step in the evolutionary process,

*L*novel mutants are available that have not been encountered before. While this is true at the first step, the number of novel mutants is

*L*− 1 at the second step since one of the mutants is the parent sequence itself that is not an allowed descendant as the walk always proceeds uphill. In fact for any

*J*≥ 2, some of the mutants have already been probed but the error introduced by ignoring this complication is of the order of 1/

*L*, which is negligible for large

*L*(Flyvbjerg and Lautrup 1992). Then for long sequences we can write(5)where

*p*(

*f*)

*T*(

*f*←

*h*) gives the probability that a mutant with fitness

*f*>

*h*is chosen. Furthermore for large

*L*, it is a good approximation to replace the sum in the denominator of (4) by an integral and we may write(6)Thus we work with absolute fitnesses instead of fitness ranks. Since the transition probability (6) vanishes for slowly decaying fitness distributions

*p*(

*f*) ∼

*f*

^{−δ}, δ ≤ 2, we restrict δ > 2 in (1). Using (6) in (5), we finally obtain

Equation 7 is the central equation of this article and we employ it to obtain various results on the statistical properties of adaptive walks. In the following, we assume the initial condition *P*_{0}(*f*) = δ(*f*) corresponding to zero initial fitness. As *P _{J}*(

*f*) obeys an integral equation that is harder to analyze, we may try to write a differential equation for

*P*(

_{J}*f*). Differentiating (7) with respect to

*f*, we get(8)(9)where the prime denotes an

*f*-derivative. On using (7) and (8) in (9), we find(10)The first derivative term in the above equation can be eliminated by writing , which finally yields

In this article, we restrict our attention to exponentially and uniformly distributed fitnesses as these two fitness distributions are consistent with the available empirical data. We show that due to (9), a second-order ordinary differential equation is obeyed by a generating function of *P _{J}*(

*f*) for these two distributions, which can be solved within an approximation subject to the boundary conditions(12)(13)where (12) is a direct consequence of (7) and (13) arises on using the initial condition in (8).

Besides *P _{J}*(

*f*), we also find the walk length distribution

*Q*and the average fitness at the

_{J}*J*th step, which can be related to

*P*(

_{J}*f*) as explained below. Integrating over

*f*on both sides of (7), we get(14)(15)(16)Then the walk length probability

*Q*that exactly

_{J}*J*steps are taken is given by(17)with

*Q*

_{0}= 0 since the initial fitness is zero. The above equation has a simple interpretation: Since

*P*(

_{J}*h*) is the probability that at least

*J*steps are taken and the fitness at the

*J*th step is

*h*, exactly

*J*steps will be taken if all the

*L*mutants of the sequence at the

*J*th step carry a fitness smaller than

*h*from which (17) follows. The average walk length for large

*L*. The average fitness is defined as . Using (7), we can write(18)(19)Note that neither (17) nor (19) is a closed equation.

Our analytical results are also compared with numerical simulations that were performed using an exact procedure for *L* ≤ 10 and an approximate method outlined in Orr (2002) for larger *L*. We refer the reader to *Appendix B* for details.

## Results

### Average fitness and walk length for general fitness distributions

For a broad class of fitness distributions, the average fitness for an infinitely long sequence can be computed. Although this limit is biologically unrealistic, it provides a good approximation to the average fitness for small *J* (see Figure 1) as the population cannot sense the finiteness of sequence length far from the local optimum. On taking the limit *L* → ∞ in (19) and denoting the average fitness in this limit by *F _{J}*, we obtain(20)

#### Algebraically decaying fitness distributions:

On substituting (1) in (20) and performing the integrals involving *p*(*f*), we get(21)where we have used that *P _{J}*|

_{L}_{→∞}= 1 due to (16) and the initial condition

*P*

_{0}= 1. Repeated iteration with

*F*

_{0}= 1 yields(22)which increases geometrically with

*J*. This result is compared in Figure 1A with the average fitness for finite sequences, which shows that the number of steps up to which and

*F*match increases with

_{J}*L*.

#### Exponential fitness distribution:

For fitness distributions given by (2), the equation for *F _{J}* does not close except for γ = 1. For

*p*(

*f*) =

*e*

^{−}

*, we get*

^{f}*F*= 2 +

_{J}*F*

_{J}_{−1}, which gives(23)Figure 1B shows that the rate of increase of fitness is slower than a constant at larger

*J*’s.

#### Bounded fitness distributions:

A calculation similar to that above for *p*(*f*) in (3) gives(24)and therefore(25)For uniformly distributed fitness (ν = 1), we find that 1 − *F _{J}* = 3

^{−}

*in good agreement with the numerical data in Figure 1 for small*

^{J}*J*.

We now give an argument to estimate the average walk length using the above results for the average fitness *F _{J}* and the EVT (Flyvbjerg and Lautrup 1992). We first note that since

*P*|

_{J}

_{L}_{→∞}= 1 for all

*J*, every step in the adaptive walk is definitely taken for infinitely long sequences and hence the average walk length is expected to diverge with

*L*. For a sequence of finite length, the adaptive walk stops when the population has reached a local optimum whose fitness is the largest among

*L*+ 1 i.i.d. random variables. But since the average number of fitnesses with value ≥

*f*is given by (

*L*+ 1)(1 −

*q*(

*f*)), at a local optimum we have(26)(Sornette 2000), where we have approximated by . The above equation yieldsOn matching the expected fitness with the

*F*obtained in the above discussion for various distributions, we getThus the above argument shows that for large

_{J}*L*,(33)where the prefactor α depends on

*p*(

*f*). We note that α

_{algebraic}< α

_{exponential}< α

_{bounded}, which implies that smaller numbers of substitutions occur for fat-tailed fitness distributions than for the bounded ones. To understand this qualitative trend, consider the transition probability for the first step given by

*T*(

*f*← 0)

*p*(

*f*) ∼

*fp*(

*f*). At large

*f*, this probability is higher for slowly decaying distributions and thus a large fitness gain occurs initially. But as the probability to exceed the high fitness achieved at the first step is small, the walk terminates sooner for broad distributions.

The results of our numerical simulations for shown in Figure 2 are in agreement with the logarithmic dependence on *L* but the value of the prefactor does not match with that obtained above [except for *p*(*f*) = *e*^{−}* ^{f}*]. The prefactor α is expected to interpolate between the two limiting cases of adaptive walks, namely greedy walk in which the best mutant is chosen with probability one and random adaptive walk in which all better mutants are chosen with equal probability. The former limit is obtained when δ → 1 in (1) and the latter when ν → 0 in (3) (Joyce

*et al.*2008). Since the average walk length for a greedy walker is a finite constant equal to

*e*− 1 ≈ 1.718 for infinitely long sequences (Orr 2003), the prefactor α = 0 while α = 1 for the random adaptive walk (see

*Appendix A*). In the following sections, we find that α = for exponentially distributed fitness and α = for the uniform case, which are consistent with the results in Figure 2 and the analytical results of Neidhart and Krug (2011), which are obtained using a simpler version of the adaptive walk model considered here.

### Fitness distribution at the first step for general distributions

If the whole population is assumed to have an initial fitness *f*_{0}, using *P*_{0}(*f*) = δ(*f* − *f*_{0}) in (7) we have(34)The above fitness distribution at the first step is nonmonotonic for all fitness distributions in (1–3) except for truncated distributions with ν ≤ 1. The implications of this result are examined in the *Discussion*.

### Entire walk with exponentially distributed fitness

For *p*(*f*) = *e*^{−}* ^{f}*, from (11) we obtain(35)where

*q*(

*f*) = 1 −

*e*

^{−}

*. Due to (12) and (13), the boundary conditions are*

^{f}*P*(0) = 0 and .

_{J}We define a generating function which obeys the following second-order ordinary differential equation:(36)To arrive at the above equation, we have used that which is obtained by using the initial condition in (7). The generating function *G*(*x*, *f*) obeys a Schrödinger equation for the wave function of a particle in a one-dimensional potential *V*(*f*) ∼ 1 − *q ^{L}*(

*f*) and energy zero (Mathews and Walker 2004). Since is close to unity for

*f*≪≪ ln

*L*and vanishes for

*f*≫≫ ln

*L*, the potential

*V*(

*f*) decreases smoothly from one to zero and moves rightward with increasing

*L*. Similar potentials also arise when two materials with different transport properties are joined together and in such systems, an analytical solution is obtained within a step function potential approximation (Blonder

*et al.*1982; Schaeybroeck and Lazarides 2009). We follow this approach here and approximate the distribution 1 −

*q*(

^{L}*f*) by the Heaviside theta function , where . Within this

*step distribution approximation*, we have

For , the differential Equation 37 has a solution of the form which reduces to since *G*(*x*, 0) = 0 due to . Since the solution for cannot depend on we appeal to the infinite sequence length limit to fix the proportionality constant *c*. As noted earlier, the distribution *P _{J}*|

_{L}_{→∞}= 1 for all

*J*≥ 0, which implies that(38)and therefore(39)We check that the boundary condition which is equivalent to

*G*′(

*x*,0) =

*x*, is also satisfied by the above solution.

For , the solution *G*_{>}(*x*, *f*) = *af* + *b*, where the constants of integration *a*, *b* can be fixed by matching the solutions *G*_{<} and *G*_{>} and their first derivative at . Thus the constants *a* and *b* are determined by the following conditions:(40)(41)A simple algebra shows that

Using the above expressions for *G*(*x*, *f*), the fitness distribution *P _{J}*(

*f*) for the fixed beneficial mutations can be calculated. On expanding (39) and (42) in a power series about

*x*= 0 and picking the coefficient of

*x*, we have(43)where . Figure 3 shows our numerical results for

^{J}*P*(

_{J}*f*) for the first few adaptive steps. As the walk proceeds, the distribution moves rightward as expected and its amplitude decreases since the probability

*q*(

^{L}*f*) that the walker cannot find a better neighbor approaches unity with increasing

*f*. Our analytical result (43) is also shown in Figure 3 for comparison. For

*L*= 10

^{3}, the step distribution approximation used to find (43) gives 1 −

*q*(

^{L}*f*) ≈ 1 for

*f*< ln

*L*= 6.9 and zero otherwise. However, as the probability 1 −

*q*(

^{L}*f*) stays close to unity for

*f*≤ 5 and decreases gradually to zero when

*f*≈ 12, the distribution (43) in the region 5 <

*f*< 12 does not match well with the simulation results but outside this crossover region, we see a good quantitative agreement. We also note that the fitness distribution does not move appreciably for

*J*≥ 4 and is centered around

*f*≈ 7 (see inset in Figure 3). This is because the average walk length for

*L*= 10

^{3}is ∼ 4.6 steps (refer to Figure 2) and as the local optimum is approached, the fitness distribution of fixed beneficial mutation remains centered close to the typical fitness of the local optimum given by (26), which is ln

*L*≈ 6.9. This also explains the initial linear rise in the average fitness followed by a slower increase in Figure 1.

We next calculate the walk length distribution *Q _{J}* defined by (17). Since within the step distribution approximation discussed above, (17) reduces to(44)On integrating

*P*(

_{J}*f*) given in (43), we get(45)This expression is compared with numerical results in Figure 4 and shows a reasonable agreement. The average number of adaptive steps calculated using (45) is given by(46)which is in good agreement with the simulation result in Figure 2. The width of the distribution

*Q*measured using the variance also increases with

_{J}*L*.

### Entire walk with uniformly distributed fitness

For *p*(*f*) = 1, since , the differential equation (11) reduces to(47)with boundary conditions *P _{J}*(0) = 0 and . As before, we define a generating function that obeys the second-order ordinary differential equation(48)where we have used that

*P*

_{1}(

*f*) = 2

*f*. We treat this case also within the step distribution approximation discussed earlier. Since the probability 1 −

*f*≈ 1 −

^{L}*e*

^{−}

^{L}^{(1−}

^{f}^{)}, we approximate it by a step function , where . For , we obtain an inhomogeneous second-order ordinary differential equation with variable coefficients:(49)This equation can be solved by standard methods (detailed in

*Appendix C*) to yield(50)where the exponents(51)The first two terms on the right-hand side give the solution of the homogeneous equation and the last two terms are the particular integral involving the variational parameters given in

*Appendix C*. The constants of integration

*a*

_{±}can be obtained using the boundary conditions

*G*(

*x*, 0) = 0 and . After some straightforward algebra, we find that(52)We verify that the condition for

*J*> 1 that amounts to

*G*′(

*x*, 0) = 0 is also satisfied. For , as , the solution

*G*

_{>}(

*x*,

*f*) =

*af*+

*b*, where

*a*,

*b*can be determined using (40) and (41) to give(53)Explicit expressions for

*P*(

_{J}*f*) for first few adaptive steps are given in

*Appendix C*and a comparison between the analytical and the simulation results is shown in Figure 5.

To find the walk length distribution , we define(54)(55)As an explicit expression for *Q _{J}* is rather unwieldy, its derivation and the expression itself are given in

*Appendix C*and a comparison with the simulations is shown in Figure 6. The average number of steps is given by(56)which shows that for large

*L*, the number of adaptive steps grows as (2/3) ln

*L*in agreement with the numerical results shown in Figure 2. The higher moments can also be found straightforwardly and we find that the variance and the skewness of the distribution decays slowly as (ln

*L*)

^{−1/2}.

### Effect of correlations on the number of adaptive steps

We now turn to a discussion of adaptive walk properties when the fitnesses are correlated and given by a block model. We compute the average number of adaptive steps given by , where *Q _{J}*(

*L*,

*B*) is the probability that exactly

*J*adaptive mutations occur when a sequence of length

*L*is divided into

*B*blocks.

Consider the distribution *Q*(*m*_{1}, … , *m _{B}*), which gives the joint probability that the

*i*th block of length

*L*in a sequence of length

_{B}*L*carries

*m*adaptive mutations, where

_{i}*i*= 1, … ,

*B*. An important property of the block model is that this joint distribution factorizes; that is,(57)(Perelson and Macken 1995), where

*Q*(

_{J}*L*, 1) ≡

_{B}*Q*(

_{J}*L*) is the walk length probability when the fitnesses are uncorrelated and the sequence length is

_{B}*L*

_{B}_{.}The above equation expresses the fact that the block fitnesses evolve independently. As only one mutation occurs in the sequence at any step so that all but one block sequence remains unchanged and since the block fitnesses are i.i.d. random variables, (57) holds.

Since the distribution *Q _{J}*(

*L*,

*B*) is given by(58)it follows that(59)where we have used that and is the average number of steps in the adaptive walk for uncorrelated fitnesses. Figure 7 shows the results of our numerical simulations for average walk length when the block length

*L*=

_{B}*L*/

*B*is kept fixed and the block fitnesses are exponentially and uniformly distributed. For fixed

*L*, (59) predicts that increases linearly with

_{B}*B*, which is in excellent agreement with the numerical data.

For large *L*, due to (33) we have(60)For small *B*, a linear rise in the average number of steps with the number of blocks has been seen numerically for exponential-like distributions and it was inferred that the mean walk length is independent of underlying fitness distributions (Orr 2006). However, as discussed in the previous sections, the average number depends on the fitness distribution *p*(*f*) and therefore the average is also nonuniversal.

## Discussion

In the last few years, several analytical results have been obtained for the mutational landscape model (Gillespie 1991). However, many of these results deal with the first step in the adaptation process (Orr 2002, 2006; Joyce *et al.* 2008) and an extension of the theory to full adaptive walk is necessary. Previous studies also assume that the process of adaptation starts from a highly fit sequence that is not applicable to situations in which the population is subjected to high stress and hence has a very low initial fitness (MacLean and Buckling 2009; McDonald *et al.* 2010). In this article, we have obtained results for the entire adaptive walk starting from a low initial fitness but as discussed below, we expect some of these results to hold for moderately high initial fitness also.

### Walk length distribution and average walk length

In previous works, the walk length distributions for the greedy walk and the random adaptive walk have been studied and found to be universal in that they are independent of the underlying fitness distribution *p*(*f*). The origin of this universality property is clear in the light of the results of Joyce *et al.* (2008) who pointed out that these two models can be obtained as a limit of (4), which defines the mutational landscape model. For the random adaptive walk, the distribution *Q _{J}* for infinitely long sequence vanishes (see Equation A3) and the average walk length diverges with sequence length. In contrast, for the greedy walk, the walk length distribution in the

*L*→ ∞ limit decreases exponentially fast with

*J*for the greedy walk as a result of which the average number of steps turns out to be a constant (Orr 2003; Rosenberg 2005).

In this article, we have calculated the walk length distribution for exponentially and uniformly distributed fitnesses and found the average walk length for general fitness distributions. An important conclusion of our study is that the average number of adaptive steps increases logarithmically with the sequence length with a prefactor smaller than unity if the walk starts from zero fitness. Our simulations (not shown) also indicate that if the initial rank is of order *L*, the average number of steps increases logarithmically with the rank and with the same proportionality constant as that for the zero initial fitness case. Thus for a wild-type sequence with initial rank (or *L*) of the order 100, the number of substitutions is expected to be less than five. Although short adaptive walks have been observed in experiments (Rokyta *et al.* 2009; Schoustra *et al.* 2009), more detailed experimental studies testing the logarithmic dependence would be desirable. Although a test of the *L* dependence of the average walk length may not be experimentally viable, it should be possible to study the average walk length as a function of the initial rank.

Besides the sequence length, the number of steps to a local optimum depends on the underlying fitness distribution and the fitness correlations also. If the fitnesses are uncorrelated, as the numerical data in Figure 2 show, the prefactor α in (33) depends on the shape of the fitness distribution and therefore a rather detailed knowledge of the full fitness distribution (how fast it decays) is required to test this, which is presently unavailable. However, one can discern a trend in the value of α: It decreases as the fitness distribution broadens. This suggests that systems with fitness distribution in the Gumbel class (Imhof and Schlotterer 2001; Sanjuán *et al.* 2004; Rokyta *et al.* 2005; Kassen and Bataillon 2006; MacLean and Buckling 2009) will register shorter walks than those in the Weibull domain (Rokyta *et al.* 2008). As shown here in the block model of correlated fitnesses, the average number of adaptive steps increases as the number of blocks (and hence fitness correlations) increases. This is in accordance with the expectation that on a smooth correlated fitness landscape, as the local optima are less common (Perelson and Macken 1995), there is less chance to get trapped and therefore the uphill walk can last longer (Weinberger 1991; Kauffman 1993; Orr 2006).

### Distribution of fixed beneficial mutations during the walk

The fitness distribution *P _{J}*(

*f*) has not been studied in previous theoretical studies of adaptive walks in the SSWM limit and here we have computed this fitness distribution analytically using the recursion relation (7). The fitness distribution at the first step given by (34) can give a qualitative idea about the shape of

*p*(

*f*). For most fitness distributions,

*P*

_{1}(

*f*) is expected to be nonmonotonic but for bounded distributions that diverge at the upper limit or the uniform distribution,

*P*

_{1}(

*f*) increases monotonically toward the upper bound. An inspection of the experimental data of Rokyta

*et al.*(2005) shows the fitness distribution at the first step to be nonmonotonic, which is consistent with their assumption of exponentially decreasing distribution of beneficial effects. It would be interesting to check whether the distribution

*P*

_{1}(

*f*) in Rokyta

*et al.*(2008) is monotonic as the data in this study are consistent with a uniformly distributed fitness. The above behavior of

*P*

_{1}(

*f*) is expected to be robust in the presence of correlations as at the first step in evolution, the population has not sensed the correlations in the fitness landscape (Orr 2006).

For the fitness distribution for the entire walk, we presented an analysis for two distributions, namely exponential and uniform, that are consistent with the available experimental data. The distribution *P _{J}*(

*f*) is obtained within a step distribution approximation that captures the shape of the fitness distribution correctly for the first few steps and leads to an accurate estimate of the number of average steps. Our approximation consists of replacing the probability 1 −

*q*(

^{L}*f*) by a step function , where is given by (28) for exponentially and by (29) for uniformly distributed fitnesses. For and , our approximate solution matches the simulation results well for any

*J*. With increasing

*J*, the distribution

*P*(

_{J}*f*) shifts toward higher fitnesses and peaks about for larger

*J*’s. As explained earlier, the fitness is reached when

*J*is close to and therefore we expect our approximation to work well for

*J*≪ ln

*L*.

When the underlying fitness distribution is exponential, we find that the fitness distribution of the fixed beneficial mutation also has an exponential tail (see Equation 43). The robustness of this result, *i.e.*, whether any fitness distribution in the Gumbel class exhibits an exponential tail for *P _{J}*(

*f*), is, however, not clear. For uniformly distributed fitnesses, as the width of the distribution 1 −

*q*(

^{L}*f*) decreases with increasing

*L*, the step distribution approximation works better in this case than in the exponential case where the width is a constant (compare Figures 4 and 6). The properties of multiple steps in an adaptive walk have been measured in some recent experiments (Rokyta

*et al.*2009; Schoustra

*et al.*2009) and a detailed analysis of the experimental results would be very welcome. On the theoretical front, an extension of the results described above to distributions other than uniform and exponential would be desirable. We have recently made some progress in this direction and the results will appear elsewhere.

Another interesting question concerns the distribution *P*(*s _{J}*) of the selection coefficient

*s*= (

_{J}*f*−

_{J}*f*

_{J}_{−1})/

*f*

_{J}_{−1}at the

*J*th step in the adaptive walk. As we start with zero fitness, the selection coefficient is defined for

*J*≥ 2. Our preliminary numerical results for

*P*(

*s*) are shown in Figure 8 for the first few steps in the walk and we observe that the typical selection coefficient decreases as the walk proceeds. This behavior matches qualitatively with the experimental results of Schoustra

_{J}*et al.*(2009). A theoretical analysis of the distribution

*P*(

*s*) requires the joint distribution of the fitness at step

_{J}*J*− 1 and

*J*and we hope to address this question in a future work.

## Acknowledgments

K.J. thanks J. R. David for helpful suggestions and J. Krug for comments on an earlier version of the manuscript and useful correspondence. The authors also thank L. Wahl for suggestions to improve the manuscript. K.J. thanks Kavli Institute of Theoretical Physics, Santa Barbara for hospitality and support under National Science Foundation grant PHY05-51164.

## Appendix A: Random Adaptive Walk

In this *Appendix*, we briefly review the known results for random adaptive walk in which all better mutants are chosen with equal probability (Macken and Perelson 1989; Flyvbjerg and Lautrup 1992; Kauffman 1993). The probability distribution *P _{J}*(

*f*) obeys the recursion relation

(Flyvbjerg and Lautrup 1992), where . A change of variable from the fitness *f* to the cumulative probability *q*(*f*) gives(A2)Since the walk length distribution for the random adaptive walk also obeys (17), we have(A3)which shows that *Q _{J}* is a

*universal distribution*in that it is independent of the underlying fitness distribution

*p*(

*f*). Note that for infinitely long sequences, the probability

*Q*= 0 as in the mutational landscape model. Differentiating (62) with respect to

_{J}*q*immediately gives(A4)The generating function then obeys the following

*first-order*differential equation:(A5)For the initial condition

*P*

_{0}(

*f*) = δ(

*f*), we have

*P*

_{1}(

*q*) = 1 and due to (A2), the distribution

*P*(0) = 0. Solving the above differential equation using these boundary conditions gives , where and hence the distribution

_{J}*P*(

_{J}*q*) is given by(A6)(Flyvbjerg and Lautrup 1992). Since the product

*q*(

^{L}P_{J}*q*) in (A3) peaks around

*q*= 1, using

*H*(

_{L}*q*) ≈ ln

*L*for

*q*close to unity for finite but long sequences and performing the integral in (A3), we get(A7)where . Thus the walk length distribution is a Poisson distribution (in

*J*) with mean (Flyvbjerg and Lautrup 1992).

## Appendix B: Simulation Procedure

For short sequences of length *L* ≤ 10 and uncorrelated fitnesses, a randomly chosen sequence was assigned a fitness equal to zero. Then the rest of the fitness landscape composed of 2* ^{L}* − 1 fitnesses was generated by drawing random variables independently from a common distribution

*p*(

*f*). The transition probability from the initial sequence to each of the better sequences among the

*L*nearest neighbors was calculated according to (4) and the fixed sequence at the first step in the adaptive walk was chosen. Then the transition probability from the chosen mutant sequence to its better neighbors was calculated and this process was repeated until a fitter sequence was not available.

To simulate sequences with length *L* ≥ 10^{2}, we followed an approximate procedure outlined in Orr (2002) as the total number of sequences 2* ^{L}* is prohibitively large for long sequences. Starting with zero fitness,

*L*i.i.d. random variables were generated and a higher fitness

*f*was chosen according to the transition probability (4). During the next step in the process,

*L*new i.i.d. random variables were generated and the transition probability from

*f*to a better fitness was calculated. These steps were repeated until the new set of random fitnesses did not exceed the currently fixed fitness. The block model was simulated to generate weakly correlated fitnesses by assigning independent fitnesses to each block sequence. In all the simulations, the data were collected using 10

^{6}independent realizations of the fitness landscape.

## Appendix C: Derivations for Uniformly Distributed Fitness

### Solution of Differential Equation 49

The generating function *G*_{<}(*x*, *f*) obeys the inhomogeneous second-order differential equation(C1)where we have dropped the subscript for brevity. The general solution of such differential equations is a linear combination of the general solution *G*_{H}(*x*, *f*) of the homogeneous equation obtained by setting the right-hand side equal to zero and the particular solution *G*_{P} of the inhomogeneous equation (Mathews and Walker 2004). The homogeneous solution is of the form(C2)where α_{±} are the solutions of the quadratic equation α^{2} − α − 2*x* = 0 and given by (51). The particular solution is found using the method of variation of parameters and is of the form , where the functions *u*_{±}(*f*) obey the following first-order differential equations:(C3)(C4)(Mathews and Walker 2004). On solving the above equations, we obtain(C5)Finally, using the boundary conditions in the general solution *G*_{<}(*x*, *f*) = *G*_{P}(*x*, *f*) + *G*_{H}(*x*, *f*), the desired result (Equation 52) is obtained.

### Distribution of Fixed Beneficial Mutations

The fitness distribution found using (52) and (53) is given below for the first few adaptive steps:(C6)(C7)(C8)(C9)

### Walk Length Distribution

On matching powers of *x ^{J}* on both sides in (55), we get(C10)(C11)(C12)(C13)where ℓ = ln

*L*. A general solution of

*Q*by this method does not seem possible but an approximate analytic expression for

_{J}*Q*can be obtained as explained below.

_{J}From the definition of the generating function *H*(*x*) in (55), it follows that(C14)By the residue theorem for complex variables, we have(C15)(Mathews and Walker 2004), where *z*_{0} is a pole of order *n* + 1 of the function *f*(*z*) and the contour *C* encloses the singularities of *f*(*z*). From (C14) and (C15), we can write(C16)where *K*(*z*) = ln *H*(*z*) − (*J* + 1) ln *z*. We solve this integral by the method of steepest descent, which for large *J* gives(C17)(Mathews and Walker 2004), where the prime refers to the derivative with respect to *z*. In the above equation, *z*_{s} is a solution of the equation(C18)and(C19)(C20)where the prime denotes a derivative with respect to *z*. Since α_{+} > 0, neglecting the exponentially small term in in (55), we get(C21)where . Differentiating *H*(*z*) once with respect to *z* gives(C22)Using the above expression in (C18) for large *y*, we get *y*_{s} ≈ 4*J*/ℓ and therefore(C23)On differentiating (C22) once, we have(C24)Using (C22) and (C24) in (C20), we obtain(C25)(C26)Thus we have(C27)where α* _{±}* is given by (51).

## Footnotes

*Communicating editor: L. M. Wahl*

- Received July 19, 2011.
- Accepted August 29, 2011.

- Copyright © 2011 by the Genetics Society of America