Phase transition in random adaptive walks on correlated fitness landscapes

We study biological evolution on a random fitness landscape where correlations are introduced through a linear fitness gradient of strength $c$. When selection is strong and mutations rare the dynamics is a directed uphill walk that terminates at a local fitness maximum. We analytically calculate the dependence of the walk length on the genome size $L$. When the distribution of the random fitness component has an exponential tail, we find a phase transition of the walk length $D$ between a phase at small $c$, where walks are short $(D\sim lnL)$, and a phase at large $c$, where walks are long $(D\sim L)$. For all other distributions only a single phase exists for any $c>0$. The considered process is equivalent to a zero temperature Metropolis dynamics for the random energy model in an external magnetic field, thus also providing insight into the aging dynamics of spin glasses.

Figure 1

Scaling collapse plots of ${\xi }_l{l}^{\beta /\nu }$ vs $|c-1|l^{1/\nu }$ with $\beta =1$ and $\nu =2$ for $c=0.95,0.98,0.99,1.01,1.02$, and 1.05. Horizontal line corresponds to $\psi \left(0\right)=1/\sqrt{2\pi }$ and the slanted line shows $y=x$, which confirms the scaling ansatz Eq. (13).

Figure 2

Plots of $D_{\mathrm{RAW}}$ vs $lnL$ for $f\left(x\right)=e^{-x}$ and various choices of $c$ on a double-logarithmic scale. The black line shows ${(lnL)}^2$, while the other lines correspond to $lnL/(1-c)$. (Inset) Scaling collapse plot of $D_{\text{RAW}}/{(lnL)}^2$ against $|1-c|lnL$ on a double-logarithmic scale. The straight line with slope $-1$ is drawn to show the $lnL$ behavior of $D_{\text{RAW}}$ for $c<1$.

Figure 3

Double-logarithmic plots of $D_{\mathrm{RAW}}$ vs $lnL$ for various choices of $c$ (a) for the WD with $\alpha =\frac{1}{2}$ and (b) for the GPD with $\kappa =0.5$. The case of $c=0$, which is exactly solvable, is also drawn for comparison. $D_{\text{RAW}}\sim lnL$ in the large $L$ limit, independently of $c$.

Figure 4

Double-logarithmic plots of $D_{\mathrm{RAW}}$ vs $L$ for various choices of $c$ (a) for the WD with $\alpha =2$ and (b) for the GPD with $\kappa =-1$. The line segment in (a) and the straight line in (b) show the line $y\propto x$. The case of $c=0$ which is exactly solvable is also drawn for comparison. $D_{\text{RAW}}$ increases linearly in $L$ in the large $L$ limit, independently of $c$.

Figure 5

Finite size scaling collapse plot of $D_{\text{RAW}}/{(lnL)}^2$ vs $|1-ctanh(c\left)\right|lnL$ for $c=\tilde{c}+\Delta c$ with $\Delta c=0.03$, 0.02, 0.01 (top data sets) and $-0.01,-0.02,-0.03$ (bottom data sets), where $\tilde{c}=1.199$ 678 640 is the solution of Eq. (25) with $\phi =1$.

Figure 6

Double-logarithmic plots of mean $z_l$ (symbols) and standard deviation ${\sigma }_l$ (bottom line) of the distribution $Q_l\left(x\right)$ against $l$ for a nonlinear deterministic fitness function $\Delta k_l=c{l}^{b-1}$ $\left(k_0=0\right)$, with $b=0.9$. Lines show the asymptotic power law $z_l={\left(Al\right)}^b$ with the prefactor $A$ given by the numerical solution of Eq. (34).

Figure 7

Finite size scaling collapse plot of $D_{\text{RAW}}/{(lnL)}^2$ vs $\left|\Delta c\right|lnL$ for $\Delta c=c-\frac{4}{3}$, with $\Delta c=0.03$, 0.02, 0.01 (top data sets) and $-0.01,-0.02,-0.03$ (bottom data sets). The fixation probability Eq. (35) was used with $\lambda =2$, and the distribution of the random fitness component is exponential with unit mean.

Figure 8

Comparison of $D_{\text{RAW}}$ vs $L$ for simulations with and without back steps. As can be verified, curves show excellent agreement for $lnL>10$ $\left(L>2\times {10}^5\right)$.