{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,28]],"date-time":"2026-10-28T00:07:13Z","timestamp":1793146033885,"version":"4.5.0"},"update-to":[{"DOI":"10.1371\/journal.pcbi.1011905","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2024,3,27]],"date-time":"2024-03-27T00:00:00Z","timestamp":1711497600000}}],"reference-count":57,"publisher":"Public Library of Science (PLoS)","issue":"3","license":[{"start":{"date-parts":[[2024,3,15]],"date-time":"2024-03-15T00:00:00Z","timestamp":1710460800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000057","name":"National Institute of General Medical Sciences","doi-asserted-by":"publisher","award":["R35GM147445"],"award-info":[{"award-number":["R35GM147445"]}],"id":[{"id":"10.13039\/100000057","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2019266"],"award-info":[{"award-number":["2019266"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["T32 EB009403"],"award-info":[{"award-number":["T32 EB009403"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["www.ploscompbiol.org"],"crossmark-restriction":false},"short-container-title":["PLoS Comput Biol"],"abstract":"<jats:p>To design population topologies that can accelerate rates of solution discovery in directed evolution problems or for evolutionary optimization applications, we must first systematically understand how population structure shapes evolutionary outcome. Using the mathematical formalism of evolutionary graph theory, recent studies have shown how to topologically build networks of population interaction that increase probabilities of fixation of beneficial mutations, at the expense, however, of longer fixation times, which can slow down rates of evolution, under elevated mutation rate. Here we find that moving beyond dyadic interactions in population graphs is fundamental to explain the trade-offs between probabilities and times to fixation of new mutants in the population. We show that higher-order motifs, and in particular three-node structures, allow the tuning of times to fixation, without changes in probabilities of fixation. This gives a near-continuous control over achieving solutions that allow for a wide range of times to fixation. We apply our algorithms and analytic results to two evolutionary optimization problems and show that the rate of solution discovery can be tuned near continuously by adjusting the higher-order topology of the population. We show that the effects of population structure on the rate of evolution critically depend on the optimization landscape and find that decelerators, with longer times to fixation of new mutants, are able to reach the optimal solutions faster than accelerators in complex solution spaces. Our results highlight that no one population topology fits all optimization applications, and we provide analytic and computational tools that allow for the design of networks suitable for each specific task.<\/jats:p>","DOI":"10.1371\/journal.pcbi.1011905","type":"journal-article","created":{"date-parts":[[2024,3,15]],"date-time":"2024-03-15T13:56:59Z","timestamp":1710511019000},"page":"e1011905","update-policy":"https:\/\/doi.org\/10.1371\/journal.pcbi.corrections_policy","source":"Crossref","is-referenced-by-count":16,"title":["Evolutionary graph theory beyond pairwise interactions: Higher-order network motifs shape times to fixation in structured populations"],"prefix":"10.1371","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5211-3328","authenticated-orcid":true,"given":"Yang Ping","family":"Kuo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4296-2326","authenticated-orcid":true,"given":"Oana","family":"Carja","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"340","published-online":{"date-parts":[[2024,3,15]]},"reference":[{"issue":"1","key":"pcbi.1011905.ref001","doi-asserted-by":"crossref","first-page":"1","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":"7023","key":"pcbi.1011905.ref002","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":"1","key":"pcbi.1011905.ref003","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/ncomms4409","article-title":"Social evolution in structured populations","volume":"5","author":"F D\u00e9barre","year":"2014","journal-title":"Nature Communications"},{"issue":"4-6","key":"pcbi.1011905.ref004","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.physrep.2007.04.004","article-title":"Evolutionary games on graphs","volume":"446","author":"G Szab\u00f3","year":"2007","journal-title":"Physics Reports"},{"key":"pcbi.1011905.ref005","article-title":"A theory of evolutionary dynamics on any complex spatial structure","author":"YP Kuo","year":"2021","journal-title":"bioRxiv"},{"key":"pcbi.1011905.ref006","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"},{"issue":"9","key":"pcbi.1011905.ref007","doi-asserted-by":"crossref","first-page":"098103","DOI":"10.1103\/PhysRevLett.98.098103","article-title":"Temporal and dimensional effects in evolutionary graph theory","volume":"98","author":"C Paley","year":"2007","journal-title":"Physical Review Letters"},{"issue":"1","key":"pcbi.1011905.ref008","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"},{"issue":"2","key":"pcbi.1011905.ref009","doi-asserted-by":"crossref","first-page":"022407","DOI":"10.1103\/PhysRevE.95.022407","article-title":"Evolutionary games on cycles with strong selection","volume":"95","author":"PM Altrock","year":"2017","journal-title":"Physical Review E"},{"issue":"4","key":"pcbi.1011905.ref010","doi-asserted-by":"crossref","first-page":"042707","DOI":"10.1103\/PhysRevE.92.042707","article-title":"Analytical calculation of average fixation time in evolutionary graphs","volume":"92","author":"M Askari","year":"2015","journal-title":"Physical Review E"},{"issue":"1762","key":"pcbi.1011905.ref011","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"},{"issue":"4","key":"pcbi.1011905.ref012","doi-asserted-by":"crossref","first-page":"042304","DOI":"10.1103\/PhysRevE.99.042304","article-title":"Fixation time in evolutionary graphs: A mean-field approach","volume":"99","author":"M Hajihashemi","year":"2019","journal-title":"Physical Review E"},{"issue":"6","key":"pcbi.1011905.ref013","doi-asserted-by":"crossref","first-page":"622","DOI":"10.1002\/bit.20066","article-title":"A new approach to random mutagenesis in vitro","volume":"86","author":"YP Lai","year":"2004","journal-title":"Biotechnology and Bioengineering"},{"issue":"4710","key":"pcbi.1011905.ref014","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1126\/science.2990046","article-title":"A general method for saturation mutagenesis of cloned DNA fragments","volume":"229","author":"RM Myers","year":"1985","journal-title":"Science"},{"issue":"12","key":"pcbi.1011905.ref015","doi-asserted-by":"crossref","first-page":"4193","DOI":"10.1073\/pnas.82.12.4193","article-title":"Mutagenic repair in Escherichia coli: products of the recA gene and of the umuD and umuC genes act at different steps in UV-induced mutagenesis","volume":"82","author":"BA Bridges","year":"1985","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"2","key":"pcbi.1011905.ref016","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BF02761755","article-title":"An efficient random mutagenesis technique using an E. coli mutator strain","volume":"7","author":"A Greener","year":"1997","journal-title":"Molecular Biotechnology"},{"key":"pcbi.1011905.ref017","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/978-1-60761-652-8_7","volume-title":"In vitro mutagenesis protocols","author":"EO McCullum","year":"2010"},{"key":"pcbi.1011905.ref018","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/1090.001.0001","volume-title":"Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence","author":"JH Holland","year":"1992"},{"issue":"1","key":"pcbi.1011905.ref019","first-page":"B1","article-title":"Handbook of evolutionary computation","volume":"97","author":"T B\u00e4ck","year":"1997","journal-title":"Release"},{"issue":"4","key":"pcbi.1011905.ref020","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1038\/nbt0496-458","article-title":"Directed evolution of a para-nitrobenzyl esterase for aqueous-organic solvents","volume":"14","author":"JC Moore","year":"1996","journal-title":"Nature Biotechnology"},{"issue":"3","key":"pcbi.1011905.ref021","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1006\/jmbi.1997.1252","article-title":"Strategies for the in vitro evolution of protein function: enzyme evolution by random recombination of improved sequences","volume":"272","author":"JC Moore","year":"1997","journal-title":"Journal of Molecular Biology"},{"issue":"1","key":"pcbi.1011905.ref022","doi-asserted-by":"crossref","first-page":"1","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"},{"issue":"1","key":"pcbi.1011905.ref023","doi-asserted-by":"crossref","first-page":"1","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":"5","key":"pcbi.1011905.ref024","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1038\/s41562-020-01024-1","article-title":"Evolutionary dynamics of higher-order interactions in social networks","volume":"5","author":"U Alvarez-Rodriguez","year":"2021","journal-title":"Nature Human Behaviour"},{"issue":"6295","key":"pcbi.1011905.ref025","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1126\/science.aad9029","article-title":"Higher-order organization of complex networks","volume":"353","author":"AR Benson","year":"2016","journal-title":"Science"},{"issue":"17","key":"pcbi.1011905.ref026","doi-asserted-by":"crossref","first-page":"178701","DOI":"10.1103\/PhysRevLett.94.178701","article-title":"Voter model on heterogeneous graphs","volume":"94","author":"V Sood","year":"2005","journal-title":"Physical Review Letters"},{"issue":"18","key":"pcbi.1011905.ref027","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":"3","key":"pcbi.1011905.ref028","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1080\/15598608.2011.10412035","article-title":"Evolutionary dynamics on graphs-the effect of graph structure and initial placement on mutant spread","volume":"5","author":"M Broom","year":"2011","journal-title":"Journal of Statistical Theory and Practice"},{"key":"pcbi.1011905.ref029","doi-asserted-by":"crossref","first-page":"5034","DOI":"10.1038\/srep05034","article-title":"Characterizing the effect of population heterogeneity on evolutionary dynamics on complex networks","volume":"4","author":"S Tan","year":"2014","journal-title":"Scientific Reports"},{"issue":"1","key":"pcbi.1011905.ref030","doi-asserted-by":"crossref","first-page":"17979","DOI":"10.1038\/s41598-021-97187-6","article-title":"Fixation probabilities in network structured meta-populations","volume":"11","author":"S Yagoobi","year":"2021","journal-title":"Scientific Reports"},{"issue":"21","key":"pcbi.1011905.ref031","doi-asserted-by":"crossref","first-page":"218102","DOI":"10.1103\/PhysRevLett.127.218102","article-title":"Toward a universal model for spatially structured populations","volume":"127","author":"L Marrec","year":"2021","journal-title":"Physical review letters"},{"issue":"200","key":"pcbi.1011905.ref032","doi-asserted-by":"crossref","first-page":"20220769","DOI":"10.1098\/rsif.2022.0769","article-title":"Categorizing update mechanisms for graph-structured metapopulations","volume":"20","author":"S Yagoobi","year":"2023","journal-title":"Journal of the Royal Society Interface"},{"issue":"11","key":"pcbi.1011905.ref033","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 Comput Biol"},{"issue":"4","key":"pcbi.1011905.ref034","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1145\/1151659.1159930","article-title":"Systematic topology analysis and generation using degree correlations","volume":"36","author":"P Mahadevan","year":"2006","journal-title":"ACM SIGCOMM Computer Communication Review"},{"issue":"20","key":"pcbi.1011905.ref035","doi-asserted-by":"crossref","first-page":"208701","DOI":"10.1103\/PhysRevLett.89.208701","article-title":"Assortative mixing in networks","volume":"89","author":"ME Newman","year":"2002","journal-title":"Physical Review Letters"},{"issue":"04","key":"pcbi.1011905.ref036","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1017\/S0963548399003867","article-title":"Generating random regular graphs quickly","volume":"8","author":"A Steger","year":"1999","journal-title":"Combinatorics, Probability and Computing"},{"key":"pcbi.1011905.ref037","doi-asserted-by":"crossref","unstructured":"Kim JH, Vu VH. Generating random regular graphs. In: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing; 2003. p. 213\u2013222.","DOI":"10.1145\/780542.780576"},{"key":"pcbi.1011905.ref038","doi-asserted-by":"crossref","DOI":"10.25080\/TCWV9851","volume-title":"Exploring network structure, dynamics, and function using NetworkX","author":"A Hagberg","year":"2008"},{"key":"pcbi.1011905.ref039","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1007\/BFb0091828","volume-title":"Combinatorial Mathematics VIII","author":"R Taylor","year":"1981"},{"issue":"6","key":"pcbi.1011905.ref040","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1063\/1.1699114","article-title":"Equation of state calculations by fast computing machines","volume":"21","author":"N Metropolis","year":"1953","journal-title":"The journal of chemical physics"},{"key":"pcbi.1011905.ref041","article-title":"The Markov Chain Simulation Method for Generating Connected Power Law Random Graphs","author":"C Gkantsidis","year":"2003","journal-title":"Alenex"},{"issue":"6","key":"pcbi.1011905.ref042","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1093\/genetics\/47.6.713","article-title":"On the probability of fixation of mutant genes in a population","volume":"47","author":"M Kimura","year":"1962","journal-title":"Genetics"},{"key":"pcbi.1011905.ref043","article-title":"An introduction to population genetics theory","author":"JF Crow","year":"1970","journal-title":"An introduction to population genetics theory"},{"issue":"7092","key":"pcbi.1011905.ref044","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1038\/nature04605","article-title":"A simple rule for the evolution of cooperation on graphs and social networks","volume":"441","author":"H Ohtsuki","year":"2006","journal-title":"Nature"},{"issue":"6","key":"pcbi.1011905.ref045","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1143\/ptp\/88.6.1035","article-title":"Statistical mechanics of population: the lattice Lotka-Volterra model","volume":"88","author":"H Matsuda","year":"1992","journal-title":"Progress of theoretical Physics"},{"issue":"54","key":"pcbi.1011905.ref046","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1098\/rsif.2010.0179","article-title":"Insights from unifying modern approximations to infections on networks","volume":"8","author":"T House","year":"2011","journal-title":"Journal of The Royal Society Interface"},{"key":"pcbi.1011905.ref047","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-21822-9","volume-title":"Mathematical population genetics: theoretical introduction","author":"WJ Ewens","year":"2004"},{"issue":"8","key":"pcbi.1011905.ref048","doi-asserted-by":"crossref","first-page":"1923","DOI":"10.1007\/s11538-006-9061-4","article-title":"Fixation of strategies for an evolutionary game in finite populations","volume":"68","author":"T Antal","year":"2006","journal-title":"Bulletin of Mathematical Biology"},{"issue":"5","key":"pcbi.1011905.ref049","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1109\/TEVC.2005.863128","article-title":"Graph-based evolutionary algorithms","volume":"10","author":"KM Bryden","year":"2006","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"pcbi.1011905.ref050","unstructured":"Baker JE. Adaptive selection methods for genetic algorithms. In: Proceedings of an International Conference on Genetic Algorithms and their applications. vol. 101. Hillsdale, New Jersey; 1985. p. 111."},{"key":"pcbi.1011905.ref051","volume-title":"Systems of Extreme Control","author":"LA Rastrigin","year":"1974"},{"issue":"1","key":"pcbi.1011905.ref052","doi-asserted-by":"crossref","first-page":"4009","DOI":"10.1038\/s41467-021-24271-w","article-title":"Fast and strong amplifiers of natural selection","volume":"12","author":"J Tkadlec","year":"2021","journal-title":"Nature Communications"},{"issue":"3","key":"pcbi.1011905.ref053","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0040-5809(70)90047-X","article-title":"Effective number of alleles in a subdivided population","volume":"1","author":"T Maruyama","year":"1970","journal-title":"Theoretical Population Biology"},{"key":"pcbi.1011905.ref054","doi-asserted-by":"crossref","first-page":"477","DOI":"10.2307\/2408196","article-title":"Fixation probabilities and fixation times in a subdivided population","author":"M Slatkin","year":"1981","journal-title":"Evolution"},{"key":"pcbi.1011905.ref055","first-page":"356","article-title":"The roles of mutation, inbreeding, crossbreeding, and selection in evolution","author":"S Wright","year":"1932","journal-title":"Proceedings of the Sixth International Congress on Genetics"},{"issue":"24","key":"pcbi.1011905.ref056","doi-asserted-by":"crossref","first-page":"7530","DOI":"10.1073\/pnas.1410631112","article-title":"A tortoise\u2013hare pattern seen in adapting structured and unstructured populations suggests a rugged fitness landscape in bacteria","volume":"112","author":"JR Nahum","year":"2015","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"pcbi.1011905.ref057","first-page":"127","article-title":"The fate of competing beneficial mutations in an asexual population","volume":"102","author":"PJ Gerrish","year":"1998","journal-title":"Genetics"}],"updated-by":[{"DOI":"10.1371\/journal.pcbi.1011905","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2024,3,27]],"date-time":"2024-03-27T00:00:00Z","timestamp":1711497600000}}],"container-title":["PLOS Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1011905","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,14]],"date-time":"2024-11-14T06:33:45Z","timestamp":1731566025000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1011905"}},"subtitle":[],"editor":[{"given":"Christian","family":"Hilbe","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2024,3,15]]},"references-count":57,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2024,3,15]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pcbi.1011905","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2021.06.26.450017","asserted-by":"object"}]},"ISSN":["1553-7358"],"issn-type":[{"value":"1553-7358","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,15]]}}}