Moran Birth-death process is a standard stochastic process that is used to model natural selection in spatially structured populations. A newly occurring mutation that invades a population of residents can either fixate on the whole population or it can go extinct due to random drift. The duration of the process depends not only on the total population size n, but also on the spatial structure of the population. In this work, we consider the Moran process with a single type of individuals who invade and colonize an otherwise empty environment. Mathematically, this corresponds to the setting where the residents have zero reproduction rate, thus they never reproduce. The spatial structure is represented by a graph. We present two main contributions. First, in contrast to the Moran process in which residents do reproduce, we show that the colonization time is always at most a polynomial function of the population size n. Namely, we show that colonization always takes at most [Formula: see text] expected steps, and for each n, we identify the slowest graph where it takes exactly that many steps. Moreover, we establish a stronger bound of roughly [Formula: see text] steps for undirected graphs and an even stronger bound of roughly [Formula: see text] steps for so-called regular graphs. Second, we discuss various complications that one faces when attempting to measure fixation times and colonization times in spatially structured populations, and we propose to measure the real duration of the process, rather than counting the steps of the classic Moran process.

Computer Science Institute Charles University Prague Czech Republic

IST Austria Klosterneuburg Austria

See more in PubMed

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

Bürger R. The mathematical theory of selection, recombination, and mutation. Wiley; 2000.

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

Sharma N, Traulsen A. Suppressors of fixation can increase average fitness beyond amplifiers of selection. Proc Natl Acad Sci U S A 2022;119(37):e2205424119. doi: 10.1073/pnas.2205424119 PubMed DOI PMC

Durrett R, Levin S. The importance of being discrete (and spatial). Theor Popul Biol 1994;46(3):363–94. doi: 10.1006/tpbi.1994.1032 DOI

Frean M, Rainey PB, Traulsen A. The effect of population structure on the rate of evolution. Proc Biol Sci 2013;280(1762):20130211. doi: 10.1098/rspb.2013.0211 PubMed DOI PMC

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

Yagoobi S, Traulsen A. Fixation probabilities in network structured meta-populations. Sci Rep 2021;11(1):17979. doi: 10.1038/s41598-021-97187-6 PubMed DOI PMC

Yagoobi S, Sharma N, Traulsen A. Categorizing update mechanisms for graph-structured metapopulations. J R Soc Interface 2023;20(200):20220769. doi: 10.1098/rsif.2022.0769 PubMed DOI PMC

Svoboda J, Tkadlec J, Kaveh K, Chatterjee K. Coexistence times in the Moran process with environmental heterogeneity. Proc Roy Soc A. 2023:479(2271);20220685.

Svoboda J, Joshi S, Tkadlec J, Chatterjee K. Amplifiers of selection for the Moran process with both Birth-death and death-Birth updating. arXiv preprint. 2024. https://arxiv.org/abs/2401.14914 PubMed PMC

Kaveh K, Komarova NL, Kohandel M. The duality of spatial death-birth and birth-death processes and limitations of the isothermal theorem. R Soc Open Sci 2015;2(4):140465. doi: 10.1098/rsos.140465 PubMed DOI PMC

Tkadlec J, Kaveh K, Chatterjee K, Nowak MA. Evolutionary dynamics of mutants that modify population structure. J R Soc Interface 2023;20(208):20230355. doi: 10.1098/rsif.2023.0355 PubMed DOI PMC

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

KIMURA M. On the probability of fixation of mutant genes in a population. Genetics 1962;47(6):713–9. doi: 10.1093/genetics/47.6.713 PubMed DOI PMC

Kimura M. Average time until fixation of a mutant allele in a finite population under continued mutation pressure: Studies by analytical, numerical, and pseudo-sampling methods. Proc Natl Acad Sci U S A 1980;77(1):522–6. doi: 10.1073/pnas.77.1.522 PubMed DOI PMC

Slatkin M. Fixation probabilities and fixation times in a subdivided population. Evolution. n.d.;35(4):477–88. PubMed

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

