Computing the rate of evolution in spatially structured populations is difficult. A key quantity is the fixation time of a single mutant with relative reproduction rate r which invades a population of residents. We say that the fixation time is "fast" if it is at most a polynomial function in terms of the population size N. Here we study fixation times of advantageous mutants (r > 1) and neutral mutants (r = 1) on directed graphs, which are those graphs that have at least some one-way connections. We obtain three main results. First, we prove that for any directed graph the fixation time is fast, provided that r is sufficiently large. Second, we construct an efficient algorithm that gives an upper bound for the fixation time for any graph and any r ≥ 1. Third, we identify a broad class of directed graphs with fast fixation times for any r ≥ 1. This class includes previously studied amplifiers of selection, such as Superstars and Metafunnels. We also show that on some graphs the fixation time is not a monotonically declining function of r; in particular, neutral fixation can occur faster than fixation for small selective advantages.

Computer Science Institute Charles University Prague Czech Republic

Department of Mathematics Harvard University Cambridge Massachusetts United States of America

Department of Organismic and Evolutionary Biology Harvard University Cambridge Massachusetts United States of America

John A Paulson School of Engineering and Applied Sciences Harvard University Cambridge Massachusetts United States of America

Zobrazit více v PubMed

Kimura M. Evolutionary rate at the molecular level. Nature. 1968;217:624–626. doi: 10.1038/217624a0 PubMed DOI

Moran PAP. Random processes in genetics. In: Mathematical proceedings of the cambridge philosophical society. vol. 54. Cambridge University Press; 1958. p. 60–71.

Ewens WJ. Mathematical population genetics: theoretical introduction. vol. 27. Springer; 2004.

Durrett R, Levin S. The importance of being discrete (and spatial). Theoretical population biology. 1994;46(3):363–394. doi: 10.1006/tpbi.1994.1032 DOI

Whitlock MC. Fixation probability and time in subdivided populations. Genetics. 2003;164(2):767–779. doi: 10.1093/genetics/164.2.767 PubMed DOI PMC

Slatkin M. Fixation probabilities and fixation times in a subdivided population. Evolution. 1981; p. 477–488. doi: 10.1111/j.1558-5646.1981.tb04911.x PubMed DOI

Bonachela JA, Pringle RM, Sheffer E, Coverdale TC, Guyton JA, Caylor KK, et al.. Termite mounds can increase the robustness of dryland ecosystems to climatic change. Science. 2015;347(6222):651–655. doi: 10.1126/science.1261487 PubMed DOI

Tilman D, May RM, Lehman CL, Nowak MA. Habitat destruction and the extinction debt. Nature. 1994;371(64926492):65–66. doi: 10.1038/371065a0 DOI

Comins HN, Hassell MP, May RM. The Spatial Dynamics of Host–Parasitoid Systems. Journal of Animal Ecology. 1992;61(3):735–748. doi: 10.2307/5627 DOI

Hassell MP, Comins HN, Mayt RM. Spatial structure and chaos in insect population dynamics. Nature. 1991;353(63416341):255–258. doi: 10.1038/353255a0 DOI

Levin SA. The Problem of Pattern and Scale in Ecology: The Robert H. MacArthur Award Lecture. Ecology. 1992;73(6):1943–1967. doi: 10.2307/1941447 DOI

Levin SA. Population Dynamic Models in Heterogeneous Environments. Annual Review of Ecology and Systematics. 1976;7(1):287–310. doi: 10.1146/annurev.es.07.110176.001443 DOI

Tilman D, Kareiva P. Spatial ecology: the role of space in population dynamics and interspecific interactions. Princeton University Press; 1997.

Barton NH. The probability of fixation of a favoured allele in a subdivided population. Genetics Research. 1993;62(2):149–157. doi: 10.1017/S0016672300031748 DOI

Fisher RA, Ford EB. The “Sewall Wright effect. Heredity. 1950;4:117–19. doi: 10.1038/hdy.1950.8 PubMed DOI

Maruyama T. Effective number of alleles in a subdivided population. Theoretical Population Biology. 1970;1(3):273–306. doi: 10.1016/0040-5809(70)90047-X PubMed DOI

Nagylaki T, Lucier B. NUMERICAL ANALYSIS OF RANDOM DRIFT IN A CLINE. Genetics. 1980;94(2):497–517. doi: 10.1093/genetics/94.2.497 PubMed DOI PMC

S W. The roles of mutation, inbreeding, crossbreeding and selection in evolution. Proceedings of the sixth international congress of Genetics. 1932;1:356–366.

