Abstract
The adaptive evolution of a population under the influence of mutation and selection is strongly influenced by the structure of the underlying fitness landscape, which encodes the interactions between mutations at different genetic loci. Theoretical studies of such landscapes have been carried out for several decades, but only recently experimental fitness measurements encompassing all possible combinations of small sets of mutations have become available. The empirical studies have spawned new questions about the accessibility of optimal genotypes under natural selection. Depending on population dynamic parameters such as mutation rate and population size, evolutionary accessibility can be quantified through the statistics of accessible mutational pathways (along which fitness increases monotonically), or through the study of the basin of attraction of the optimal genotype under greedy (steepest ascent) dynamics. Here we investigate these two measures of accessibility in the framework of Kauffman’s LK-model, a paradigmatic family of random fitness landscapes with tunable ruggedness. The key parameter governing the strength of genetic interactions is the number K of interaction partners of each of the L sites in the genotype sequence. In general, accessibility increases with increasing genotype dimensionality L and decreases with increasing number of interactions K. Remarkably, however, we find that some measures of accessibility behave non-monotonically as a function of K, indicating a special role of the most sparsely connected, non-trivial cases K=1 and 2. The relation between models for fitness landscapes and spin glasses is also addressed.
Similar content being viewed by others
Notes
In the terminology of stochastic processes, this is the ‘diffusive’ term in the Fokker-Planck equation describing the probability distribution of mutant frequencies, while the term describing the deterministic behavior is usually called ‘drift’. Since in almost all that follows, only selection will be considered, this should not lead to confusion.
For an empirical analysis of accessible pathways that includes the possibility of mutational reversions see [27].
At least for the HoC and RMF models described below, it can be shown that the statistics of accessible paths to the global maximum does not depend on the choice of the starting point.
The factor λ=1 or 2 depending on the population dynamic model, see [36].
The model is generally known as the ‘NK model’. Here we follow the convention of most population genetic literature in reserving the letter N for population size and designating the number of loci by L.
Often the sum on the right hand side of (3) is scaled by L −1 or L −1/2 in order to guarantee the existence of the limit L→∞. Here only the rank ordering of fitness is of interest and the overall magnitude of F is irrelevant.
Note that, in contrast to the peaks seen in Fig. 4, the gap does not live on the scale L!, since Δn/L!→0 for L→∞.
Note that this estimate relies on uniformly sampling all local maxima. The size of a typical basin found by a greedy walk starting at a random position will be larger, because this introduces a bias towards larger basins.
References
Darwin, C.: On the Origin of Species by Means of Natural Selection. Murray, London (1859)
Haldane, J.B.S.: The Causes of Evolution. Longmans, Green, London (1932)
Wright, S.: Evolution in Mendelian populations. Genetics 16, 97–159 (1931)
Fisher, R.A.: The Genetical Theory of Natural Selection. Clarendon Press, Oxford (1930)
Huxley, J.S.: Evolution: The Modern Synthesis. MIT Press, Cambridge (2010)
Stemmer, W.P.C.: Rapid evolution of a protein in vitro by DNA shuffling. Nature 370, 389–391 (1994)
Weinreich, D.M., Watson, R.A., Chao, L.: Perspective: sign epistasis and genetic constraint of evolutionary trajectories. Evolution 59, 1165–1174 (2005)
Weinreich, D.M., Delaney, N.F., DePristo, M.A., Hartl, D.L.: Darwinian evolution can follow only very few mutational paths to fitter proteins. Science 312, 111–114 (2006)
Carneiro, M., Hartl, D.L.: Adaptive landscapes and protein evolution. Proc. Natl. Acad. Sci. USA 107, 1747–1751 (2010)
Franke, J., Klözer, A., de Visser, J.A.G.M., Krug, J.: Evolutionary accessibility of mutational pathways. PLoS Comput. Biol. 7, e1002134 (2011)
Alberts, B., Johnson, A., Lewis, J., Raff, M., Roberts, K., Walter, P.: Molecular Biology of the Cell, 5th edn. Garland Science, Taylor & Francis, New York (2008)
Gillespie, J.H.: Population Genetics: A Concise Guide, 2nd edn. Johns Hopkins University Press, Baltimore (2004)
Blythe, R.A., McKane, A.J.: Stochastic models of evolution in genetics, ecology and linguistics. J. Stat. Mech.: Theory Exp. P07018 (2007)
Park, S.-C., Simon, D., Krug, J.: The speed of evolution in large asexual populations. J. Stat. Phys. 138, 381–410 (2010)
Gillespie, J.H.: A simple stochastic gene substitution model. Theor. Popul. Biol. 23, 202–215 (1983)
Gillespie, J.H.: The Causes of Molecular Evolution. Oxford Series in Ecology and Evolution. Oxford University Press, Oxford (2002)
Orr, H.A.: A minimum on the mean number of steps taken in adaptive walks. J. Theor. Biol. 220, 241–247 (2003)
Jain, K., Krug, J.: Deterministic and stochastic regimes of asexual evolution on rugged fitness landscapes. Genetics 175, 1275–1288 (2007)
Jain, K., Krug, J., Park, S.-C.: Evolutionary advantage of small populations on complex fitness landscapes. Evolution 65, 1945–1955 (2011)
Kauffman, S.A.: The Origins of Order: Self-organization and Selection in Evolution. Oxford University Press, Oxford (1993)
Weinberger, E.: Correlated and uncorrelated fitness landscapes and how to tell the difference. Biol. Cybern. 63, 325–336 (1990)
Stadler, P.F., Happel, R.: Random field models for fitness landscapes. J. Math. Biol. 38, 435–478 (1999)
de Visser, J.A.G.M., Hoekstra, R.F., van den Enden, H.: Test of interaction between genetic markers that affect fitness in Aspergillus niger. Evolution 51, 1499–1505 (1997)
de Visser, J.A.G.M., Park, S.-C., Krug, J.: Exploring the effects of sex on empirical fitness landscapes. Am. Nat. 174, S15–S30 (2009)
Stadler, B.M.R., Stadler, P.F.: Combinatorial vector fields and the valley structure of fitness landscapes. J. Math. Biol. 61, 877–898 (2010)
Gokhale, C.S., Iwasa, Y., Nowak, M.A., Traulsen, A.: The pace of evolution across fitness valleys. J. Theor. Biol. 259, 613–620 (2009)
DePristo, M.A., Hartl, D.L., Weinreich, D.M.: Mutational reversions during adaptive protein evolution. Mol. Biol. Evol. 24, 1608–1610 (2007)
Stauffer, D., Aharony, A.: Introduction to Percolation Theory. Taylor & Francis, New York (1991)
Gavrilets, S., Gravner, J.: Percolation on the fitness hypercube and the evolution of reproductive isolation. J. Theor. Biol. 184, 51–64 (1997)
Gavrilets, S.: Fitness Landscapes and the Origin of Species. Monographs in Population Biology. Princeton University Press, Princeton (2004)
Mézard, M., Parisi, G., Virasoro, M.A.: Spin Glass Theory and Beyond. World Scientific Publishing, Singapore (1987)
Mézard, M., Montanari, A.: Information, Physics, and Computation. Oxford University Press, Oxford (2009)
Hartmann, A.K., Rieger, H.: Optimization Algorithms in Physics. Wiley-VCH, Berlin (2002)
Stein, D.L. (ed.): Spin Glasses and Biology. World Scientific, Singapore (1992)
Berg, J., Willmann, S., Lässig, M.: Adaptive evolution of transcription factor binding sites. BMC Evol. Biol. 4, 42 (2004)
Sella, G., Hirsh, A.E.: The application of statistical physics to evolutionary biology. Proc. Natl. Acad. Sci. USA 102, 9541–9546 (2005)
Chou, H.-H., Chiu, H.-C., Delaney, N.F., Segrè, D., Marx, C.J.: Diminishing returns epistasis among beneficial mutations decelerates adaptation. Science 332, 1190–1192 (2011)
Khan, A.I., Dinh, D.M., Schneider, D., Lenski, R.E., Cooper, T.F.: Negative epistasis between beneficial mutations in an evolving bacterial population. Science 332, 1193–1196 (2011)
Tan, L., Serene, S., Chao, H.X., Gore, J.: Hidden randomness between fitness landscapes limits reverse evolution. Phys. Rev. Lett. 106, 198102 (2011)
Szendro, I.G., Schenk, M.F., Franke, J., Krug, J., de Visser, J.A.G.M.: Quantitative analyses of empirical fitness landscapes. arXiv:1202.4378, to appear in J. Stat. Mech.: Theor. Exp.
Kingman, J.: A simple model for the balance between selection and mutation. J. Appl. Probab. 15, 1–12 (1978)
Kauffman, S., Levin, S.: Towards a general theory of adaptive walks on rugged landscapes. J. Theor. Biol. 128, 11–45 (1987)
Derrida, B.: Random-energy model: limit of a family of disordered models. Phys. Rev. Lett. 45, 79–82 (1980)
Derrida, B.: Random-energy model: limit of a family of disordered systems. Phys. Rev. B 24, 2613–2626 (1981)
Miller, C.R., Joyce, P., Wichmann, H.A.: Mutational effects and population dynamics during viral adaptation challenge current models. Genetics 187, 185–202 (2011)
Aita, T., et al.: Analysis of a local fitness landscape with a model of the rough Mt.-Fuji-type landscape: application to prolyl endepeptidase and thermolysin. Biopolymers 54, 64–79 (2000)
Kauffman, S.A., Weinberger, E.D.: The NK model of rugged fitness landscapes and its application to maturation of the immune response. J. Theor. Biol. 141, 211–245 (1989)
de Visser, J.A.G.M., Cooper, T.F., Elena, S.F.: The causes of epistasis. Proc. R. Soc. Lond. B 278, 3617–3624 (2011)
Fontana, W., et al.: RNA folding and combinatory landscapes. Phys. Rev. E 47, 2083–2099 (1993)
Perelson, A.S., Macken, C.A.: Protein evolution on partially correlated landscapes. Proc. Natl. Acad. Sci. USA 92, 9657–9661 (1995)
Welch, J.J., Waxman, D.: The nk model and population genetics. J. Theor. Biol. 234, 329–340 (2005)
Weinberger, E.D.: Fourier and Taylor series on fitness landscapes. Biol. Cybern. 65, 321–330 (1991)
Neher, R.A., Shraiman, B.I.: Statistical genetics and evolution of quantitative traits. Rev. Mod. Phys. 83, 1283–1300 (2011)
Drossel, B.: Biological evolution and statistical physics. Adv. Phys. 50, 209–295 (2001)
Derrida, B., Gardner, E.: Metastable states of a spin glass chain at 0 temperature. J. Phys. (Paris) 47, 959–965 (1986)
Weinberger, E.D.: Local properties of Kauffman’s N−k model: a tunably rugged energy landscape. Phys. Rev. A 44, 6399–6413 (1991)
Evans, S.N., Steinsaltz, D.: Estimating some features of NK fitness landscapes. Ann. Probab. 12, 1299–1321 (2002)
Durrett, R., Limic, V.: Rigorous results for the NK model. Ann. Probab. 31, 1713–1753 (2003)
Limic, V., Pemantle, R.: More rigorous results on the Kauffman-Levin model of evolution. Ann. Probab. 32, 2149–2187 (2004)
Østman, B., Hintze, A., Adami, C.: Impact of epistasis and pleiotropy on evolutionary adaptation. Proc. R. Soc. Lond. B 279, 247–256 (2012)
Klözer, A.: NK fitness landscapes. Diploma Thesis, Universität zu Köln (2008)
Franke, J., Wergen, G., Krug, J.: Records and sequences of records from random variables with a linear trend. J. Stat. Mech.: Theor. Exp. P10013 (2010)
Gross, D.J., Mézard, M.: The simplest spin glass. Nucl. Phys. B 240, 431–452 (1984)
Kirkpatrick, T.R., Thirumalai, D.: Dynamics of the structural glass transition and the p-spin-interaction spin-glass model. Phys. Rev. Lett. 58, 2091–2094 (1987)
Ben Arous, G., Bovier, A., Černý, J.: Universality of random energy model-like ageing in mean field spin glasses. J. Stat. Mech. L04003 (2008)
Acknowledgements
We would like to thank Johannes Berg, Anton Bovier, Bernard Derrida and Remi Monasson for useful discussions and remarks, and Alexander Klözer for his contributions in the initial stages of this project. This work was supported by DFG within SFB 680 and BCGS. JF acknowledges financial support from Studienstiftung des deutschen Volkes.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Franke, J., Krug, J. Evolutionary Accessibility in Tunably Rugged Fitness Landscapes. J Stat Phys 148, 706–723 (2012). https://doi.org/10.1007/s10955-012-0507-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10955-012-0507-9