Broom M, Rychtář J. An analysis of the fixation probability of a mutant on special classes of non-directed graphs. Proc R Soc A 2008;464(2098):2609–27. doi: 10.1098/rspa.2008.0058 DOI

Hadjichrysanthou C, Broom M, Rychtář J. Evolutionary games on star graphs under various updating rules. Dyn Games Appl 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. Proc R Soc A 2014;470(2165):20130730. doi: 10.1098/rspa.2013.0730 DOI

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

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

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

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

Monk T, van Schaik A. Correction to “Wald’s martingale and the conditional distributions of absorption time in the Moran process”. Proc Math Phys Eng Sci 2020;476(2242):20200731. doi: 10.1098/rspa.2020.0731 PubMed DOI PMC

Kuo YP, Carja O. Evolutionary graph theory beyond pairwise interactions: Higher-order network motifs shape times to fixation in structured populations. PLoS Comput Biol 2024;20(3):e1011905. doi: 10.1371/journal.pcbi.1011905 PubMed DOI PMC

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

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

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

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

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

Hathcock D, Strogatz SH. Fitness dependence of the fixation-time distribution for evolutionary dynamics on graphs. Phys Rev E. 2019;100(1–1):012408. doi: 10.1103/PhysRevE.100.012408 PubMed DOI

Ann Goldberg L, Lapinskas J, Richerby D. Phase transitions of the Moran process and algorithmic consequences. Random Struct Algorithms 2019;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 Struct Alg 2016;49(1):137–59. doi: 10.1002/rsa.20617 DOI

Allen B, Lippner G, Chen Y-T, Fotouhi B, Momeni N, Yau S-T, et al.. Evolutionary dynamics on any population structure. Nature 2017;544(7649):227–30. doi: 10.1038/nature21723 PubMed DOI

McAvoy A, Allen B. Fixation probabilities in evolutionary dynamics under weak selection. J Math Biol 2021;82(3):14. doi: 10.1007/s00285-021-01568-4 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–71. doi: 10.24963/ijcai.2022/38 DOI

Brendborg J, Karras P, Pavlogiannis A, Rasmussen AU, Tkadlec J. Fixation maximization in the positional Moran process. AAAI 2022;36(9):9304–12. doi: 10.1609/aaai.v36i9.21160 DOI

M Altrock P, Traulsen A. Fixation times in evolutionary games under weak selection. New J Phys 2009;11(1):013012. doi: 10.1088/1367-2630/11/1/013012 DOI

Gao S, Liu Y, Wu B. The speed of neutral evolution on graphs. J R Soc Interface 2024;21(215):20230594. doi: 10.1098/rsif.2023.0594 PubMed DOI PMC

Ibsen-Jensen R, Chatterjee K, Nowak MA. Computational complexity of ecological and evolutionary spatial dynamics. Proc Natl Acad Sci U S A 2015;112(51):15636–41. doi: 10.1073/pnas.1511366112 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 Comput Biol 2020;16(1):e1007529. doi: 10.1371/journal.pcbi.1007529 PubMed DOI PMC

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

Brewster DA, Nowak MA, Tkadlec J. Fixation times on directed graphs. PLoS Comput Biol 2024;20(7):e1012299. doi: 10.1371/journal.pcbi.1012299 PubMed DOI PMC

Komarova NL, Rodriguez-Brenes IA, Wodarz D. Laws of spatially structured population dynamics on a lattice. Physics. 2022;4(3):812–32.

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

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

Adlam B, Chatterjee K, Nowak MA. Amplifiers of selection. Proc R Soc A 2015;471(2181):20150114. doi: 10.1098/rspa.2015.0114 DOI

Hindersin L, Traulsen A. Counterintuitive properties of the fixation time in network-structured populations. J R Soc Interface 2014;11(99):20140606. doi: 10.1098/rsif.2014.0606 PubMed DOI PMC

Gillespie DT. Exact stochastic simulation of coupled chemical reactions. J Phys Chem 1977;81(25):2340–61. doi: 10.1021/j100540a008 DOI