Wright S. Evolution in Mendelian Populations. Genetics. 1931;16(2):97–159. doi: 10.1093/genetics/16.2.97 PubMed DOI PMC

Allen B, Lippner G, Chen YT, Fotouhi B, Momeni N, Yau ST, et al.. Evolutionary dynamics on any population structure. Nature. 2017;544(76497649):227–230. doi: 10.1038/nature21723 PubMed DOI

Hauert C, Doebeli M. Spatial structure often inhibits the evolution of cooperation in the snowdrift game. Nature. 2004;428(69836983):643–646. doi: 10.1038/nature02360 PubMed DOI

Nakamaru M, Matsuda H, Iwasa Y. The Evolution of Cooperation in a Lattice-Structured Population. Journal of Theoretical Biology. 1997;184(1):65–81. doi: 10.1006/jtbi.1996.0243 PubMed DOI

Nowak MA, May RM. Evolutionary games and spatial chaos. Nature. 1992;359(63986398):826–829. doi: 10.1038/359826a0 DOI

Ohtsuki H, Hauert C, Lieberman E, Nowak MA. A simple rule for the evolution of cooperation on graphs and social networks. Nature. 2006;441(70927092):502–505. doi: 10.1038/nature04605 PubMed DOI PMC

Grenfell BT, Bjørnstad ON, Kappey J. Travelling waves and spatial hierarchies in measles epidemics. Nature. 2001;414(68656865):716–723. doi: 10.1038/414716a PubMed DOI

Lloyd AL, May RM. Spatial Heterogeneity in Epidemic Models. Journal of Theoretical Biology. 1996;179(1):1–11. doi: 10.1006/jtbi.1996.0042 PubMed DOI

May RM, Lloyd AL. Infection dynamics on scale-free networks. Physical Review E. 2001;64(6):066112. doi: 10.1103/PhysRevE.64.066112 PubMed DOI

May RM, Nowak MA. Superinfection, Metapopulation Dynamics, and the Evolution of Diversity. Journal of Theoretical Biology. 1994;170(1):95–114. doi: 10.1006/jtbi.1994.1171 PubMed DOI

Noble R, Burri D, Le Sueur C, Lemant J, Viossat Y, Kather JN, et al.. Spatial structure governs the mode of tumour evolution. Nature Ecology & Evolution. 2022;6(22):207–217. doi: 10.1038/s41559-021-01615-9 PubMed DOI PMC

Waclaw B, Bozic I, Pittman ME, Hruban RH, Vogelstein B, Nowak MA. A spatial model predicts that dispersal and cell turnover limit intratumour heterogeneity. Nature. 2015;525(75687568):261–264. doi: 10.1038/nature14971 PubMed DOI PMC

Barton NH. The dynamics of hybrid zones. Heredity. 1979;43(33):341–359. doi: 10.1038/hdy.1979.87 DOI

Mitchell JC. Social Networks. Annual Review of Anthropology. 1974;3(1):279–299. doi: 10.1146/annurev.an.03.100174.001431 DOI

Lieberman E, Hauert C, Nowak MA. Evolutionary dynamics on graphs. Nature. 2005;433(7023):312–316. doi: 10.1038/nature03204 PubMed DOI

Díaz J, Mitsche D. A survey of the modified Moran process and evolutionary graph theory. Computer Science Review. 2021;39:100347. doi: 10.1016/j.cosrev.2020.100347 DOI

Donnelly P, Welsh D. Finite particle systems and infection models. In: Mathematical Proceedings of the Cambridge Philosophical Society. vol. 94. Cambridge University Press; 1983. p. 167–182.

Chakraborty PP, Nemzer LR, Kassen R. Experimental evidence that network topology can accelerate the spread of beneficial mutations. Evolution Letters. 2023;7(6):447–456. doi: 10.1093/evlett/qrad047 PubMed DOI PMC

Hindersin L, Traulsen A. Most undirected random graphs are amplifiers of selection for birth-death dynamics, but suppressors of selection for death-birth dynamics. PLoS computational biology. 2015;11(11):e1004437. doi: 10.1371/journal.pcbi.1004437 PubMed DOI PMC

Broom M, Hadjichrysanthou C, Rychtář J. Evolutionary games on graphs and the speed of the evolutionary process. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2010;466(2117):1327–1346. doi: 10.1098/rspa.2009.0487 DOI

