Skip to main content
Springer Nature Link
Log in

Evolutionary Accessibility in Tunably Rugged Fitness Landscapes

  • Published:
Journal of Statistical Physics Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig.��4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13

Similar content being viewed by others

Notes

  1. 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.

  2. For an empirical analysis of accessible pathways that includes the possibility of mutational reversions see [27].

  3. 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.

  4. The factor λ=1 or 2 depending on the population dynamic model, see [36].

  5. 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.

  6. 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.

  7. 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→∞.

  8. 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

  1. Darwin, C.: On the Origin of Species by Means of Natural Selection. Murray, London (1859)

    Google Scholar 

  2. Haldane, J.B.S.: The Causes of Evolution. Longmans, Green, London (1932)

    Google Scholar 

  3. Wright, S.: Evolution in Mendelian populations. Genetics 16, 97–159 (1931)

    Google Scholar 

  4. Fisher, R.A.: The Genetical Theory of Natural Selection. Clarendon Press, Oxford (1930)

    MATH  Google Scholar 

  5. Huxley, J.S.: Evolution: The Modern Synthesis. MIT Press, Cambridge (2010)

    Google Scholar 

  6. Stemmer, W.P.C.: Rapid evolution of a protein in vitro by DNA shuffling. Nature 370, 389–391 (1994)

    Article  ADS  Google Scholar 

  7. Weinreich, D.M., Watson, R.A., Chao, L.: Perspective: sign epistasis and genetic constraint of evolutionary trajectories. Evolution 59, 1165–1174 (2005)

    Google Scholar 

  8. 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)

    Article  ADS  Google Scholar 

  9. Carneiro, M., Hartl, D.L.: Adaptive landscapes and protein evolution. Proc. Natl. Acad. Sci. USA 107, 1747–1751 (2010)

    Article  ADS  Google Scholar 

  10. Franke, J., Klözer, A., de Visser, J.A.G.M., Krug, J.: Evolutionary accessibility of mutational pathways. PLoS Comput. Biol. 7, e1002134 (2011)

    Article  Google Scholar 

  11. 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)

    Google Scholar 

  12. Gillespie, J.H.: Population Genetics: A Concise Guide, 2nd edn. Johns Hopkins University Press, Baltimore (2004)

    Google Scholar 

  13. Blythe, R.A., McKane, A.J.: Stochastic models of evolution in genetics, ecology and linguistics. J. Stat. Mech.: Theory Exp. P07018 (2007)

  14. Park, S.-C., Simon, D., Krug, J.: The speed of evolution in large asexual populations. J. Stat. Phys. 138, 381–410 (2010)

    Article  MathSciNet  ADS  MATH  Google Scholar 

  15. Gillespie, J.H.: A simple stochastic gene substitution model. Theor. Popul. Biol. 23, 202–215 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  16. Gillespie, J.H.: The Causes of Molecular Evolution. Oxford Series in Ecology and Evolution. Oxford University Press, Oxford (2002)

    Google Scholar 

  17. Orr, H.A.: A minimum on the mean number of steps taken in adaptive walks. J. Theor. Biol. 220, 241–247 (2003)

    Article  MathSciNet  Google Scholar 

  18. Jain, K., Krug, J.: Deterministic and stochastic regimes of asexual evolution on rugged fitness landscapes. Genetics 175, 1275–1288 (2007)

    Article  Google Scholar 

  19. Jain, K., Krug, J., Park, S.-C.: Evolutionary advantage of small populations on complex fitness landscapes. Evolution 65, 1945–1955 (2011)

    Article  Google Scholar 

  20. Kauffman, S.A.: The Origins of Order: Self-organization and Selection in Evolution. Oxford University Press, Oxford (1993)

    Google Scholar 

  21. Weinberger, E.: Correlated and uncorrelated fitness landscapes and how to tell the difference. Biol. Cybern. 63, 325–336 (1990)

    Article  MATH  Google Scholar 

  22. Stadler, P.F., Happel, R.: Random field models for fitness landscapes. J. Math. Biol. 38, 435–478 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  23. 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)

    Article  Google Scholar 

  24. 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)

    Article  Google Scholar 

  25. Stadler, B.M.R., Stadler, P.F.: Combinatorial vector fields and the valley structure of fitness landscapes. J. Math. Biol. 61, 877–898 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  26. Gokhale, C.S., Iwasa, Y., Nowak, M.A., Traulsen, A.: The pace of evolution across fitness valleys. J. Theor. Biol. 259, 613–620 (2009)

    Article  MathSciNet  Google Scholar 

  27. DePristo, M.A., Hartl, D.L., Weinreich, D.M.: Mutational reversions during adaptive protein evolution. Mol. Biol. Evol. 24, 1608–1610 (2007)

    Article  Google Scholar 

  28. Stauffer, D., Aharony, A.: Introduction to Percolation Theory. Taylor & Francis, New York (1991)

    Google Scholar 

  29. Gavrilets, S., Gravner, J.: Percolation on the fitness hypercube and the evolution of reproductive isolation. J. Theor. Biol. 184, 51–64 (1997)

    Article  Google Scholar 

  30. Gavrilets, S.: Fitness Landscapes and the Origin of Species. Monographs in Population Biology. Princeton University Press, Princeton (2004)

    Google Scholar 

  31. Mézard, M., Parisi, G., Virasoro, M.A.: Spin Glass Theory and Beyond. World Scientific Publishing, Singapore (1987)

    MATH  Google Scholar 

  32. Mézard, M., Montanari, A.: Information, Physics, and Computation. Oxford University Press, Oxford (2009)

    Book  MATH  Google Scholar 

  33. Hartmann, A.K., Rieger, H.: Optimization Algorithms in Physics. Wiley-VCH, Berlin (2002)

    MATH  Google Scholar 

  34. Stein, D.L. (ed.): Spin Glasses and Biology. World Scientific, Singapore (1992)

    Google Scholar 

  35. Berg, J., Willmann, S., Lässig, M.: Adaptive evolution of transcription factor binding sites. BMC Evol. Biol. 4, 42 (2004)

    Article  Google Scholar 

  36. Sella, G., Hirsh, A.E.: The application of statistical physics to evolutionary biology. Proc. Natl. Acad. Sci. USA 102, 9541–9546 (2005)

    Article  ADS  Google Scholar 

  37. 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)

    Article  ADS  Google Scholar 

  38. 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)

    Article  ADS  Google Scholar 

  39. Tan, L., Serene, S., Chao, H.X., Gore, J.: Hidden randomness between fitness landscapes limits reverse evolution. Phys. Rev. Lett. 106, 198102 (2011)

    Article  ADS  Google Scholar 

  40. 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.

  41. Kingman, J.: A simple model for the balance between selection and mutation. J. Appl. Probab. 15, 1–12 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  42. Kauffman, S., Levin, S.: Towards a general theory of adaptive walks on rugged landscapes. J. Theor. Biol. 128, 11–45 (1987)

    Article  MathSciNet  Google Scholar 

  43. Derrida, B.: Random-energy model: limit of a family of disordered models. Phys. Rev. Lett. 45, 79–82 (1980)

    Article  MathSciNet  ADS  Google Scholar 

  44. Derrida, B.: Random-energy model: limit of a family of disordered systems. Phys. Rev. B 24, 2613–2626 (1981)

    Article  MathSciNet  ADS  Google Scholar 

  45. Miller, C.R., Joyce, P., Wichmann, H.A.: Mutational effects and population dynamics during viral adaptation challenge current models. Genetics 187, 185–202 (2011)

    Article  Google Scholar 

  46. 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)

    Article  Google Scholar 

  47. 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)

    Article  Google Scholar 

  48. 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)

    Article  Google Scholar 

  49. Fontana, W., et al.: RNA folding and combinatory landscapes. Phys. Rev. E 47, 2083–2099 (1993)

    Article  ADS  Google Scholar 

  50. Perelson, A.S., Macken, C.A.: Protein evolution on partially correlated landscapes. Proc. Natl. Acad. Sci. USA 92, 9657–9661 (1995)

    Article  ADS  MATH  Google Scholar 

  51. Welch, J.J., Waxman, D.: The nk model and population genetics. J. Theor. Biol. 234, 329–340 (2005)

    Article  MathSciNet  Google Scholar 

  52. Weinberger, E.D.: Fourier and Taylor series on fitness landscapes. Biol. Cybern. 65, 321–330 (1991)

    Article  MATH  Google Scholar 

  53. Neher, R.A., Shraiman, B.I.: Statistical genetics and evolution of quantitative traits. Rev. Mod. Phys. 83, 1283–1300 (2011)

    Article  ADS  Google Scholar 

  54. Drossel, B.: Biological evolution and statistical physics. Adv. Phys. 50, 209–295 (2001)

    Article  ADS  Google Scholar 

  55. Derrida, B., Gardner, E.: Metastable states of a spin glass chain at 0 temperature. J. Phys. (Paris) 47, 959–965 (1986)

    Article  Google Scholar 

  56. Weinberger, E.D.: Local properties of Kauffman’s N−k model: a tunably rugged energy landscape. Phys. Rev. A 44, 6399–6413 (1991)

    Article  ADS  Google Scholar 

  57. Evans, S.N., Steinsaltz, D.: Estimating some features of NK fitness landscapes. Ann. Probab. 12, 1299–1321 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  58. Durrett, R., Limic, V.: Rigorous results for the NK model. Ann. Probab. 31, 1713–1753 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  59. Limic, V., Pemantle, R.: More rigorous results on the Kauffman-Levin model of evolution. Ann. Probab. 32, 2149–2187 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  60. Østman, B., Hintze, A., Adami, C.: Impact of epistasis and pleiotropy on evolutionary adaptation. Proc. R. Soc. Lond. B 279, 247–256 (2012)

    Article  Google Scholar 

  61. Klözer, A.: NK fitness landscapes. Diploma Thesis, Universität zu Köln (2008)

  62. 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)

  63. Gross, D.J., Mézard, M.: The simplest spin glass. Nucl. Phys. B 240, 431–452 (1984)

    Article  ADS  Google Scholar 

  64. 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)

    Article  MathSciNet  ADS  Google Scholar 

  65. Ben Arous, G., Bovier, A., Černý, J.: Universality of random energy model-like ageing in mean field spin glasses. J. Stat. Mech. L04003 (2008)

Download references

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

  1. Institute for Theoretical Physics, University of Cologne, Cologne, Germany

    Jasper Franke & Joachim Krug

Authors
  1. Jasper Franke
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Joachim Krug
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Joachim Krug.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10955-012-0507-9

Keywords

Search

Navigation