Evolutionary accessibility in tunably rugged fitness landscapes. (English) Zbl 1257.82057
Summary: 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.
MSC:
| 82B44 | Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics |
| 82D30 | Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) |
| 92D25 | Population dynamics (general) |
| 60J20 | Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) |
| 92D10 | Genetics and epigenetics |
References:
| [1] | Darwin, C.: On the Origin of Species by Means of Natural Selection. Murray, London (1859) |
| [2] | Haldane, J.B.S.: The Causes of Evolution. Longmans, Green, London (1932) · JFM 58.0472.10 |
| [3] | Wright, S.: Evolution in Mendelian populations. Genetics 16, 97-159 (1931) |
| [4] | Fisher, R.A.: The Genetical Theory of Natural Selection. Clarendon Press, Oxford (1930) · JFM 56.1106.13 |
| [5] | Huxley, J.S.: Evolution: The Modern Synthesis. MIT Press, Cambridge (2010) |
| [6] | Stemmer, W.P.C.: Rapid evolution of a protein in vitro by DNA shuffling. Nature 370, 389-391 (1994) · doi:10.1038/370389a0 |
| [7] | Weinreich, D.M., Watson, R.A., Chao, L.: Perspective: sign epistasis and genetic constraint of evolutionary trajectories. Evolution 59, 1165-1174 (2005) |
| [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) · doi:10.1126/science.1123539 |
| [9] | Carneiro, M., Hartl, D.L.: Adaptive landscapes and protein evolution. Proc. Natl. Acad. Sci. USA 107, 1747-1751 (2010) · doi:10.1073/pnas.0906192106 |
| [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) · doi:10.1371/journal.pcbi.1002134 |
| [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) |
| [12] | Gillespie, J.H.: Population Genetics: A Concise Guide, 2nd edn. Johns Hopkins University Press, Baltimore (2004) |
| [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) · Zbl 1187.82112 · doi:10.1007/s10955-009-9915-x |
| [15] | Gillespie, J.H.: A simple stochastic gene substitution model. Theor. Popul. Biol. 23, 202-215 (1983) · Zbl 0507.92010 · doi:10.1016/0040-5809(83)90014-X |
| [16] | Gillespie, J.H.: The Causes of Molecular Evolution. Oxford Series in Ecology and Evolution. Oxford University Press, Oxford (2002) |
| [17] | Orr, H.A.: A minimum on the mean number of steps taken in adaptive walks. J. Theor. Biol. 220, 241-247 (2003) · Zbl 1464.92202 · doi:10.1006/jtbi.2003.3161 |
| [18] | Jain, K., Krug, J.: Deterministic and stochastic regimes of asexual evolution on rugged fitness landscapes. Genetics 175, 1275-1288 (2007) · doi:10.1534/genetics.106.067165 |
| [19] | Jain, K., Krug, J., Park, S.-C.: Evolutionary advantage of small populations on complex fitness landscapes. Evolution 65, 1945-1955 (2011) · doi:10.1111/j.1558-5646.2011.01280.x |
| [20] | Kauffman, S.A.: The Origins of Order: Self-organization and Selection in Evolution. Oxford University Press, Oxford (1993) |
| [21] | Weinberger, E.: Correlated and uncorrelated fitness landscapes and how to tell the difference. Biol. Cybern. 63, 325-336 (1990) · Zbl 0703.92016 · doi:10.1007/BF00202749 |
| [22] | Stadler, P.F., Happel, R.: Random field models for fitness landscapes. J. Math. Biol. 38, 435-478 (1999) · Zbl 0982.92024 · doi:10.1007/s002850050156 |
| [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) · doi:10.2307/2411202 |
| [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) · doi:10.1086/599081 |
| [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) · Zbl 1205.92057 · doi:10.1007/s00285-010-0326-z |
| [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) · Zbl 1402.92311 · doi:10.1016/j.jtbi.2009.04.011 |
| [27] | DePristo, M.A., Hartl, D.L., Weinreich, D.M.: Mutational reversions during adaptive protein evolution. Mol. Biol. Evol. 24, 1608-1610 (2007) · doi:10.1093/molbev/msm118 |
| [28] | Stauffer, D., Aharony, A.: Introduction to Percolation Theory. Taylor & Francis, New York (1991) · Zbl 0862.60092 |
| [29] | Gavrilets, S., Gravner, J.: Percolation on the fitness hypercube and the evolution of reproductive isolation. J. Theor. Biol. 184, 51-64 (1997) · doi:10.1006/jtbi.1996.0242 |
| [30] | Gavrilets, S.: Fitness Landscapes and the Origin of Species. Monographs in Population Biology. Princeton University Press, Princeton (2004) |
| [31] | Mézard, M., Parisi, G., Virasoro, M.A.: Spin Glass Theory and Beyond. World Scientific Publishing, Singapore (1987) · Zbl 0992.82500 |
| [32] | Mézard, M., Montanari, A.: Information, Physics, and Computation. Oxford University Press, Oxford (2009) · Zbl 1163.94001 · doi:10.1093/acprof:oso/9780198570837.001.0001 |
| [33] | Hartmann, A.K., Rieger, H.: Optimization Algorithms in Physics. Wiley-VCH, Berlin (2002) · Zbl 1003.82002 |
| [34] | Stein, D.L. (ed.): Spin Glasses and Biology. World Scientific, Singapore (1992) |
| [35] | Berg, J., Willmann, S., Lässig, M.: Adaptive evolution of transcription factor binding sites. BMC Evol. Biol. 4, 42 (2004) · doi:10.1186/1471-2148-4-42 |
| [36] | Sella, G., Hirsh, A.E.: The application of statistical physics to evolutionary biology. Proc. Natl. Acad. Sci. USA 102, 9541-9546 (2005) · doi:10.1073/pnas.0501865102 |
| [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) · doi:10.1126/science.1203799 |
| [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) · doi:10.1126/science.1203801 |
| [39] | Tan, L., Serene, S., Chao, H.X., Gore, J.: Hidden randomness between fitness landscapes limits reverse evolution. Phys. Rev. Lett. 106, 198102 (2011) · doi:10.1103/PhysRevLett.106.198102 |
| [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. · Zbl 1456.92101 |
| [41] | Kingman, J.: A simple model for the balance between selection and mutation. J. Appl. Probab. 15, 1-12 (1978) · Zbl 0382.92003 · doi:10.2307/3213231 |
| [42] | Kauffman, S., Levin, S.: Towards a general theory of adaptive walks on rugged landscapes. J. Theor. Biol. 128, 11-45 (1987) · doi:10.1016/S0022-5193(87)80029-2 |
| [43] | Derrida, B.: Random-energy model: limit of a family of disordered models. Phys. Rev. Lett. 45, 79-82 (1980) · doi:10.1103/PhysRevLett.45.79 |
| [44] | Derrida, B.: Random-energy model: limit of a family of disordered systems. Phys. Rev. B 24, 2613-2626 (1981) · Zbl 1323.60134 · doi:10.1103/PhysRevB.24.2613 |
| [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) · doi:10.1534/genetics.110.121400 |
| [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) · doi:10.1002/(SICI)1097-0282(200007)54:1<64::AID-BIP70>3.0.CO;2-R |
| [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) · doi:10.1016/S0022-5193(89)80019-0 |
| [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) · doi:10.1098/rspb.2011.1537 |
| [49] | Fontana, W., et al.: RNA folding and combinatory landscapes. Phys. Rev. E 47, 2083-2099 (1993) · doi:10.1103/PhysRevE.47.2083 |
| [50] | Perelson, A.S., Macken, C.A.: Protein evolution on partially correlated landscapes. Proc. Natl. Acad. Sci. USA 92, 9657-9661 (1995) · Zbl 0832.92014 · doi:10.1073/pnas.92.21.9657 |
| [51] | Welch, J.J., Waxman, D.: The nk model and population genetics. J. Theor. Biol. 234, 329-340 (2005) · Zbl 1445.92216 · doi:10.1016/j.jtbi.2004.11.027 |
| [52] | Weinberger, E.D.: Fourier and Taylor series on fitness landscapes. Biol. Cybern. 65, 321-330 (1991) · Zbl 0756.65160 · doi:10.1007/BF00216965 |
| [53] | Neher, R.A., Shraiman, B.I.: Statistical genetics and evolution of quantitative traits. Rev. Mod. Phys. 83, 1283-1300 (2011) · doi:10.1103/RevModPhys.83.1283 |
| [54] | Drossel, B.: Biological evolution and statistical physics. Adv. Phys. 50, 209-295 (2001) · doi:10.1080/00018730110041365 |
| [55] | Derrida, B., Gardner, E.: Metastable states of a spin glass chain at 0 temperature. J. Phys. (Paris) 47, 959-965 (1986) · doi:10.1051/jphys:01986004706095900 |
| [56] | Weinberger, E.D.: Local properties of Kauffman’s N−k model: a tunably rugged energy landscape. Phys. Rev. A 44, 6399-6413 (1991) · doi:10.1103/PhysRevA.44.6399 |
| [57] | Evans, S.N., Steinsaltz, D.: Estimating some features of NK fitness landscapes. Ann. Probab. 12, 1299-1321 (2002) · Zbl 1040.60043 · doi:10.1214/aoap/1037125864 |
| [58] | Durrett, R., Limic, V.: Rigorous results for the NK model. Ann. Probab. 31, 1713-1753 (2003) · Zbl 1049.60037 · doi:10.1214/aop/1068646364 |
| [59] | Limic, V., Pemantle, R.: More rigorous results on the Kauffman-Levin model of evolution. Ann. Probab. 32, 2149-2187 (2004) · Zbl 1044.92042 · doi:10.1214/009117904000000081 |
| [60] | Østman, B., Hintze, A., Adami, C.: Impact of epistasis and pleiotropy on evolutionary adaptation. Proc. R. Soc. Lond. B 279, 247-256 (2012) · doi:10.1098/rspb.2011.0870 |
| [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) · Zbl 1375.62005 |
| [63] | Gross, D.J., Mézard, M.: The simplest spin glass. Nucl. Phys. B 240, 431-452 (1984) · doi:10.1016/0550-3213(84)90237-2 |
| [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) · doi:10.1103/PhysRevLett.58.2091 |
| [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) · Zbl 1208.82024 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