Broom M, Hadjichrysanthou C, Rychtář J, Stadler B. Two results on evolutionary processes on general non-directed graphs. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2010;466(2121):2795–2798. doi: 10.1098/rspa.2010.0067 DOI

Monk T, van Schaik A. Wald’s martingale and the conditional distributions of absorption time in the Moran process. Proceedings of the Royal Society A. 2020;476(2241):20200135. doi: 10.1098/rspa.2020.0731 PubMed DOI PMC

Monk T, van Schaik A. Martingales and the characteristic functions of absorption time on bipartite graphs. Royal Society Open Science. 2021;8(10):210657. doi: 10.1098/rsos.210657 PubMed DOI PMC

Nowak MA, Michor F, Iwasa Y. The linear process of somatic evolution. Proceedings of the National Academy of Sciences. 2003;100(25):14966–14969. doi: 10.1073/pnas.2535419100 PubMed DOI PMC

Nowak MA. Evolutionary dynamics: exploring the equations of life. Harvard University Press; 2006.

Adlam B, Chatterjee K, Nowak MA. Amplifiers of selection. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2015;471(2181):20150114. doi: 10.1098/rspa.2015.0114 DOI

Hadjichrysanthou C, Broom M, Rychtár J. Evolutionary games on star graphs under various updating rules. Dynamic Games and Applications. 2011;1(3):386–407. doi: 10.1007/s13235-011-0022-7 DOI

Monk T, Green P, Paulin M. Martingales and fixation probabilities of evolutionary graphs. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2014;470(2165):20130730. doi: 10.1098/rspa.2013.0730 DOI

Chalub FA. Asymptotic expression for the fixation probability of a mutant in star graphs. arXiv preprint arXiv:14043944. 2014;.

Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak MA. Amplification on undirected population structures: comets beat stars. Scientific reports. 2017;7(1):82. doi: 10.1038/s41598-017-00107-w PubMed DOI PMC

Díaz J, Goldberg LA, Mertzios GB, Richerby D, Serna M, Spirakis PG. On the fixation probability of superstars. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2013;469(2156):20130193. doi: 10.1098/rspa.2013.0193 DOI

Jamieson-Lane A, Hauert C. Fixation probabilities on superstars, revisited and revised. Journal of Theoretical Biology. 2015;382:44–56. doi: 10.1016/j.jtbi.2015.06.029 PubMed DOI

Galanis A, Göbel A, Goldberg LA, Lapinskas J, Richerby D. Amplifiers for the Moran process. Journal of the ACM (JACM). 2017;64(1):1–90. doi: 10.1145/3019609 DOI

Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. Population structure determines the tradeoff between fixation probability and fixation time. Communications biology. 2019;2(1):138. doi: 10.1038/s42003-019-0373-y PubMed DOI PMC

Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak MA. Construction of arbitrarily strong amplifiers of natural selection using evolutionary graph theory. Communications biology. 2018;1(1):71. doi: 10.1038/s42003-018-0078-7 PubMed DOI PMC

Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. Fast and strong amplifiers of natural selection. Nature Communications. 2021;12(1):4009. doi: 10.1038/s41467-021-24271-w PubMed DOI PMC

Sharma N, Traulsen A. Suppressors of fixation can increase average fitness beyond amplifiers of selection. Proceedings of the National Academy of Sciences. 2022;119(37):e2205424119. doi: 10.1073/pnas.2205424119 PubMed DOI PMC

Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to algorithms. MIT press; 2022.

Díaz J, Goldberg LA, Mertzios GB, Richerby D, Serna M, Spirakis PG. Approximating fixation probabilities in the generalized moran process. Algorithmica. 2014;69:78–91. doi: 10.1007/s00453-012-9722-7 DOI

Goldberg LA, Lapinskas J, Richerby D. Phase transitions of the Moran process and algorithmic consequences. Random Structures & Algorithms. 2020;56(3):597–647. doi: 10.1002/rsa.20890 DOI

Díaz J, Goldberg LA, Richerby D, Serna M. Absorption time of the Moran process. Random Structures & Algorithms. 2016;49(1):137–159. doi: 10.1002/rsa.20617 DOI

Ibsen-Jensen R, Chatterjee K, Nowak MA. Computational complexity of ecological and evolutionary spatial dynamics. Proceedings of the National Academy of Sciences. 2015;112(51):15636–15641. doi: 10.1073/pnas.1511366112 PubMed DOI PMC

Altrock PM, Gokhale CS, Traulsen A. Stochastic slowdown in evolutionary processes. Physical Review E. 2010;82(1):011925. doi: 10.1103/PhysRevE.82.011925 PubMed DOI

