{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T23:41:44Z","timestamp":1792798904051,"version":"4.5.0"},"update-to":[{"DOI":"10.1371\/journal.pcbi.1008695","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2021,2,12]],"date-time":"2021-02-12T00:00:00Z","timestamp":1613088000000}}],"reference-count":58,"publisher":"Public Library of Science (PLoS)","issue":"2","license":[{"start":{"date-parts":[[2021,2,2]],"date-time":"2021-02-02T00:00:00Z","timestamp":1612224000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1715315"],"award-info":[{"award-number":["DMS-1715315"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000925","name":"John Templeton Foundation","doi-asserted-by":"publisher","award":["61443"],"award-info":[{"award-number":["61443"]}],"id":[{"id":"10.13039\/100000925","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["www.ploscompbiol.org"],"crossmark-restriction":false},"short-container-title":["PLoS Comput Biol"],"abstract":"<jats:p>A population\u2019s spatial structure affects the rate of genetic change and the outcome of natural selection. These effects can be modeled mathematically using the Birth-death process on graphs. Individuals occupy the vertices of a weighted graph, and reproduce into neighboring vertices based on fitness. A key quantity is the probability that a mutant type will sweep to fixation, as a function of the mutant\u2019s fitness. Graphs that increase the fixation probability of beneficial mutations, and decrease that of deleterious mutations, are said to amplify selection. However, fixation probabilities are difficult to compute for an arbitrary graph. Here we derive an expression for the fixation probability, of a weakly-selected mutation, in terms of the time for two lineages to coalesce. This expression enables weak-selection fixation probabilities to be computed, for an arbitrary weighted graph, in polynomial time. Applying this method, we explore the range of possible effects of graph structure on natural selection, genetic drift, and the balance between the two. Using exhaustive analysis of small graphs and a genetic search algorithm, we identify families of graphs with striking effects on fixation probability, and we analyze these families mathematically. Our work reveals the nuanced effects of graph structure on natural selection and neutral drift. In particular, we show how these notions depend critically on the process by which mutations arise.<\/jats:p>","DOI":"10.1371\/journal.pcbi.1008695","type":"journal-article","created":{"date-parts":[[2021,2,2]],"date-time":"2021-02-02T20:53:03Z","timestamp":1612299183000},"page":"e1008695","update-policy":"https:\/\/doi.org\/10.1371\/journal.pcbi.corrections_policy","source":"Crossref","is-referenced-by-count":38,"title":["Fixation probabilities in graph-structured populations under weak selection"],"prefix":"10.1371","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9746-7613","authenticated-orcid":true,"given":"Benjamin","family":"Allen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5874-2256","authenticated-orcid":true,"given":"Christine","family":"Sample","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Patricia","family":"Steinhagen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Julia","family":"Shapiro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthew","family":"King","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Timothy","family":"Hedspeth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Megan","family":"Goncalves","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"340","published-online":{"date-parts":[[2021,2,2]]},"reference":[{"issue":"7023","key":"pcbi.1008695.ref001","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1038\/nature03204","article-title":"Evolutionary dynamics on graphs","volume":"433","author":"E Lieberman","year":"2005","journal-title":"Nature"},{"issue":"18","key":"pcbi.1008695.ref002","doi-asserted-by":"crossref","first-page":"188104","DOI":"10.1103\/PhysRevLett.96.188104","article-title":"Evolutionary dynamics on degree-heterogeneous graphs","volume":"96","author":"T Antal","year":"2006","journal-title":"Physical Review Letters"},{"issue":"2","key":"pcbi.1008695.ref003","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/j.biosystems.2011.09.006","article-title":"A review of evolutionary graph theory with applications to game theory","volume":"107","author":"P Shakarian","year":"2012","journal-title":"Biosystems"},{"issue":"2154","key":"pcbi.1008695.ref004","doi-asserted-by":"crossref","first-page":"20120676","DOI":"10.1098\/rspa.2012.0676","article-title":"Fixation probabilities for simple digraphs","volume":"469","author":"B Voorhees","year":"2013","journal-title":"Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science"},{"key":"pcbi.1008695.ref005","doi-asserted-by":"crossref","unstructured":"Adlam B, Chatterjee K, Nowak M; The Royal Society. Amplifiers of selection. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science. 2015;471(2181):20150114.","DOI":"10.1098\/rspa.2015.0114"},{"issue":"11","key":"pcbi.1008695.ref006","doi-asserted-by":"crossref","first-page":"e1004437","DOI":"10.1371\/journal.pcbi.1004437","article-title":"Most undirected random graphs are amplifiers of selection for birth-death dynamics, but suppressors of selection for death-birth dynamics","volume":"11","author":"L Hindersin","year":"2015","journal-title":"PLOS Computational Biology"},{"issue":"7","key":"pcbi.1008695.ref007","doi-asserted-by":"crossref","first-page":"e0180549","DOI":"10.1371\/journal.pone.0180549","article-title":"Suppressors of selection","volume":"12","author":"FA Cuesta","year":"2017","journal-title":"PLOS One"},{"issue":"1","key":"pcbi.1008695.ref008","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1038\/s42003-018-0078-7","article-title":"Construction of arbitrarily strong amplifiers of natural selection using evolutionary graph theory","volume":"1","author":"A Pavlogiannis","year":"2018","journal-title":"Communications Biology"},{"issue":"11","key":"pcbi.1008695.ref009","doi-asserted-by":"crossref","first-page":"e0200670","DOI":"10.1371\/journal.pone.0200670","article-title":"Evolutionary regime transitions in structured populations","volume":"13","author":"FA Cuesta","year":"2018","journal-title":"PLOS One"},{"issue":"1","key":"pcbi.1008695.ref010","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1038\/s42003-019-0374-x","article-title":"Exploring and mapping the universe of evolutionary graphs identifies structural properties affecting fixation probability and time","volume":"2","author":"M M\u00f6ller","year":"2019","journal-title":"Communications Biology"},{"key":"pcbi.1008695.ref011","doi-asserted-by":"crossref","DOI":"10.1038\/s42003-019-0373-y","article-title":"Population structure determines the tradeoff between fixation probability and fixation time","volume":"2","author":"J Tkadlec","year":"2019","journal-title":"Communications Biology"},{"issue":"1","key":"pcbi.1008695.ref012","doi-asserted-by":"crossref","first-page":"e1007529","DOI":"10.1371\/journal.pcbi.1007529","article-title":"Transient amplifiers of selection and reducers of fixation for death-Birth updating on graphs","volume":"16","author":"B Allen","year":"2020","journal-title":"PLoS Computational Biology"},{"issue":"1","key":"pcbi.1008695.ref013","doi-asserted-by":"crossref","first-page":"e1007494","DOI":"10.1371\/journal.pcbi.1007494","article-title":"Limits on amplifiers of natural selection under death-Birth updating","volume":"16","author":"J Tkadlec","year":"2020","journal-title":"PLoS Computational Biology"},{"issue":"2","key":"pcbi.1008695.ref014","doi-asserted-by":"crossref","first-page":"e1004108","DOI":"10.1371\/journal.pcbi.1004108","article-title":"The Molecular Clock of Neutral Evolution Can Be Accelerated or Slowed by Asymmetric Spatial Structure","volume":"11","author":"B Allen","year":"2015","journal-title":"PLOS Computational Biology"},{"issue":"7","key":"pcbi.1008695.ref015","doi-asserted-by":"crossref","first-page":"e1008010","DOI":"10.1371\/journal.pcbi.1008010","article-title":"Population structure across scales facilitates coexistence and spatial heterogeneity of antibiotic-resistant infections","volume":"16","author":"MS Krieger","year":"2020","journal-title":"PLOS Computational Biology"},{"issue":"25","key":"pcbi.1008695.ref016","doi-asserted-by":"crossref","first-page":"14966","DOI":"10.1073\/pnas.2535419100","article-title":"The linear process of somatic evolution","volume":"100","author":"MA Nowak","year":"2003","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"6161","key":"pcbi.1008695.ref017","doi-asserted-by":"crossref","first-page":"995","DOI":"10.1126\/science.1243148","article-title":"Defining stem cell dynamics in models of intestinal tumor initiation","volume":"342","author":"L Vermeulen","year":"2013","journal-title":"Science"},{"issue":"1","key":"pcbi.1008695.ref018","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1186\/s13062-016-0140-7","article-title":"Should tissue structure suppress or amplify selection to minimize cancer risk?","volume":"11","author":"L Hindersin","year":"2016","journal-title":"Biology Direct"},{"issue":"4","key":"pcbi.1008695.ref019","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1111\/eva.12361","article-title":"The implications of small stem cell niche sizes and the distribution of fitness effects of new mutations in aging and tumorigenesis","volume":"9","author":"VL Cannataro","year":"2016","journal-title":"Evolutionary Applications"},{"issue":"6","key":"pcbi.1008695.ref020","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1111\/eva.12476","article-title":"The evolutionary trade-off between stem cell niche size, aging, and tumorigenesis","volume":"10","author":"VL Cannataro","year":"2017","journal-title":"Evolutionary Applications"},{"key":"pcbi.1008695.ref021","doi-asserted-by":"crossref","DOI":"10.7554\/eLife.30212","article-title":"Evolutionary dynamics of incubation periods","volume":"6","author":"B Ottino-Loffler","year":"2017","journal-title":"eLife"},{"issue":"2098","key":"pcbi.1008695.ref022","doi-asserted-by":"crossref","first-page":"2609","DOI":"10.1098\/rspa.2008.0058","article-title":"An analysis of the fixation probability of a mutant on special classes of non-directed graphs","volume":"464","author":"M Broom","year":"2008","journal-title":"Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science"},{"issue":"2165","key":"pcbi.1008695.ref023","doi-asserted-by":"crossref","first-page":"20130730","DOI":"10.1098\/rspa.2013.0730","article-title":"Martingales and fixation probabilities of evolutionary graphs","volume":"470","author":"T Monk","year":"2014","journal-title":"Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science"},{"key":"pcbi.1008695.ref024","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/j.jtbi.2015.06.029","article-title":"Fixation probabilities on superstars, revisited and revised","volume":"382","author":"A Jamieson-Lane","year":"2015","journal-title":"Journal of Theoretical Biology"},{"issue":"1","key":"pcbi.1008695.ref025","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1038\/s41598-017-00107-w","article-title":"Amplification on undirected population structures: comets beat stars","volume":"7","author":"A Pavlogiannis","year":"2017","journal-title":"Scientific Reports"},{"issue":"1","key":"pcbi.1008695.ref026","doi-asserted-by":"crossref","first-page":"012408","DOI":"10.1103\/PhysRevE.100.012408","article-title":"Fitness dependence of the fixation-time distribution for evolutionary dynamics on graphs","volume":"100","author":"D Hathcock","year":"2019","journal-title":"Physical Review E"},{"key":"pcbi.1008695.ref027","author":"M Frean","year":"2008","journal-title":"Death-birth ordering and suppression of fitness in networks"},{"issue":"4","key":"pcbi.1008695.ref028","doi-asserted-by":"crossref","first-page":"140465","DOI":"10.1098\/rsos.140465","article-title":"The duality of spatial death\u2013birth and birth\u2013death processes and limitations of the isothermal theorem","volume":"2","author":"K Kaveh","year":"2015","journal-title":"Royal Society Open Science"},{"key":"pcbi.1008695.ref029","doi-asserted-by":"crossref","unstructured":"Pattni K, Broom M, Rycht\u00e1\u0159 J, Silvers LJ; The Royal Society. Evolutionary graph theory revisited: when is an evolutionary process equivaent to the Moran process? Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science. 2015;471(2182):20150334.","DOI":"10.1098\/rspa.2015.0334"},{"key":"pcbi.1008695.ref030","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.biosystems.2015.01.007","article-title":"Fast and asymptotic computation of the fixation probability for Moran processes on graphs","volume":"129","author":"FA Cuesta","year":"2015","journal-title":"Biosystems"},{"key":"pcbi.1008695.ref031","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.biosystems.2016.08.010","article-title":"Exact numerical calculation of fixation probability and time on graphs","volume":"150","author":"L Hindersin","year":"2016","journal-title":"Biosystems"},{"key":"pcbi.1008695.ref032","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1016\/j.jtbi.2018.04.039","article-title":"Martingales and the fixation probability of high-dimensional evolutionary graphs","volume":"451","author":"T Monk","year":"2018","journal-title":"Journal of Theoretical Biology"},{"key":"pcbi.1008695.ref033","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/s00285-021-01568-4","article-title":"Fixation probabilities in evolutionary dynamics under weak selection","volume":"82","author":"A McAvoy","year":"2021","journal-title":"Journal of Mathematical Biology"},{"issue":"6983","key":"pcbi.1008695.ref034","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1038\/nature02414","article-title":"Emergence of cooperation and evolutionary stability in finite populations","volume":"428","author":"MA Nowak","year":"2004","journal-title":"Nature"},{"issue":"2","key":"pcbi.1008695.ref035","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/j.tpb.2005.08.008","article-title":"Separation of time scales, fixation probabilities and convergence to evolutionarily stable states under isolation by distance","volume":"69","author":"F Rousset","year":"2006","journal-title":"Theoretical Population Biology"},{"issue":"2","key":"pcbi.1008695.ref036","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1214\/12-AAP849","article-title":"Sharp benefit-to-cost rules for the evolution of cooperation on regular graphs","volume":"23","author":"YT Chen","year":"2013","journal-title":"The Annals of Applied Probability"},{"issue":"5","key":"pcbi.1008695.ref037","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1007\/s00285-007-0069-7","article-title":"The probability of fixation of a single mutant in an exchangeable selection model","volume":"54","author":"S Lessard","year":"2007","journal-title":"Journal of Mathematical Biology"},{"issue":"3","key":"pcbi.1008695.ref038","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0304-4149(82)90011-4","article-title":"The coalescent","volume":"13","author":"JFC Kingman","year":"1982","journal-title":"Stochastic Processes and Their Applications"},{"issue":"4","key":"pcbi.1008695.ref039","doi-asserted-by":"crossref","first-page":"1333","DOI":"10.1214\/aop\/1176991158","article-title":"Coalescing random walks and voter model consensus times on the torus in Z d","volume":"17","author":"JT Cox","year":"1989","journal-title":"Annals of Probability"},{"key":"pcbi.1008695.ref040","volume-title":"Interacting Particle Systems","author":"TM Liggett","year":"2006"},{"key":"pcbi.1008695.ref041","volume-title":"Coalescent Theory: An Introduction","author":"J Wakeley","year":"2009"},{"issue":"1-2","key":"pcbi.1008695.ref042","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s00285-012-0622-x","article-title":"Measures of success in a class of evolutionary models with fixed population size and structure","volume":"68","author":"B Allen","year":"2014","journal-title":"Journal of Mathematical Biology"},{"key":"pcbi.1008695.ref043","volume-title":"The Statistical Process of Evolutionary Theory","author":"PAP Moran","year":"1962"},{"issue":"12","key":"pcbi.1008695.ref044","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1016\/S0169-5347(00)01994-7","article-title":"Statistical methods for detecting molecular adaptation","volume":"15","author":"Z Yang","year":"2000","journal-title":"Trends in Ecology & Evolution"},{"key":"pcbi.1008695.ref045","article-title":"A mathematical formalism for natural selection with arbitrary spatial and genetic structure","author":"B Allen","year":"2018","journal-title":"Journal of Mathematical Biology"},{"key":"pcbi.1008695.ref046","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/j.jtbi.2013.09.032","article-title":"Reproductive value in graph-structured populations","volume":"340","author":"W Maciejewski","year":"2014","journal-title":"Journal of Theoretical Biology"},{"issue":"7649","key":"pcbi.1008695.ref047","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1038\/nature21723","article-title":"Evolutionary dynamics on any population structure","volume":"544","author":"B Allen","year":"2017","journal-title":"Nature"},{"key":"pcbi.1008695.ref048","unstructured":"McKay B. Graphs; [cited 18 December 2020]. Available from: http:\/\/users.cecs.anu.edu.au\/~bdm\/data\/graphs.html."},{"key":"pcbi.1008695.ref049","article-title":"Computing fixation probabilities in graph-structured populations under weak selection","author":"C Sample","year":"2020","journal-title":"Zenodo"},{"issue":"2","key":"pcbi.1008695.ref050","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1080\/09720502.2009.10700618","article-title":"Evolutionary dynamics on small-order graphs","volume":"12","author":"M Broom","year":"2009","journal-title":"Journal of Interdisciplinary Mathematics"},{"issue":"3","key":"pcbi.1008695.ref051","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1002\/rsa.3240010303","article-title":"Maximum hitting time for random walks on graphs","volume":"1","author":"G Brightwell","year":"1990","journal-title":"Random Structures and Algorithms"},{"issue":"1","key":"pcbi.1008695.ref052","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1002\/rsa.3240060106","article-title":"A tight upper bound on the cover time for random walks on graphs","volume":"6","author":"U Feige","year":"1995","journal-title":"Random Structures and Algorithms"},{"issue":"2","key":"pcbi.1008695.ref053","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<131::AID-RSA1>3.0.CO;2-3","article-title":"Lollipop graphs are extremal for commute times","volume":"16","author":"J Jonasson","year":"2000","journal-title":"Random Structures & Algorithms"},{"issue":"3","key":"pcbi.1008695.ref054","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1007\/s13235-011-0022-7","article-title":"Evolutionary games on star graphs under various updating rules","volume":"1","author":"C Hadjichrysanthou","year":"2011","journal-title":"Dynamic Games and Applications"},{"issue":"1","key":"pcbi.1008695.ref055","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF02760024","article-title":"On cliques in graphs","volume":"3","author":"JW Moon","year":"1965","journal-title":"Israel journal of Mathematics"},{"issue":"1","key":"pcbi.1008695.ref056","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1002\/jgt.3190060110","article-title":"Harmonious labelings of windmill graphs and related graphs","volume":"6","author":"DF Hsu","year":"1982","journal-title":"Journal of Graph Theory"},{"key":"pcbi.1008695.ref057","doi-asserted-by":"crossref","first-page":"2129","DOI":"10.1016\/j.physa.2017.11.131","article-title":"Fixation probability on clique-based graphs","volume":"492","author":"JO Choi","year":"2018","journal-title":"Physica A: Statistical Mechanics and its Applications"},{"issue":"1762","key":"pcbi.1008695.ref058","doi-asserted-by":"crossref","first-page":"20130211","DOI":"10.1098\/rspb.2013.0211","article-title":"The effect of population structure on the rate of evolution","volume":"280","author":"M Frean","year":"2013","journal-title":"Proceedings of the Royal Society B: Biological Sciences"}],"updated-by":[{"DOI":"10.1371\/journal.pcbi.1008695","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2021,2,12]],"date-time":"2021-02-12T00:00:00Z","timestamp":1613088000000}}],"container-title":["PLOS Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1008695","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,12]],"date-time":"2021-02-12T22:09:36Z","timestamp":1613167776000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1008695"}},"subtitle":[],"editor":[{"given":"Arne","family":"Traulsen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2021,2,2]]},"references-count":58,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,2,2]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pcbi.1008695","relation":{"new_version":[{"id-type":"doi","id":"10.1371\/journal.pcbi.1008695","asserted-by":"object"}]},"ISSN":["1553-7358"],"issn-type":[{"value":"1553-7358","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,2]]}}}