Populations evolve by accumulating advantageous mutations. Every population has some spatial structure that can be modeled by an underlying network. The network then influences the probability that new advantageous mutations fixate. Amplifiers of selection are networks that increase the fixation probability of advantageous mutants, as compared to the unstructured fully-connected network. Whether or not a network is an amplifier depends on the choice of the random process that governs the evolutionary dynamics. Two popular choices are Moran process with Birth-death updating and Moran process with death-Birth updating. Interestingly, while some networks are amplifiers under Birth-death updating and other networks are amplifiers under death-Birth updating, so far no spatial structures have been found that function as an amplifier under both types of updating simultaneously. In this work, we identify networks that act as amplifiers of selection under both versions of the Moran process. The amplifiers are robust, modular, and increase fixation probability for any mutant fitness advantage in a range r ∈ (1, 1.2). To complement this positive result, we also prove that for certain quantities closely related to fixation probability, it is impossible to improve them simultaneously for both versions of the Moran process. Together, our results highlight how the two versions of the Moran process differ and what they have in common.

Computer Science Institute Charles University Prague Czech Republic

IST Austria Klosterneuburg Austria

See more in PubMed

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.

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

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

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

Marrec L, Lamberti I, Bitbol AF. Toward a universal model for spatially structured populations. Physical review letters. 2021;127(21):218102. doi: 10.1103/PhysRevLett.127.218102 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

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

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

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

Frean M, Rainey PB, Traulsen A. The effect of population structure on the rate of evolution. Proceedings of the Royal Society B: Biological Sciences. 2013;280(1762):20130211. doi: 10.1098/rspb.2013.0211 PubMed DOI PMC

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

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.

Clifford P, Sudbury A. A model for spatial conflict. Biometrika. 1973;60(3):581–588. doi: 10.1093/biomet/60.3.581 DOI

Komarova NL. Spatial stochastic models for cancer initiation and progression. Bulletin of mathematical biology. 2006;68:1573–1599. doi: 10.1007/s11538-005-9046-8 PubMed DOI

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

Richter H. Spectral analysis of transient amplifiers for death–birth updating constructed from regular graphs. Journal of Mathematical Biology. 2021;82(7):61. doi: 10.1007/s00285-021-01609-y PubMed DOI PMC

Antal T, Redner S, Sood V. Evolutionary dynamics on degree-heterogeneous graphs. Physical review letters. 2006;96(18):188104. doi: 10.1103/PhysRevLett.96.188104 PubMed DOI PMC

Broom M, Rychtář J. An analysis of the fixation probability of a mutant on special classes of non-directed graphs. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2008;464(2098):2609–2627. doi: 10.1098/rspa.2008.0058 DOI

Kaveh K, Komarova NL, Kohandel M. The duality of spatial death–birth and birth–death processes and limitations of the isothermal theorem. Royal Society open science. 2015;2(4):140465. doi: 10.1098/rsos.140465 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

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

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

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

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

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

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

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

Richter H. Spectral dynamics of guided edge removals and identifying transient amplifiers for death–Birth updating. Journal of Mathematical Biology. 2023;87(1):3. doi: 10.1007/s00285-023-01937-1 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

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

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

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

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

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

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

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

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.

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

Colonization times in Moran process on graphs

Fixation times on directed graphs