{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,17]],"date-time":"2026-04-17T13:53:43Z","timestamp":1776434023473,"version":"3.51.2"},"update-to":[{"DOI":"10.1371\/journal.pcbi.1008402","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T00:00:00Z","timestamp":1605571200000}}],"reference-count":50,"publisher":"Public Library of Science (PLoS)","issue":"11","license":[{"start":{"date-parts":[[2020,11,5]],"date-time":"2020-11-05T00:00:00Z","timestamp":1604534400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100006754","name":"Army Research Laboratory","doi-asserted-by":"publisher","award":["W911NF-18-2-0265"],"award-info":[{"award-number":["W911NF-18-2-0265"]}],"id":[{"id":"10.13039\/100006754","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000865","name":"Bill and Melinda Gates Foundation","doi-asserted-by":"publisher","award":["OPP1148627"],"award-info":[{"award-number":["OPP1148627"]}],"id":[{"id":"10.13039\/100000865","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007065","name":"Nvidia","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007065","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["www.ploscompbiol.org"],"crossmark-restriction":false},"short-container-title":["PLoS Comput Biol"],"abstract":"<jats:p>Resources are rarely distributed uniformly within a population. Heterogeneity in the concentration of a drug, the quality of breeding sites, or wealth can all affect evolutionary dynamics. In this study, we represent a collection of properties affecting the fitness at a given location using a color. A green node is rich in resources while a red node is poorer. More colors can represent a broader spectrum of resource qualities. For a population evolving according to the birth-death Moran model, the first question we address is which structures, identified by graph connectivity and graph coloring, are evolutionarily equivalent. We prove that all properly two-colored, undirected, regular graphs are evolutionarily equivalent (where \u201cproperly colored\u201d means that no two neighbors have the same color). We then compare the effects of background heterogeneity on properly two-colored graphs to those with alternative schemes in which the colors are permuted. Finally, we discuss dynamic coloring as a model for spatiotemporal resource fluctuations, and we illustrate that random dynamic colorings often diminish the effects of background heterogeneity relative to a proper two-coloring.<\/jats:p>","DOI":"10.1371\/journal.pcbi.1008402","type":"journal-article","created":{"date-parts":[[2020,11,5]],"date-time":"2020-11-05T18:56:10Z","timestamp":1604602570000},"page":"e1008402","update-policy":"https:\/\/doi.org\/10.1371\/journal.pcbi.corrections_policy","source":"Crossref","is-referenced-by-count":8,"title":["The Moran process on 2-chromatic graphs"],"prefix":"10.1371","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8213-1797","authenticated-orcid":true,"given":"Kamran","family":"Kaveh","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9110-4635","authenticated-orcid":true,"given":"Alex","family":"McAvoy","sequence":"additional","affiliation":[]},{"given":"Krishnendu","family":"Chatterjee","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5489-0908","authenticated-orcid":true,"given":"Martin A.","family":"Nowak","sequence":"additional","affiliation":[]}],"member":"340","published-online":{"date-parts":[[2020,11,5]]},"reference":[{"key":"pcbi.1008402.ref001","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-76214-7","volume-title":"Introduction to Theoretical Population Genetics","author":"T Nagylaki","year":"1992"},{"key":"pcbi.1008402.ref002","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-78168-6","volume-title":"Probability models for DNA sequence evolution","author":"R Durrett","year":"2008"},{"key":"pcbi.1008402.ref003","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1002\/9783527628001.ch2","article-title":"Stochastic evolutionary game dynamics","volume":"2","author":"A Traulsen","year":"2009","journal-title":"Reviews of Nonlinear Dynamics and Complexity"},{"key":"pcbi.1008402.ref004","volume-title":"Game-Theoretical Models in Biology","author":"M Broom","year":"2014"},{"issue":"11","key":"pcbi.1008402.ref005","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":"7649","key":"pcbi.1008402.ref006","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"},{"issue":"1","key":"pcbi.1008402.ref007","doi-asserted-by":"crossref","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":"1","key":"pcbi.1008402.ref008","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.1008402.ref009","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":"1","key":"pcbi.1008402.ref010","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":"7023","key":"pcbi.1008402.ref011","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":"2","key":"pcbi.1008402.ref012","doi-asserted-by":"crossref","first-page":"744","DOI":"10.1016\/S0006-3495(03)74517-2","article-title":"Metabolic Switching in the Sugar Phosphotransferase System of Escherichia coli","volume":"85","author":"M Thattai","year":"2003","journal-title":"Biophysical Journal"},{"issue":"9","key":"pcbi.1008402.ref013","doi-asserted-by":"crossref","first-page":"e1004556","DOI":"10.1371\/journal.pgen.1004556","article-title":"Memory and Fitness Optimization of Bacteria under Fluctuating Environments","volume":"10","author":"L Guillaume","year":"2014","journal-title":"PLoS Genetics"},{"issue":"7568","key":"pcbi.1008402.ref014","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1038\/nature14971","article-title":"A spatial model predicts that dispersal and cell turnover limit intratumour heterogeneity","volume":"525","author":"B Waclaw","year":"2015","journal-title":"Nature"},{"issue":"6304","key":"pcbi.1008402.ref015","doi-asserted-by":"crossref","first-page":"1147","DOI":"10.1126\/science.aag0822","article-title":"Spatiotemporal microbial evolution on antibiotic landscapes","volume":"353","author":"M Baym","year":"2016","journal-title":"Science"},{"issue":"20","key":"pcbi.1008402.ref016","doi-asserted-by":"crossref","first-page":"11514","DOI":"10.1073\/pnas.95.20.11514","article-title":"Drug concentration heterogeneity facilitates the evolution of drug resistance","volume":"95","author":"TB Kepler","year":"1998","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"1","key":"pcbi.1008402.ref017","first-page":"3","article-title":"Reservoirs of HIV-1 in vivo: implications for antiretroviral therapy","volume":"5","author":"NK Saksena","year":"2003","journal-title":"AIDS Reviews"},{"issue":"9","key":"pcbi.1008402.ref018","doi-asserted-by":"crossref","first-page":"1955","DOI":"10.1093\/jac\/dkq257","article-title":"Penetration of antibiotics through Staphylococcus aureus and Staphylococcus epidermidis biofilms","volume":"65","author":"R Singh","year":"2010","journal-title":"Journal of Antimicrobial Chemotherapy"},{"issue":"27","key":"pcbi.1008402.ref019","doi-asserted-by":"crossref","first-page":"10775","DOI":"10.1073\/pnas.1117716109","article-title":"On the rapidity of antibiotic resistance evolution facilitated by a concentration gradient","volume":"109","author":"R Hermsen","year":"2012","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"8","key":"pcbi.1008402.ref020","doi-asserted-by":"crossref","first-page":"088101","DOI":"10.1103\/PhysRevLett.109.088101","article-title":"Mutational pathway determines whether drug gradients accelerate evolution of drug-resistant cells","volume":"109","author":"P Greulich","year":"2012","journal-title":"Physical Review Letters"},{"issue":"22","key":"pcbi.1008402.ref021","doi-asserted-by":"crossref","first-page":"E2874","DOI":"10.1073\/pnas.1424184112","article-title":"Imperfect drug penetration leads to spatial monotherapy and rapid evolution of multidrug resistance","volume":"112","author":"S Moreno-Gamez","year":"2015","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"40","key":"pcbi.1008402.ref022","doi-asserted-by":"crossref","first-page":"16103","DOI":"10.1073\/pnas.1314385110","article-title":"Cell motility and drug gradients in the emergence of resistance to chemotherapy","volume":"110","author":"A Wu","year":"2013","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"3","key":"pcbi.1008402.ref023","doi-asserted-by":"crossref","first-page":"e1004142","DOI":"10.1371\/journal.pcbi.1004142","article-title":"Spatial Heterogeneity in Drug Concentrations Can Facilitate the Emergence of Resistance to Cancer Therapy","volume":"11","author":"F Fu","year":"2015","journal-title":"PLOS Computational Biology"},{"issue":"836","key":"pcbi.1008402.ref024","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1086\/281792","article-title":"Genetic Equilibrium When More Than One Ecological Niche is Available","volume":"87","author":"H Levene","year":"1953","journal-title":"The American Naturalist"},{"issue":"960","key":"pcbi.1008402.ref025","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1086\/282894","article-title":"Polymorphism in Patchy Environments","volume":"108","author":"J Gillespie","year":"1974","journal-title":"The American Naturalist"},{"issue":"2","key":"pcbi.1008402.ref026","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1086\/285094","article-title":"Evolution in a Variable Environment","volume":"136","author":"SA Frank","year":"1990","journal-title":"The American Naturalist"},{"key":"pcbi.1008402.ref027","volume-title":"The Causes of Molecular Evolution","author":"JH Gillespie","year":"1991"},{"issue":"1","key":"pcbi.1008402.ref028","doi-asserted-by":"crossref","first-page":"010103","DOI":"10.1103\/PhysRevE.82.010103","article-title":"Heterogeneous voter models","volume":"82","author":"N Masuda","year":"2010","journal-title":"Physical Review E"},{"key":"pcbi.1008402.ref029","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/j.jtbi.2013.10.013","article-title":"Heterogeneity in background fitness acts as a suppressor of selection","volume":"343","author":"OP Hauser","year":"2014","journal-title":"Journal of Theoretical Biology"},{"key":"pcbi.1008402.ref030","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/j.jtbi.2014.06.040","article-title":"Environmental evolutionary graph theory","volume":"360","author":"W Maciejewski","year":"2014","journal-title":"Journal of Theoretical Biology"},{"issue":"10","key":"pcbi.1008402.ref031","doi-asserted-by":"crossref","first-page":"e0140234","DOI":"10.1371\/journal.pone.0140234","article-title":"Modeling Invasion Dynamics with Spatial Random-Fitness Due to Micro-Environment","volume":"10","author":"VSK Manem","year":"2015","journal-title":"PLoS ONE"},{"issue":"1","key":"pcbi.1008402.ref032","doi-asserted-by":"crossref","first-page":"5193","DOI":"10.1038\/s41598-017-05375-0","article-title":"Genotype by random environmental interactions gives an advantage to non-favored minor alleles","volume":"7","author":"A Mahdipour-Shirayeh","year":"2017","journal-title":"Scientific Reports"},{"issue":"11","key":"pcbi.1008402.ref033","doi-asserted-by":"crossref","first-page":"e1005864","DOI":"10.1371\/journal.pcbi.1005864","article-title":"The effect of spatial randomness on the average fixation time of mutants","volume":"13","author":"S Farhang-Sardroodi","year":"2017","journal-title":"PLoS Computational Biology"},{"issue":"11","key":"pcbi.1008402.ref034","doi-asserted-by":"crossref","first-page":"e1006559","DOI":"10.1371\/journal.pcbi.1006559","article-title":"Invasion and effective size of graph-structured populations","volume":"14","author":"S Giaimo","year":"2018","journal-title":"PLoS Computational Biology"},{"issue":"157","key":"pcbi.1008402.ref035","doi-asserted-by":"crossref","first-page":"20180781","DOI":"10.1098\/rsif.2018.0781","article-title":"Environmental spatial and temporal variability and its role in non-favoured mutant dynamics","volume":"16","author":"S Farhang-Sardroodi","year":"2019","journal-title":"Journal of The Royal Society Interface"},{"issue":"1","key":"pcbi.1008402.ref036","doi-asserted-by":"crossref","first-page":"181661","DOI":"10.1098\/rsos.181661","article-title":"Environmental fitness heterogeneity in the Moran process","volume":"6","author":"K Kaveh","year":"2019","journal-title":"Royal Society Open Science"},{"issue":"01","key":"pcbi.1008402.ref037","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1017\/S0305004100033193","article-title":"Random processes in genetics","volume":"54","author":"PAP Moran","year":"1958","journal-title":"Mathematical Proceedings of the Cambridge Philosophical Society"},{"key":"pcbi.1008402.ref038","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-9967-7","volume-title":"Graph Theory","author":"B Bollob\u00e1s","year":"1979"},{"issue":"1-2","key":"pcbi.1008402.ref039","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1556\/Select.2.2001.1-2.2","article-title":"What can Invasion Analyses Tell us about Evolution under Stochasticity in Finite Populations?","volume":"2","author":"SR Proulx","year":"2002","journal-title":"Selection"},{"issue":"4","key":"pcbi.1008402.ref040","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1016\/j.tpb.2007.08.006","article-title":"The evolution of bet-hedging adaptations to rare scenarios","volume":"72","author":"OD King","year":"2007","journal-title":"Theoretical Population Biology"},{"issue":"135","key":"pcbi.1008402.ref041","doi-asserted-by":"crossref","first-page":"20170509","DOI":"10.1098\/rsif.2017.0509","article-title":"Effects of motion in structured populations","volume":"14","author":"MS Krieger","year":"2017","journal-title":"Journal of The Royal Society Interface"},{"issue":"1","key":"pcbi.1008402.ref042","doi-asserted-by":"crossref","DOI":"10.1038\/s41598-018-22062-w","article-title":"Stirring does not make populations well mixed","volume":"8","author":"F Herrer\u00edas-Azcu\u00e9","year":"2018","journal-title":"Scientific Reports"},{"issue":"10","key":"pcbi.1008402.ref043","doi-asserted-by":"crossref","first-page":"2892","DOI":"10.1890\/0012-9658(2000)081[2892:CACOHO]2.0.CO;2","article-title":"Choices and consequences of habitat occupancy and nest site selection in Sage Sparrows","volume":"81","author":"MD Misenhelter","year":"2000","journal-title":"Ecology"},{"issue":"5-6","key":"pcbi.1008402.ref044","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1016\/j.jpubeco.2004.05.001","article-title":"The impact of school choice on student outcomes: an analysis of the Chicago Public Schools","volume":"89","author":"JB Cullen","year":"2005","journal-title":"Journal of Public Economics"},{"issue":"1","key":"pcbi.1008402.ref045","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0162-3095(84)90034-7","article-title":"The reproductive success of wealthy Americans","volume":"5","author":"SM Essock-Vitale","year":"1984","journal-title":"Ethology and Sociobiology"},{"issue":"8","key":"pcbi.1008402.ref046","doi-asserted-by":"crossref","first-page":"819","DOI":"10.1038\/s41562-020-0881-2","article-title":"Social goods dilemmas in heterogeneous societies","volume":"4","author":"A McAvoy","year":"2020","journal-title":"Nature Human Behaviour"},{"key":"pcbi.1008402.ref047","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/j.jtbi.2014.01.009","article-title":"Spatial invasion dynamics on random and unstructured meshes: Implications for heterogeneous tumor populations","volume":"349","author":"VSK Manem","year":"2014","journal-title":"Journal of Theoretical Biology"},{"issue":"2165","key":"pcbi.1008402.ref048","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.1008402.ref049","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-85823-9","volume-title":"Boolean Methods in Operations Research and Related Areas","author":"PL Hammer","year":"1968"},{"issue":"1-3","key":"pcbi.1008402.ref050","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0166-218X(01)00341-9","article-title":"Pseudo-Boolean optimization","volume":"123","author":"E Boros","year":"2002","journal-title":"Discrete Applied Mathematics"}],"updated-by":[{"DOI":"10.1371\/journal.pcbi.1008402","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T00:00:00Z","timestamp":1605571200000}}],"container-title":["PLOS Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1008402","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,11]],"date-time":"2023-10-11T15:43:37Z","timestamp":1697039017000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1008402"}},"subtitle":[],"editor":[{"given":"Mark","family":"Broom","sequence":"first","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2020,11,5]]},"references-count":50,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2020,11,5]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pcbi.1008402","relation":{"new_version":[{"id-type":"doi","id":"10.1371\/journal.pcbi.1008402","asserted-by":"object"}]},"ISSN":["1553-7358"],"issn-type":[{"value":"1553-7358","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,5]]}}}