Maciejewski W. Reproductive value in graph-structured populations. Journal of Theoretical Biology. 2014;340:285–293. doi: 10.1016/j.jtbi.2013.09.032 PubMed DOI

Durocher L, Karras P, Pavlogiannis A, Tkadlec J. Invasion dynamics in the biased voter process. In: Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence; 2022. p. 265–271.

Monk T. Martingales and the fixation probability of high-dimensional evolutionary graphs. Journal of theoretical biology. 2018;451:10–18. doi: 10.1016/j.jtbi.2018.04.039 PubMed DOI

Monk T, van Schaik A. Martingales and the fixation time of evolutionary graphs with arbitrary dimensionality. Royal Society Open Science. 2022;9(5):220011. doi: 10.1098/rsos.220011 PubMed DOI PMC

Allen B, Sample C, Jencks R, Withers J, Steinhagen P, Brizuela L, et al.. Transient amplifiers of selection and reducers of fixation for death-Birth updating on graphs. PLoS computational biology. 2020;16(1):e1007529. doi: 10.1371/journal.pcbi.1007529 PubMed DOI PMC

McKay BD, Piperno A. Practical graph isomorphism, II. Journal of symbolic computation. 2014;60:94–112. doi: 10.1016/j.jsc.2013.09.003 DOI

Möller M, Hindersin L, Traulsen A. Exploring and mapping the universe of evolutionary graphs identifies structural properties affecting fixation probability and time. Communications biology. 2019;2(1):137. doi: 10.1038/s42003-019-0374-x PubMed DOI PMC

Goldberg LA, Lapinskas J, Lengler J, Meier F, Panagiotou K, Pfister P. Asymptotically optimal amplifiers for the Moran process. Theoretical Computer Science. 2019;758:73–93. doi: 10.1016/j.tcs.2018.08.005 DOI

Downey RG, Fellows MR. Parameterized complexity. Springer Science & Business Media; 2012.

Cygan M, Fomin FV, Kowalik Ł, Lokshtanov D, Marx D, Pilipczuk M, et al.. Parameterized algorithms. vol. 4. Springer; 2015.

Levene H. Genetic equilibrium when more than one ecological niche is available. The American Naturalist. 1953;87(836):331–333. doi: 10.1086/281792 DOI

Bulmer M. Multiple niche polymorphism. The American Naturalist. 1972;106(948):254–257. doi: 10.1086/282765 DOI

Felsenstein J. The theoretical population genetics of variable selection and migration. Annual review of genetics. 1976;10(1):253–280. doi: 10.1146/annurev.ge.10.120176.001345 PubMed DOI

Yeaman S, Otto SP. Establishment and maintenance of adaptive genetic divergence under migration, selection, and drift. Evolution. 2011;65(7):2123–2129. doi: 10.1111/j.1558-5646.2011.01277.x PubMed DOI

Svoboda J, Tkadlec J, Kaveh K, Chatterjee K. Coexistence times in the Moran process with environmental heterogeneity. Proceedings of the Royal Society A. 2023;479(2271):20220685. doi: 10.1098/rspa.2022.0685 DOI

Maciejewski W, Puleo GJ. Environmental evolutionary graph theory. Journal of theoretical biology. 2014;360:117–128. doi: 10.1016/j.jtbi.2014.06.040 PubMed DOI

Kaveh K, McAvoy A, Nowak MA. Environmental fitness heterogeneity in the Moran process. Royal Society open science. 2019;6(1):181661. doi: 10.1098/rsos.181661 PubMed DOI PMC

Brendborg J, Karras P, Pavlogiannis A, Rasmussen AU, Tkadlec J. Fixation maximization in the positional moran process. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 36; 2022. p. 9304–9312.

Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. Limits on amplifiers of natural selection under death-Birth updating. PLoS computational biology. 2020;16(1):e1007494. doi: 10.1371/journal.pcbi.1007494 PubMed DOI PMC

Svoboda J, Joshi S, Tkadlec J, Chatterjee K. Amplifiers of selection for the Moran process with both Birth-death and death-Birth updating. PLOS Computational Biology. 2024;20(3):e1012008. doi: 10.1371/journal.pcbi.1012008 PubMed DOI PMC

Sood V, Antal T, Redner S. Voter models on heterogeneous networks. Physical Review E. 2008;77(4):041121. doi: 10.1103/PhysRevE.77.041121 PubMed DOI PMC

Colonization times in Moran process on graphs