1
|
Brewster DA, Nowak MA, Tkadlec J. Fixation times on directed graphs. PLoS Comput Biol 2024; 20:e1012299. [PMID: 39024375 PMCID: PMC11288448 DOI: 10.1371/journal.pcbi.1012299] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/12/2024] [Revised: 07/30/2024] [Accepted: 07/04/2024] [Indexed: 07/20/2024] Open
Abstract
Computing the rate of evolution in spatially structured populations is difficult. A key quantity is the fixation time of a single mutant with relative reproduction rate r which invades a population of residents. We say that the fixation time is "fast" if it is at most a polynomial function in terms of the population size N. Here we study fixation times of advantageous mutants (r > 1) and neutral mutants (r = 1) on directed graphs, which are those graphs that have at least some one-way connections. We obtain three main results. First, we prove that for any directed graph the fixation time is fast, provided that r is sufficiently large. Second, we construct an efficient algorithm that gives an upper bound for the fixation time for any graph and any r ≥ 1. Third, we identify a broad class of directed graphs with fast fixation times for any r ≥ 1. This class includes previously studied amplifiers of selection, such as Superstars and Metafunnels. We also show that on some graphs the fixation time is not a monotonically declining function of r; in particular, neutral fixation can occur faster than fixation for small selective advantages.
Collapse
Affiliation(s)
- David A. Brewster
- John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, Massachusetts, United States of America
| | - Martin A. Nowak
- Department of Mathematics, Harvard University, Cambridge, Massachusetts, United States of America
- Department of Organismic and Evolutionary Biology, Harvard University, Cambridge, Massachusetts, United States of America
| | - Josef Tkadlec
- Department of Mathematics, Harvard University, Cambridge, Massachusetts, United States of America
- Computer Science Institute, Charles University, Prague, Czech Republic
| |
Collapse
|
2
|
Kuo YP, Carja O. Evolutionary graph theory beyond single mutation dynamics: on how network-structured populations cross fitness landscapes. Genetics 2024; 227:iyae055. [PMID: 38639307 PMCID: PMC11151934 DOI: 10.1093/genetics/iyae055] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/07/2024] [Revised: 03/28/2024] [Accepted: 04/01/2024] [Indexed: 04/20/2024] Open
Abstract
Spatially resolved datasets are revolutionizing knowledge in molecular biology, yet are under-utilized for questions in evolutionary biology. To gain insight from these large-scale datasets of spatial organization, we need mathematical representations and modeling techniques that can both capture their complexity, but also allow for mathematical tractability. Evolutionary graph theory utilizes the mathematical representation of networks as a proxy for heterogeneous population structure and has started to reshape our understanding of how spatial structure can direct evolutionary dynamics. However, previous results are derived for the case of a single new mutation appearing in the population and the role of network structure in shaping fitness landscape crossing is still poorly understood. Here we study how network-structured populations cross fitness landscapes and show that even a simple extension to a two-mutational landscape can exhibit complex evolutionary dynamics that cannot be predicted using previous single-mutation results. We show how our results can be intuitively understood through the lens of how the two main evolutionary properties of a network, the amplification and acceleration factors, change the expected fate of the intermediate mutant in the population and further discuss how to link these models to spatially resolved datasets of cellular organization.
Collapse
Affiliation(s)
- Yang Ping Kuo
- Computational Biology Department, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15232, USA
| | - Oana Carja
- Computational Biology Department, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15232, USA
| |
Collapse
|
3
|
Gao S, Liu Y, Wu B. The speed of neutral evolution on graphs. J R Soc Interface 2024; 21:20230594. [PMID: 38835245 DOI: 10.1098/rsif.2023.0594] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/12/2023] [Accepted: 04/02/2024] [Indexed: 06/06/2024] Open
Abstract
The speed of evolution on structured populations is crucial for biological and social systems. The likelihood of invasion is key for evolutionary stability. But it makes little sense if it takes long. It is far from known what population structure slows down evolution. We investigate the absorption time of a single neutral mutant for all the 112 non-isomorphic undirected graphs of size 6. We find that about three-quarters of the graphs have an absorption time close to that of the complete graph, less than one-third are accelerators, and more than two-thirds are decelerators. Surprisingly, determining whether a graph has a long absorption time is too complicated to be captured by the joint degree distribution. Via the largest sojourn time, we find that echo-chamber-like graphs, which consist of two homogeneous graphs connected by few sparse links, are likely to slow down absorption. These results are robust for large graphs, mutation patterns as well as evolutionary processes. This work serves as a benchmark for timing evolution with complex interactions, and fosters the understanding of polarization in opinion formation.
Collapse
Affiliation(s)
- Shun Gao
- School of Sciences, Beijing University of Posts and Telecommunications, Beijing, People's Republic of China
| | - Yuan Liu
- School of Sciences, Beijing University of Posts and Telecommunications, Beijing, People's Republic of China
| | - Bin Wu
- School of Sciences, Beijing University of Posts and Telecommunications, Beijing, People's Republic of China
| |
Collapse
|
4
|
Kuo YP, Nombela-Arrieta C, Carja O. A theory of evolutionary dynamics on any complex population structure reveals stem cell niche architecture as a spatial suppressor of selection. Nat Commun 2024; 15:4666. [PMID: 38821923 PMCID: PMC11143212 DOI: 10.1038/s41467-024-48617-2] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/18/2023] [Accepted: 05/02/2024] [Indexed: 06/02/2024] Open
Abstract
How the spatial arrangement of a population shapes its evolutionary dynamics has been of long-standing interest in population genetics. Most previous studies assume a small number of demes or symmetrical structures that, most often, act as well-mixed populations. Other studies use network theory to study more heterogeneous spatial structures, however they usually assume small, regular networks, or strong constraints on the strength of selection considered. Here we build network generation algorithms, conduct evolutionary simulations and derive general analytic approximations for probabilities of fixation in populations with complex spatial structure. We build a unifying evolutionary theory across network families and derive the relevant selective parameter, which is a combination of network statistics, predictive of evolutionary dynamics. We also illustrate how to link this theory with novel datasets of spatial organization and use recent imaging data to build the cellular spatial networks of the stem cell niches of the bone marrow. Across a wide variety of parameters, we find these networks to be strong suppressors of selection, delaying mutation accumulation in this tissue. We also find that decreases in stem cell population size also decrease the suppression strength of the tissue spatial structure.
Collapse
Affiliation(s)
- Yang Ping Kuo
- Computational Biology Department, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA
- Joint Carnegie Mellon University-University of Pittsburgh Ph.D. Program in Computational Biology, Carnegie Mellon University, Pittsburgh, PA, USA
| | - César Nombela-Arrieta
- Department of Medical Oncology and Hematology, University and University Hospital Zurich, Zurich, Switzerland
| | - Oana Carja
- Computational Biology Department, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA.
| |
Collapse
|
5
|
Civilini A, Sadekar O, Battiston F, Gómez-Gardeñes J, Latora V. Explosive Cooperation in Social Dilemmas on Higher-Order Networks. PHYSICAL REVIEW LETTERS 2024; 132:167401. [PMID: 38701463 DOI: 10.1103/physrevlett.132.167401] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/10/2023] [Revised: 10/27/2023] [Accepted: 03/01/2024] [Indexed: 05/05/2024]
Abstract
Understanding how cooperative behaviors can emerge from competitive interactions is an open problem in biology and social sciences. While interactions are usually modeled as pairwise networks, the units of many real-world systems can also interact in groups of three or more. Here, we introduce a general framework to extend pairwise games to higher-order networks. By studying social dilemmas on hypergraphs with a tunable structure, we find an explosive transition to cooperation triggered by a critical number of higher-order games. The associated bistable regime implies that an initial critical mass of cooperators is also required for the emergence of prosocial behavior. Our results show that higher-order interactions provide a novel explanation for the survival of cooperation.
Collapse
Affiliation(s)
- Andrea Civilini
- School of Mathematical Sciences, Queen Mary University of London, London E1 4NS, United Kingdom
- Dipartimento di Fisica ed Astronomia, Università di Catania and INFN, Catania I-95123, Italy
| | - Onkar Sadekar
- Department of Network and Data Science, Central European University Vienna, Vienna 1100, Austria
| | - Federico Battiston
- Department of Network and Data Science, Central European University Vienna, Vienna 1100, Austria
| | - Jesús Gómez-Gardeñes
- Department of Condensed Matter Physics, University of Zaragoza, 50009 Zaragoza, Spain
- GOTHAM lab, Institute of Biocomputation and Physics of Complex Systems (BIFI), University of Zaragoza, 50018 Zaragoza, Spain
| | - Vito Latora
- School of Mathematical Sciences, Queen Mary University of London, London E1 4NS, United Kingdom
- Dipartimento di Fisica ed Astronomia, Università di Catania and INFN, Catania I-95123, Italy
- Complexity Science Hub Vienna, A-1080 Vienna, Austria
| |
Collapse
|
6
|
Mohamadichamgavi J, Miȩkisz J. Effect of the degree of an initial mutant in Moran processes in structured populations. Phys Rev E 2024; 109:044406. [PMID: 38755863 DOI: 10.1103/physreve.109.044406] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/23/2023] [Accepted: 03/15/2024] [Indexed: 05/18/2024]
Abstract
We study effects of the mutant's degree on the fixation probability, extinction, and fixation times in Moran processes on Erdös-Rényi and Barabási-Albert graphs. We performed stochastic simulations and used mean-field-type approximations to obtain analytical formulas. We showed that the initial placement of a mutant has a significant impact on the fixation probability and extinction time, while it has no effect on the fixation time. In both types of graphs, an increase in the degree of an initial mutant results in a decreased fixation probability and a shorter time to extinction. Our results extend previous ones to arbitrary fitness values.
Collapse
Affiliation(s)
- Javad Mohamadichamgavi
- Institute of Applied Mathematics and Mechanics, University of Warsaw, 02-097 Warsaw, Poland
| | - Jacek Miȩkisz
- Institute of Applied Mathematics and Mechanics, University of Warsaw, 02-097 Warsaw, Poland
| |
Collapse
|
7
|
Svoboda J, Joshi S, Tkadlec J, Chatterjee K. Amplifiers of selection for the Moran process with both Birth-death and death-Birth updating. PLoS Comput Biol 2024; 20:e1012008. [PMID: 38551989 PMCID: PMC11006194 DOI: 10.1371/journal.pcbi.1012008] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/17/2024] [Revised: 04/10/2024] [Accepted: 03/18/2024] [Indexed: 04/11/2024] Open
Abstract
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.
Collapse
Affiliation(s)
| | | | - Josef Tkadlec
- Computer Science Institute, Charles University, Prague, Czech Republic
| | | |
Collapse
|
8
|
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:e1011905. [PMID: 38489353 DOI: 10.1371/journal.pcbi.1011905] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/10/2023] [Revised: 03/27/2024] [Accepted: 02/12/2024] [Indexed: 03/17/2024] Open
Abstract
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.
Collapse
Affiliation(s)
- Yang Ping Kuo
- Computational Biology Department, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, United States of America
- Joint Carnegie Mellon University-University of Pittsburgh Ph.D. Program in Computational Biology, Carnegie Mellon University, Pittsburgh, Pennsylvania, United States of America
| | - Oana Carja
- Computational Biology Department, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, United States of America
| |
Collapse
|
9
|
Moawad A, Abbara A, Bitbol AF. Evolution of cooperation in deme-structured populations on graphs. Phys Rev E 2024; 109:024307. [PMID: 38491653 DOI: 10.1103/physreve.109.024307] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/18/2023] [Accepted: 12/19/2023] [Indexed: 03/18/2024]
Abstract
Understanding how cooperation can evolve in populations despite its cost to individual cooperators is an important challenge. Models of spatially structured populations with one individual per node of a graph have shown that cooperation, modeled via the prisoner's dilemma, can be favored by natural selection. These results depend on microscopic update rules, which determine how birth, death, and migration on the graph are coupled. Recently, we developed coarse-grained models of spatially structured populations on graphs, where each node comprises a well-mixed deme, and where migration is independent from division and death, thus bypassing the need for update rules. Here, we study the evolution of cooperation in these models in the rare-migration regime, within the prisoner's dilemma. We find that cooperation is not favored by natural selection in these coarse-grained models on graphs where overall deme fitness does not directly impact migration from a deme. This is due to a separation of scales, whereby cooperation occurs at a local level within demes, while spatial structure matters between demes.
Collapse
Affiliation(s)
- Alix Moawad
- Institute of Bioengineering, School of Life Sciences, École Polytechnique Fédérale de Lausanne (EPFL), CH-1015 Lausanne, Switzerland and SIB Swiss Institute of Bioinformatics, CH-1015 Lausanne, Switzerland
| | - Alia Abbara
- Institute of Bioengineering, School of Life Sciences, École Polytechnique Fédérale de Lausanne (EPFL), CH-1015 Lausanne, Switzerland and SIB Swiss Institute of Bioinformatics, CH-1015 Lausanne, Switzerland
| | - Anne-Florence Bitbol
- Institute of Bioengineering, School of Life Sciences, École Polytechnique Fédérale de Lausanne (EPFL), CH-1015 Lausanne, Switzerland and SIB Swiss Institute of Bioinformatics, CH-1015 Lausanne, Switzerland
| |
Collapse
|
10
|
Abbara A, Bitbol AF. Frequent asymmetric migrations suppress natural selection in spatially structured populations. PNAS NEXUS 2023; 2:pgad392. [PMID: 38024415 PMCID: PMC10667037 DOI: 10.1093/pnasnexus/pgad392] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 07/16/2023] [Accepted: 11/06/2023] [Indexed: 12/01/2023]
Abstract
Natural microbial populations often have complex spatial structures. This can impact their evolution, in particular the ability of mutants to take over. While mutant fixation probabilities are known to be unaffected by sufficiently symmetric structures, evolutionary graph theory has shown that some graphs can amplify or suppress natural selection, in a way that depends on microscopic update rules. We propose a model of spatially structured populations on graphs directly inspired by batch culture experiments, alternating within-deme growth on nodes and migration-dilution steps, and yielding successive bottlenecks. This setting bridges models from evolutionary graph theory with Wright-Fisher models. Using a branching process approach, we show that spatial structure with frequent migrations can only yield suppression of natural selection. More precisely, in this regime, circulation graphs, where the total incoming migration flow equals the total outgoing one in each deme, do not impact fixation probability, while all other graphs strictly suppress selection. Suppression becomes stronger as the asymmetry between incoming and outgoing migrations grows. Amplification of natural selection can nevertheless exist in a restricted regime of rare migrations and very small fitness advantages, where we recover the predictions of evolutionary graph theory for the star graph.
Collapse
Affiliation(s)
- Alia Abbara
- Institute of Bioengineering, School of Life Sciences, École Polytechnique Fédérale de Lausanne (EPFL), CH-1015 Lausanne, Switzerland
- SIB Swiss Institute of Bioinformatics, CH-1015 Lausanne, Switzerland
| | - Anne-Florence Bitbol
- Institute of Bioengineering, School of Life Sciences, École Polytechnique Fédérale de Lausanne (EPFL), CH-1015 Lausanne, Switzerland
- SIB Swiss Institute of Bioinformatics, CH-1015 Lausanne, Switzerland
| |
Collapse
|
11
|
Tkadlec J, Kaveh K, Chatterjee K, Nowak MA. Evolutionary dynamics of mutants that modify population structure. J R Soc Interface 2023; 20:20230355. [PMID: 38016637 PMCID: PMC10684346 DOI: 10.1098/rsif.2023.0355] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/23/2023] [Accepted: 11/01/2023] [Indexed: 11/30/2023] Open
Abstract
Natural selection is usually studied between mutants that differ in reproductive rate, but are subject to the same population structure. Here we explore how natural selection acts on mutants that have the same reproductive rate, but different population structures. In our framework, population structure is given by a graph that specifies where offspring can disperse. The invading mutant disperses offspring on a different graph than the resident wild-type. We find that more densely connected dispersal graphs tend to increase the invader's fixation probability, but the exact relationship between structure and fixation probability is subtle. We present three main results. First, we prove that if both invader and resident are on complete dispersal graphs, then removing a single edge in the invader's dispersal graph reduces its fixation probability. Second, we show that for certain island models higher invader's connectivity increases its fixation probability, but the magnitude of the effect depends on the exact layout of the connections. Third, we show that for lattices the effect of different connectivity is comparable to that of different fitness: for large population size, the invader's fixation probability is either constant or exponentially small, depending on whether it is more or less connected than the resident.
Collapse
Affiliation(s)
- Josef Tkadlec
- Department of Mathematics, Harvard University, Cambridge, MA 02138, USA
- Computer Science Institute, Charles University, Prague, Czech Republic
| | - Kamran Kaveh
- Department of Applied Mathematics, University of Washington, Seattle, WA 98195, USA
| | - Krishnendu Chatterjee
- Institute of Science and Technology Austria, Am Campus 1, 3400 Klosterneuburg, Austria
| | - Martin A. Nowak
- Department of Mathematics, Harvard University, Cambridge, MA 02138, USA
- Department of Organismic and Evolutionary Biology, Harvard University, Cambridge, MA 02138, USA
| |
Collapse
|
12
|
Bhaumik J, Masuda N. Fixation probability in evolutionary dynamics on switching temporal networks. J Math Biol 2023; 87:64. [PMID: 37768362 PMCID: PMC10539469 DOI: 10.1007/s00285-023-01987-5] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/03/2023] [Revised: 08/03/2023] [Accepted: 08/13/2023] [Indexed: 09/29/2023]
Abstract
Population structure has been known to substantially affect evolutionary dynamics. Networks that promote the spreading of fitter mutants are called amplifiers of selection, and those that suppress the spreading of fitter mutants are called suppressors of selection. Research in the past two decades has found various families of amplifiers while suppressors still remain somewhat elusive. It has also been discovered that most networks are amplifiers of selection under the birth-death updating combined with uniform initialization, which is a standard condition assumed widely in the literature. In the present study, we extend the birth-death processes to temporal (i.e., time-varying) networks. For the sake of tractability, we restrict ourselves to switching temporal networks, in which the network structure deterministically alternates between two static networks at constant time intervals or stochastically in a Markovian manner. We show that, in a majority of cases, switching networks are less amplifying than both of the two static networks constituting the switching networks. Furthermore, most small switching networks, i.e., networks on six nodes or less, are suppressors, which contrasts to the case of static networks.
Collapse
Affiliation(s)
- Jnanajyoti Bhaumik
- Department of Mathematics, State University of New York at Buffalo, Buffalo, NY, 14260-2900, USA
| | - Naoki Masuda
- Department of Mathematics, State University of New York at Buffalo, Buffalo, NY, 14260-2900, USA.
- Computational and Data-Enabled Science and Engineering Program, State University of New York at Buffalo, Buffalo, NY, 14260-5030, USA.
- Center for Computational Social Science, Kobe University, Kobe, 657-8501, Japan.
| |
Collapse
|
13
|
Pattni K, Ali W, Broom M, Sharkey KJ. Eco-evolutionary dynamics in finite network-structured populations with migration. J Theor Biol 2023; 572:111587. [PMID: 37517517 DOI: 10.1016/j.jtbi.2023.111587] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/10/2023] [Revised: 07/06/2023] [Accepted: 07/20/2023] [Indexed: 08/01/2023]
Abstract
We consider the effect of network structure on the evolution of a population. Models of this kind typically consider a population of fixed size and distribution. Here we consider eco-evolutionary dynamics where population size and distribution can change through birth, death and migration, all of which are separate processes. This allows complex interaction and migration behaviours that are dependent on competition. For migration, we assume that the response of individuals to competition is governed by tolerance to their group members, such that less tolerant individuals are more likely to move away due to competition. We look at the success of a mutant in the rare mutation limit for the complete, cycle and star networks. Unlike models with fixed population size and distribution, the distribution of the individuals per site is explicitly modelled by considering the dynamics of the population. This in turn determines the mutant appearance distribution for each network. Where a mutant appears impacts its success as it determines the competition it faces. For low and high migration rates the complete and cycle networks have similar mutant appearance distributions resulting in similar success levels for an invading mutant. A higher migration rate in the star network is detrimental for mutant success because migration results in a crowded central site where a mutant is more likely to appear.
Collapse
Affiliation(s)
- Karan Pattni
- Department of Mathematical Sciences, University of Liverpool, United Kingdom.
| | - Wajid Ali
- Department of Mathematical Sciences, University of Liverpool, United Kingdom
| | - Mark Broom
- Department of Mathematics, City, University of London, United Kingdom
| | - Kieran J Sharkey
- Department of Mathematical Sciences, University of Liverpool, United Kingdom
| |
Collapse
|
14
|
Sharma N, Yagoobi S, Traulsen A. Self-loops in evolutionary graph theory: Friends or foes? PLoS Comput Biol 2023; 19:e1011387. [PMID: 37656739 PMCID: PMC10501642 DOI: 10.1371/journal.pcbi.1011387] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/27/2023] [Revised: 09/14/2023] [Accepted: 07/25/2023] [Indexed: 09/03/2023] Open
Abstract
Evolutionary dynamics in spatially structured populations has been studied for a long time. More recently, the focus has been to construct structures that amplify selection by fixing beneficial mutations with higher probability than the well-mixed population and lower probability of fixation for deleterious mutations. It has been shown that for a structure to substantially amplify selection, self-loops are necessary when mutants appear predominately in nodes that change often. As a result, for low mutation rates, self-looped amplifiers attain higher steady-state average fitness in the mutation-selection balance than well-mixed populations. But what happens when the mutation rate increases such that fixation probabilities alone no longer describe the dynamics? We show that self-loops effects are detrimental outside the low mutation rate regime. In the intermediate and high mutation rate regime, amplifiers of selection attain lower steady-state average fitness than the complete graph and suppressors of selection. We also provide an estimate of the mutation rate beyond which the mutation-selection dynamics on a graph deviates from the weak mutation rate approximation. It involves computing average fixation time scaling with respect to the population sizes for several graphs.
Collapse
Affiliation(s)
- Nikhil Sharma
- Department of Theoretical Biology, Max Planck Institute for Evolutionary Biology, Plön, Germany
| | - Sedigheh Yagoobi
- Department of Theoretical Biology, Max Planck Institute for Evolutionary Biology, Plön, Germany
| | - Arne Traulsen
- Department of Theoretical Biology, Max Planck Institute for Evolutionary Biology, Plön, Germany
| |
Collapse
|
15
|
Liu R, Masuda N. Fixation dynamics on hypergraphs. PLoS Comput Biol 2023; 19:e1011494. [PMID: 37751462 PMCID: PMC10558078 DOI: 10.1371/journal.pcbi.1011494] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/16/2023] [Revised: 10/06/2023] [Accepted: 09/05/2023] [Indexed: 09/28/2023] Open
Abstract
Hypergraphs have been a useful tool for analyzing population dynamics such as opinion formation and the public goods game occurring in overlapping groups of individuals. In the present study, we propose and analyze evolutionary dynamics on hypergraphs, in which each node takes one of the two types of different but constant fitness values. For the corresponding dynamics on conventional networks, under the birth-death process and uniform initial conditions, most networks are known to be amplifiers of natural selection; amplifiers by definition enhance the difference in the strength of the two competing types in terms of the probability that the mutant type fixates in the population. In contrast, we provide strong computational evidence that a majority of hypergraphs are suppressors of selection under the same conditions by combining theoretical and numerical analyses. We also show that this suppressing effect is not explained by one-mode projection, which is a standard method for expressing hypergraph data as a conventional network. Our results suggest that the modeling framework for structured populations in addition to the specific network structure is an important determinant of evolutionary dynamics, paving a way to studying fixation dynamics on higher-order networks including hypergraphs.
Collapse
Affiliation(s)
- Ruodan Liu
- Department of Mathematics, State University of New York at Buffalo, Buffalo, New York, United States of America
| | - Naoki Masuda
- Department of Mathematics, State University of New York at Buffalo, Buffalo, New York, United States of America
- Computational and Data-Enabled Sciences and Engineering Program, State University of New York at Buffalo, Buffalo, New York, United States of America
| |
Collapse
|
16
|
Richter H. Spectral dynamics of guided edge removals and identifying transient amplifiers for death-Birth updating. J Math Biol 2023; 87:3. [PMID: 37284903 DOI: 10.1007/s00285-023-01937-1] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/05/2022] [Revised: 01/03/2023] [Accepted: 05/19/2023] [Indexed: 06/08/2023]
Abstract
The paper deals with two interrelated topics: (1) identifying transient amplifiers in an iterative process, and (2) analyzing the process by its spectral dynamics, which is the change in the graph spectra by edge manipulation. Transient amplifiers are networks representing population structures which shift the balance between natural selection and random drift. Thus, amplifiers are highly relevant for understanding the relationships between spatial structures and evolutionary dynamics. We study an iterative procedure to identify transient amplifiers for death-Birth updating. The algorithm starts with a regular input graph and iteratively removes edges until desired structures are achieved. Thus, a sequence of candidate graphs is obtained. The edge removals are guided by quantities derived from the sequence of candidate graphs. Moreover, we are interested in the Laplacian spectra of the candidate graphs and analyze the iterative process by its spectral dynamics. The results show that although transient amplifiers for death-Birth updating are generally rare, a substantial number of them can be obtained by the proposed procedure. The graphs identified share structural properties and have some similarity to dumbbell and barbell graphs. We analyze amplification properties of these graphs and also two more families of bell-like graphs and show that further transient amplifiers for death-Birth updating can be found. Finally, it is demonstrated that the spectral dynamics possesses characteristic features useful for deducing links between structural and spectral properties. These feature can also be taken for distinguishing transient amplifiers among evolutionary graphs in general.
Collapse
Affiliation(s)
- Hendrik Richter
- Faculty of Engineering, HTWK Leipzig University of Applied Sciences, Leipzig, Germany.
| |
Collapse
|
17
|
Nemati H, Kaveh K, Ejtehadi MR. Counterintuitive properties of evolutionary measures: A stochastic process study in cyclic population structures with periodic environments. J Theor Biol 2023; 564:111436. [PMID: 36828246 DOI: 10.1016/j.jtbi.2023.111436] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/02/2022] [Revised: 01/26/2023] [Accepted: 02/05/2023] [Indexed: 02/24/2023]
Abstract
Local environmental interactions are a major factor in determining the success of a new mutant in structured populations. Spatial variations in the concentration of genotype-specific resources change the fitness of competing strategies locally and thus can drastically change the outcome of evolutionary processes in unintuitive ways. The question is how such local environmental variations in network population structures change the condition for selection and fixation probability of an advantageous (or deleterious) mutant. We consider linear graph structures and focus on the case where resources have a spatial periodic pattern. This is the simplest model with two parameters, length scale and fitness scales, representing heterogeneity. We calculate fixation probability and fixation times for a constant population birth-death process as fitness heterogeneity and period vary. Fixation probability is affected by not only the level of fitness heterogeneity but also spatial scale of resources variations set by period of distribution T. We identify conditions for which a previously a deleterious mutant (in a uniform environment) becomes beneficial as fitness heterogeneity is increased. We observe cases where the fixation probability of both mutant and resident types are more than their neutral value, 1/N, simultaneously. This coincides with exponential increase in time to fixation which points to potential coexistence of resident and mutant types. Finally, we discuss the effect of the 'fitness shift' where the fitness function of two types has a phase difference. We observe significant increases (or decreases) in the fixation probability of the mutant as a result of such phase shift.
Collapse
Affiliation(s)
- Hossein Nemati
- Sharif University of Technology, Physics Department, Iran
| | - Kamran Kaveh
- University of Washington, Department of Applied Mathematics, United States of America.
| | | |
Collapse
|
18
|
Yagoobi S, Sharma N, Traulsen A. Categorizing update mechanisms for graph-structured metapopulations. J R Soc Interface 2023; 20:20220769. [PMID: 36919418 PMCID: PMC10015335 DOI: 10.1098/rsif.2022.0769] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 03/16/2023] Open
Abstract
The structure of a population strongly influences its evolutionary dynamics. In various settings ranging from biology to social systems, individuals tend to interact more often with those present in their proximity and rarely with those far away. A common approach to model the structure of a population is evolutionary graph theory. In this framework, each graph node is occupied by a reproducing individual. The links connect these individuals to their neighbours. The offspring can be placed on neighbouring nodes, replacing the neighbours-or the progeny of its neighbours can replace a node during the course of ongoing evolutionary dynamics. Extending this theory by replacing single individuals with subpopulations at nodes yields a graph-structured metapopulation. The dynamics between the different local subpopulations is set by an update mechanism. There are many such update mechanisms. Here, we classify update mechanisms for structured metapopulations, which allows to find commonalities between past work and illustrate directions for further research and current gaps of investigation.
Collapse
Affiliation(s)
- Sedigheh Yagoobi
- Department of Evolutionary Theory, Max Planck Institute for Evolutionary Biology, August-Thienemann Strasse 2, Plön 24306, Germany
| | - Nikhil Sharma
- Department of Evolutionary Theory, Max Planck Institute for Evolutionary Biology, August-Thienemann Strasse 2, Plön 24306, Germany
| | - Arne Traulsen
- Department of Evolutionary Theory, Max Planck Institute for Evolutionary Biology, August-Thienemann Strasse 2, Plön 24306, Germany
| |
Collapse
|
19
|
Universal scaling of extinction time in stochastic evolutionary dynamics. Sci Rep 2022; 12:22403. [PMID: 36575301 PMCID: PMC9794815 DOI: 10.1038/s41598-022-27102-0] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/18/2022] [Accepted: 12/26/2022] [Indexed: 12/28/2022] Open
Abstract
Evolutionary dynamics is well captured by the replicator equations when the population is infinite and well-mixed. However, the extinction dynamics is modified with finite and structured populations. Experiments on the non-transitive ecosystem containing three populations of bacteria found that the ecological stability sensitively depends on the spatial structure of the populations. Based on the Reference-Gamble-Birth algorithm, we use agent-based Monte Carlo simulations to investigate the extinction dynamics in the rock-paper-scissors ecosystem with finite and structured populations. On the fully-connected network, the extinction time in stable and unstable regimes falls into two universal functions when plotted with the rescaled variables. On the two dimensional grid, the spatial structure changes the transition boundary between stable and unstable regimes but doesn't change its extinction trend. The finding of universal scaling in extinction dynamics is unexpected, and may provide a powerful method to classify different evolutionary dynamics into universal classes.
Collapse
|
20
|
Suppressors of fixation can increase average fitness beyond amplifiers of selection. Proc Natl Acad Sci U S A 2022; 119:e2205424119. [PMID: 36067304 PMCID: PMC9478682 DOI: 10.1073/pnas.2205424119] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/18/2022] Open
Abstract
Evolutionary dynamics on graphs has remarkable features: For example, it has been shown that amplifiers of selection exist that-compared to an unstructured population-increase the fixation probability of advantageous mutations, while they decrease the fixation probability of disadvantageous mutations. So far, the theoretical literature has focused on the case of a single mutant entering a graph-structured population, asking how the graph affects the probability that a mutant takes over a population and the time until this typically happens. For continuously evolving systems, the more relevant case is that mutants constantly arise in an evolving population. Typically, such mutations occur with a small probability during reproduction events. We thus focus on the low mutation rate limit. The probability distribution for the fitness in this process converges to a steady state at long times. Intuitively, amplifiers of selection are expected to increase the population's mean fitness in the steady state. Similarly, suppressors of selection are expected to decrease the population's mean fitness in the steady state. However, we show that another set of graphs, called suppressors of fixation, can attain the highest population mean fitness. The key reason behind this is their ability to efficiently reject deleterious mutants. This illustrates the importance of the deleterious mutant regime for the long-term evolutionary dynamics, something that seems to have been overlooked in the literature so far.
Collapse
|
21
|
Danovski K, Brede M. On the evolutionary language game in structured and adaptive populations. PLoS One 2022; 17:e0273608. [PMID: 36040912 PMCID: PMC9426894 DOI: 10.1371/journal.pone.0273608] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/31/2022] [Accepted: 08/07/2022] [Indexed: 11/18/2022] Open
Abstract
We propose an evolutionary model for the emergence of shared linguistic convention in a population of agents whose social structure is modelled by complex networks. Through agent-based simulations, we show a process of convergence towards a common language, and explore how the topology of the underlying networks affects its dynamics. We find that small-world effects act to speed up convergence, but observe no effect of topology on the communicative efficiency of common languages. We further explore differences in agent learning, discriminating between scenarios in which new agents learn from their parents (vertical transmission) versus scenarios in which they learn from their neighbors (oblique transmission), finding that vertical transmission results in faster convergence and generally higher communicability. Optimal languages can be formed when parental learning is dominant, but a small amount of neighbor learning is included. As a last point, we illustrate an exclusion effect leading to core-periphery networks in an adaptive networks setting when agents attempt to reconnect towards better communicators in the population.
Collapse
Affiliation(s)
- Kaloyan Danovski
- Electronics and Computer Science, University of Southampton, Southampton, Hampshire, United Kingdom
- * E-mail:
| | - Markus Brede
- Electronics and Computer Science, University of Southampton, Southampton, Hampshire, United Kingdom
| |
Collapse
|
22
|
Coggan H, Page KM. The role of evolutionary game theory in spatial and non-spatial models of the survival of cooperation in cancer: a review. JOURNAL OF THE ROYAL SOCIETY, INTERFACE 2022; 19:20220346. [PMID: 35975562 PMCID: PMC9382458 DOI: 10.1098/rsif.2022.0346] [Citation(s) in RCA: 5] [Impact Index Per Article: 2.5] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Indexed: 12/15/2022]
Abstract
Evolutionary game theory (EGT) is a branch of mathematics which considers populations of individuals interacting with each other to receive pay-offs. An individual’s pay-off is dependent on the strategy of its opponent(s) as well as on its own, and the higher its pay-off, the higher its reproductive fitness. Its offspring generally inherit its interaction strategy, subject to random mutation. Over time, the composition of the population shifts as different strategies spread or are driven extinct. In the last 25 years there has been a flood of interest in applying EGT to cancer modelling, with the aim of explaining how cancerous mutations spread through healthy tissue and how intercellular cooperation persists in tumour-cell populations. This review traces this body of work from theoretical analyses of well-mixed infinite populations through to more realistic spatial models of the development of cooperation between epithelial cells. We also consider work in which EGT has been used to make experimental predictions about the evolution of cancer, and discuss work that remains to be done before EGT can make large-scale contributions to clinical treatment and patient outcomes.
Collapse
Affiliation(s)
- Helena Coggan
- Department of Mathematics, University College London, London, UK
| | - Karen M Page
- Department of Mathematics, University College London, London, UK
| |
Collapse
|
23
|
Monk T, van Schaik A. Martingales and the fixation time of evolutionary graphs with arbitrary dimensionality. ROYAL SOCIETY OPEN SCIENCE 2022; 9:220011. [PMID: 35573040 PMCID: PMC9091843 DOI: 10.1098/rsos.220011] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 01/06/2022] [Accepted: 04/01/2022] [Indexed: 05/03/2023]
Abstract
Evolutionary graph theory (EGT) investigates the Moran birth-death process constrained by graphs. Its two principal goals are to find the fixation probability and time for some initial population of mutants on the graph. The fixation probability of graphs has received considerable attention. Less is known about the distribution of fixation time. We derive clean, exact expressions for the full conditional characteristic functions (CCFs) of a close proxy to fixation and extinction times. That proxy is the number of times that the mutant population size changes before fixation or extinction. We derive these CCFs from a product martingale that we identify for an evolutionary graph with any number of partitions. The existence of that martingale only requires that the connections between those partitions are of a certain type. Our results are the first expressions for the CCFs of any proxy to fixation time on a graph with any number of partitions. The parameter dependence of our CCFs is explicit, so we can explore how they depend on graph structure. Martingales are a powerful approach to study principal problems of EGT. Their applicability is invariant to the number of partitions in a graph, so we can study entire families of graphs simultaneously.
Collapse
Affiliation(s)
- Travis Monk
- International Centre for Neuromorphic Systems, The MARCS Institute, Western Sydney University, Sydney, Australia
| | - André van Schaik
- International Centre for Neuromorphic Systems, The MARCS Institute, Western Sydney University, Sydney, Australia
| |
Collapse
|
24
|
Hajihashemi M, Aghababaei Samani K. Multi-strategy evolutionary games: A Markov chain approach. PLoS One 2022; 17:e0263979. [PMID: 35176094 PMCID: PMC8853582 DOI: 10.1371/journal.pone.0263979] [Citation(s) in RCA: 2] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/27/2021] [Accepted: 02/01/2022] [Indexed: 11/18/2022] Open
Abstract
Interacting strategies in evolutionary games is studied analytically in a well-mixed population using a Markov chain method. By establishing a correspondence between an evolutionary game and Markov chain dynamics, we show that results obtained from the fundamental matrix method in Markov chain dynamics are equivalent to corresponding ones in the evolutionary game. In the conventional fundamental matrix method, quantities like fixation probability and fixation time are calculable. Using a theorem in the fundamental matrix method, conditional fixation time in the absorbing Markov chain is calculable. Also, in the ergodic Markov chain, the stationary probability distribution that describes the Markov chain’s stationary state is calculable analytically. Finally, the Rock, scissor, paper evolutionary game are evaluated as an example, and the results of the analytical method and simulations are compared. Using this analytical method saves time and computational facility compared to prevalent simulation methods.
Collapse
Affiliation(s)
- Mahdi Hajihashemi
- Department of Physics, Isfahan University of Technology, Isfahan, Iran
- * E-mail:
| | | |
Collapse
|
25
|
Cuesta FA, Guerberoff G, Rojo ÁL. Bernoulli and binomial proliferation on evolutionary graphs. J Theor Biol 2022; 534:110942. [PMID: 34717934 DOI: 10.1016/j.jtbi.2021.110942] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/18/2021] [Revised: 10/18/2021] [Accepted: 10/20/2021] [Indexed: 11/16/2022]
Abstract
In this paper we introduce random proliferation models on graphs. We consider two types of particles: type-1/mutant/invader/red particles proliferates on a population of type-2/wild-type/resident/blue particles. Unlike the well-known Moran model on graphs -as introduced in Lieberman et al. (2005)-, type-1 particles can occupy in a single iteration several neighbouring sites previously occupied by type-2 particles. Two variants are considered, depending on the random distribution involving the proliferation mechanism: Bernoulli and binomial proliferation. By comparison with fixation probability of type-1 particles in the Moran process, critical parameters are introduced. Properties of proliferation are studied and some particular cases are analytically solved. Finally, by updating the parameters that drive the processes through a density-dependent mechanism, it is possible to capture additional relevant features as fluctuating waves of type-1 particles over long periods of time. In fact, the models can be adapted to tackle more general, complex and realistic situations.
Collapse
Affiliation(s)
- Fernando Alcalde Cuesta
- Instituto de Matemáticas, Universidad de Santiago de Compostela, Santiago de Compostela E-15782, Spain
| | - Gustavo Guerberoff
- Instituto de Matemática y Estadística Rafael Laguardia, Facultad de Ingeniería, Universidad de la República, J. Herrera y Reissig 565, Montevideo C.P.11300, Uruguay.
| | - Álvaro Lozano Rojo
- Departamento de Matemáticas, Instituto Universitario de Matemáticas y Aplicaciones (IUMA), Universidad de Zaragoza, Pedro Cerbuna, 12, Zaragoza E-50009, Spain
| |
Collapse
|
26
|
Labavić D, Loverdo C, Bitbol AF. Hydrodynamic flow and concentration gradients in the gut enhance neutral bacterial diversity. Proc Natl Acad Sci U S A 2022; 119:e2108671119. [PMID: 34969835 PMCID: PMC8740595 DOI: 10.1073/pnas.2108671119] [Citation(s) in RCA: 5] [Impact Index Per Article: 2.5] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Accepted: 11/08/2021] [Indexed: 01/23/2023] Open
Abstract
The gut microbiota features important genetic diversity, and the specific spatial features of the gut may shape evolution within this environment. We investigate the fixation probability of neutral bacterial mutants within a minimal model of the gut that includes hydrodynamic flow and resulting gradients of food and bacterial concentrations. We find that this fixation probability is substantially increased, compared with an equivalent well-mixed system, in the regime where the profiles of food and bacterial concentration are strongly spatially dependent. Fixation probability then becomes independent of total population size. We show that our results can be rationalized by introducing an active population, which consists of those bacteria that are actively consuming food and dividing. The active population size yields an effective population size for neutral mutant fixation probability in the gut.
Collapse
Affiliation(s)
- Darka Labavić
- CNRS, Institut de Biologie Paris-Seine, Laboratoire Jean Perrin (UMR 8237), Sorbonne Université, F-75005 Paris, France
| | - Claude Loverdo
- CNRS, Institut de Biologie Paris-Seine, Laboratoire Jean Perrin (UMR 8237), Sorbonne Université, F-75005 Paris, France;
| | - Anne-Florence Bitbol
- Institute of Bioengineering, School of Life Sciences, École Polytechnique Fédérale de Lausanne (EPFL), CH-1015 Lausanne, Switzerland;
- SIB Swiss Institute of Bioinformatics, CH-1015 Lausanne, Switzerland
| |
Collapse
|
27
|
Balasekaran M, Johanis M, Rychtář J, Taylor D, Zhu J. Quasi-neutral evolution in populations under small demographic fluctuations. J Theor Biol 2022; 538:111040. [DOI: 10.1016/j.jtbi.2022.111040] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/02/2021] [Revised: 01/11/2022] [Accepted: 01/19/2022] [Indexed: 10/19/2022]
|
28
|
Marrec L, Lamberti I, Bitbol AF. Toward a Universal Model for Spatially Structured Populations. PHYSICAL REVIEW LETTERS 2021; 127:218102. [PMID: 34860074 DOI: 10.1103/physrevlett.127.218102] [Citation(s) in RCA: 5] [Impact Index Per Article: 1.7] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/19/2021] [Revised: 07/23/2021] [Accepted: 10/06/2021] [Indexed: 06/13/2023]
Abstract
A key question in evolution is how likely a mutant is to take over. This depends on natural selection and on stochastic fluctuations. Population spatial structure can impact mutant fixation probabilities. We introduce a model for structured populations on graphs that generalizes previous ones by making migrations independent of birth and death. We demonstrate that by tuning migration asymmetry, the star graph transitions from amplifying to suppressing natural selection. The results from our model are universal in the sense that they do not hinge on a modeling choice of microscopic dynamics or update rules. Instead, they depend on migration asymmetry, which can be experimentally tuned and measured.
Collapse
Affiliation(s)
- Loïc Marrec
- Sorbonne Université, CNRS, Institut de Biologie Paris-Seine, Laboratoire Jean Perrin (UMR 8237), F-75005 Paris, France
| | - Irene Lamberti
- Sorbonne Université, CNRS, Institut de Biologie Paris-Seine, Laboratoire Jean Perrin (UMR 8237), F-75005 Paris, France
| | - Anne-Florence Bitbol
- Sorbonne Université, CNRS, Institut de Biologie Paris-Seine, Laboratoire Jean Perrin (UMR 8237), F-75005 Paris, France
- Institute of Bioengineering, School of Life Sciences, École Polytechnique Fédérale de Lausanne (EPFL), CH-1015 Lausanne, Switzerland
- SIB Swiss Institute of Bioinformatics, CH-1015 Lausanne, Switzerland
| |
Collapse
|
29
|
Yagoobi S, Traulsen A. Fixation probabilities in network structured meta-populations. Sci Rep 2021; 11:17979. [PMID: 34504152 PMCID: PMC8429422 DOI: 10.1038/s41598-021-97187-6] [Citation(s) in RCA: 6] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/16/2021] [Accepted: 08/23/2021] [Indexed: 02/07/2023] Open
Abstract
The effect of population structure on evolutionary dynamics is a long-lasting research topic in evolutionary ecology and population genetics. Evolutionary graph theory is a popular approach to this problem, where individuals are located on the nodes of a network and can replace each other via the links. We study the effect of complex network structure on the fixation probability, but instead of networks of individuals, we model a network of sub-populations with a probability of migration between them. We ask how the structure of such a meta-population and the rate of migration affect the fixation probability. Many of the known results for networks of individuals carry over to meta-populations, in particular for regular networks or low symmetric migration probabilities. However, when patch sizes differ we find interesting deviations between structured meta-populations and networks of individuals. For example, a two patch structure with unequal population size suppresses selection for low migration probabilities.
Collapse
Affiliation(s)
- Sedigheh Yagoobi
- Department of Evolutionary Theory, Max Planck Institute for Evolutionary Biology, 24306, Plön, Germany.
| | - Arne Traulsen
- Department of Evolutionary Theory, Max Planck Institute for Evolutionary Biology, 24306, Plön, Germany
| |
Collapse
|
30
|
Richter H. Spectral analysis of transient amplifiers for death-birth updating constructed from regular graphs. J Math Biol 2021; 82:61. [PMID: 33993365 PMCID: PMC8126557 DOI: 10.1007/s00285-021-01609-y] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/18/2021] [Revised: 03/31/2021] [Accepted: 04/19/2021] [Indexed: 11/24/2022]
Abstract
A central question of evolutionary dynamics on graphs is whether or not a mutation introduced in a population of residents survives and eventually even spreads to the whole population, or becomes extinct. The outcome naturally depends on the fitness of the mutant and the rules by which mutants and residents may propagate on the network, but arguably the most determining factor is the network structure. Some structured networks are transient amplifiers. They increase for a certain fitness range the fixation probability of beneficial mutations as compared to a well-mixed population. We study a perturbation method for identifying transient amplifiers for death–birth updating. The method involves calculating the coalescence times of random walks on graphs and finding the vertex with the largest remeeting time. If the graph is perturbed by removing an edge from this vertex, there is a certain likelihood that the resulting perturbed graph is a transient amplifier. We test all pairwise nonisomorphic regular graphs up to a certain order and thus cover the whole structural range expressible by these graphs. For cubic and quartic regular graphs we find a sufficiently large number of transient amplifiers. For these networks we carry out a spectral analysis and show that the graphs from which transient amplifiers can be constructed share certain structural properties. Identifying spectral and structural properties may promote finding and designing such networks.
Collapse
Affiliation(s)
- Hendrik Richter
- HTWK Leipzig University of Applied Sciences, Leipzig, Germany.
| |
Collapse
|
31
|
Overton CE, Sharkey KJ. Evolutionary bet-hedging in structured populations. J Math Biol 2021; 82:43. [PMID: 33796960 PMCID: PMC8016807 DOI: 10.1007/s00285-021-01597-z] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/15/2020] [Revised: 03/08/2021] [Accepted: 03/16/2021] [Indexed: 11/21/2022]
Abstract
As ecosystems evolve, species can become extinct due to fluctuations in the environment. This leads to the evolutionary adaption known as bet-hedging, where species hedge against these fluctuations to reduce their likelihood of extinction. Environmental variation can be either within or between generations. Previous work has shown that selection for bet-hedging against within-generational variation should not occur in large populations. However, this work has been limited by assumptions of well-mixed populations, whereas real populations usually have some degree of structure. Using the framework of evolutionary graph theory, we show that through adding competition structure to the population, within-generational variation can have a significant impact on the evolutionary process for any population size. This complements research using subdivided populations, which suggests that within-generational variation is important when local population sizes are small. Together, these conclusions provide evidence to support observations by some ecologists that are contrary to the widely held view that only between-generational environmental variation has an impact on natural selection. This provides theoretical justification for further empirical study into this largely unexplored area.
Collapse
|
32
|
Pattni K, Overton CE, Sharkey KJ. Evolutionary graph theory derived from eco-evolutionary dynamics. J Theor Biol 2021; 519:110648. [PMID: 33636202 DOI: 10.1016/j.jtbi.2021.110648] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/13/2020] [Revised: 02/15/2021] [Accepted: 02/18/2021] [Indexed: 11/28/2022]
Abstract
A biologically motivated individual-based framework for evolution in network-structured populations is developed that can accommodate eco-evolutionary dynamics. This framework is used to construct a network birth and death model. The evolutionary graph theory model, which considers evolutionary dynamics only, is derived as a special case, highlighting additional assumptions that diverge from real biological processes. This is achieved by introducing a negative ecological feedback loop that suppresses ecological dynamics by forcing births and deaths to be coupled. We also investigate how fitness, a measure of reproductive success used in evolutionary graph theory, is related to the life-history of individuals in terms of their birth and death rates. In simple networks, these ecologically motivated dynamics are used to provide new insight into the spread of adaptive mutations, both with and without clonal interference. For example, the star network, which is known to be an amplifier of selection in evolutionary graph theory, can inhibit the spread of adaptive mutations when individuals can die naturally.
Collapse
Affiliation(s)
- Karan Pattni
- Department of Mathematical Sciences, University of Liverpool, United Kingdom.
| | | | - Kieran J Sharkey
- Department of Mathematical Sciences, University of Liverpool, United Kingdom.
| |
Collapse
|
33
|
Fixation probabilities in evolutionary dynamics under weak selection. J Math Biol 2021; 82:14. [PMID: 33534054 DOI: 10.1007/s00285-021-01568-4] [Citation(s) in RCA: 19] [Impact Index Per Article: 6.3] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/31/2020] [Revised: 11/14/2020] [Accepted: 01/17/2021] [Indexed: 10/22/2022]
Abstract
In evolutionary dynamics, a key measure of a mutant trait's success is the probability that it takes over the population given some initial mutant-appearance distribution. This "fixation probability" is difficult to compute in general, as it depends on the mutation's effect on the organism as well as the population's spatial structure, mating patterns, and other factors. In this study, we consider weak selection, which means that the mutation's effect on the organism is small. We obtain a weak-selection perturbation expansion of a mutant's fixation probability, from an arbitrary initial configuration of mutant and resident types. Our results apply to a broad class of stochastic evolutionary models, in which the size and spatial structure are arbitrary (but fixed). The problem of whether selection favors a given trait is thereby reduced from exponential to polynomial complexity in the population size, when selection is weak. We conclude by applying these methods to obtain new results for evolutionary dynamics on graphs.
Collapse
|
34
|
Allen B, Sample C, Steinhagen P, Shapiro J, King M, Hedspeth T, Goncalves M. Fixation probabilities in graph-structured populations under weak selection. PLoS Comput Biol 2021; 17:e1008695. [PMID: 33529219 PMCID: PMC7880501 DOI: 10.1371/journal.pcbi.1008695] [Citation(s) in RCA: 8] [Impact Index Per Article: 2.7] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/14/2020] [Revised: 02/12/2021] [Accepted: 01/11/2021] [Indexed: 12/12/2022] Open
Abstract
A population's 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's 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.
Collapse
Affiliation(s)
- Benjamin Allen
- Department of Mathematics, Emmanuel College, Boston, Massachusetts, United States of America
| | - Christine Sample
- Department of Mathematics, Emmanuel College, Boston, Massachusetts, United States of America
| | - Patricia Steinhagen
- Department of Mathematics, Emmanuel College, Boston, Massachusetts, United States of America
| | - Julia Shapiro
- Department of Mathematics, Emmanuel College, Boston, Massachusetts, United States of America
| | - Matthew King
- Department of Mathematics, Emmanuel College, Boston, Massachusetts, United States of America
| | - Timothy Hedspeth
- Department of Mathematics, Emmanuel College, Boston, Massachusetts, United States of America
| | - Megan Goncalves
- Department of Mathematics, Emmanuel College, Boston, Massachusetts, United States of America
| |
Collapse
|
35
|
Kaveh K, McAvoy A, Chatterjee K, Nowak MA. The Moran process on 2-chromatic graphs. PLoS Comput Biol 2020; 16:e1008402. [PMID: 33151935 PMCID: PMC7671562 DOI: 10.1371/journal.pcbi.1008402] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/25/2020] [Revised: 11/17/2020] [Accepted: 09/27/2020] [Indexed: 12/02/2022] Open
Abstract
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 “properly colored” 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. Heterogeneity in environmental conditions can have profound effects on long-term evolutionary outcomes in structured populations. We consider a population evolving on a colored graph, wherein the color of a node represents the resources at that location. Using a combination of analytical and numerical methods, we quantify the effects of background heterogeneity on a population’s dynamics. In addition to considering the notion of an “optimal” coloring with respect to mutant invasion, we also study the effects of dynamic spatial redistribution of resources as the population evolves. Although the effects of static background heterogeneity can be quite striking, these effects are often attenuated by the movement (or “flow”) of the underlying resources.
Collapse
Affiliation(s)
- Kamran Kaveh
- Department of Mathematics, Dartmouth College, Hanover, New Hampshire, United States
- * E-mail: (KK); (AM)
| | - Alex McAvoy
- Department of Mathematics, University of Pennsylvania, Philadelphia, Pennsylvania, United States
- * E-mail: (KK); (AM)
| | | | - Martin A. Nowak
- Department of Mathematics, Harvard University, Cambridge, Massachusetts, United States
- Department of Organismic and Evolutionary Biology, Harvard University, Cambridge, Massachusetts, United States
| |
Collapse
|
36
|
Li A, Zhou L, Su Q, Cornelius SP, Liu YY, Wang L, Levin SA. Evolution of cooperation on temporal networks. Nat Commun 2020; 11:2259. [PMID: 32385279 PMCID: PMC7210286 DOI: 10.1038/s41467-020-16088-w] [Citation(s) in RCA: 35] [Impact Index Per Article: 8.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/28/2019] [Accepted: 04/04/2020] [Indexed: 11/28/2022] Open
Abstract
Population structure is a key determinant in fostering cooperation among naturally self-interested individuals in microbial populations, social insect groups, and human societies. Traditional research has focused on static structures, and yet most real interactions are finite in duration and changing in time, forming a temporal network. This raises the question of whether cooperation can emerge and persist despite an intrinsically fragmented population structure. Here we develop a framework to study the evolution of cooperation on temporal networks. Surprisingly, we find that network temporality actually enhances the evolution of cooperation relative to comparable static networks, despite the fact that bursty interaction patterns generally impede cooperation. We resolve this tension by proposing a measure to quantify the amount of temporality in a network, revealing an intermediate level that maximally boosts cooperation. Our results open a new avenue for investigating the evolution of cooperation and other emergent behaviours in more realistic structured populations. Population structure enables emergence of cooperation among individuals, but the impact of the dynamic nature of real interaction networks is not understood. Here, the authors study the evolution of cooperation on temporal networks and find that temporality enhances the evolution of cooperation.
Collapse
Affiliation(s)
- Aming Li
- Center for Systems and Control, College of Engineering, Peking University, Beijing, 100871, China.,Department of Zoology and Department of Biochemistry, University of Oxford, Oxford, OX1 3PS, UK.,Center for Complex Network Research and Department of Physics, Northeastern University, Boston, MA, 02115, USA
| | - Lei Zhou
- Center for Systems and Control, College of Engineering, Peking University, Beijing, 100871, China.,Department of Ecology and Evolutionary Biology, Princeton University, Princeton, NJ, 08544, USA
| | - Qi Su
- Center for Systems and Control, College of Engineering, Peking University, Beijing, 100871, China.,Department of Mathematics and Department of Biology, University of Pennsylvania, Philadelphia, PA, 19104, USA
| | - Sean P Cornelius
- Center for Complex Network Research and Department of Physics, Northeastern University, Boston, MA, 02115, USA.,Department of Physics, Ryerson University, Toronto, ON, M5B 2K3, Canada.,Channing Division of Network Medicine, Brigham and Women's Hospital, Harvard Medical School, Boston, MA, 02115, USA
| | - Yang-Yu Liu
- Channing Division of Network Medicine, Brigham and Women's Hospital, Harvard Medical School, Boston, MA, 02115, USA. .,Center for Cancer Systems Biology, Dana-Farber Cancer Institute, Boston, MA, 02115, USA.
| | - Long Wang
- Center for Systems and Control, College of Engineering, Peking University, Beijing, 100871, China.
| | - Simon A Levin
- Department of Ecology and Evolutionary Biology, Princeton University, Princeton, NJ, 08544, USA.
| |
Collapse
|
37
|
Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. Limits on amplifiers of natural selection under death-Birth updating. PLoS Comput Biol 2020; 16:e1007494. [PMID: 31951609 PMCID: PMC6968837 DOI: 10.1371/journal.pcbi.1007494] [Citation(s) in RCA: 24] [Impact Index Per Article: 6.0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/03/2019] [Accepted: 10/18/2019] [Indexed: 12/29/2022] Open
Abstract
The fixation probability of a single mutant invading a population of residents is among the most widely-studied quantities in evolutionary dynamics. Amplifiers of natural selection are population structures that increase the fixation probability of advantageous mutants, compared to well-mixed populations. Extensive studies have shown that many amplifiers exist for the Birth-death Moran process, some of them substantially increasing the fixation probability or even guaranteeing fixation in the limit of large population size. On the other hand, no amplifiers are known for the death-Birth Moran process, and computer-assisted exhaustive searches have failed to discover amplification. In this work we resolve this disparity, by showing that any amplification under death-Birth updating is necessarily bounded and transient. Our boundedness result states that even if a population structure does amplify selection, the resulting fixation probability is close to that of the well-mixed population. Our transience result states that for any population structure there exists a threshold r⋆ such that the population structure ceases to amplify selection if the mutant fitness advantage r is larger than r⋆. Finally, we also extend the above results to δ-death-Birth updating, which is a combination of Birth-death and death-Birth updating. On the positive side, we identify population structures that maintain amplification for a wide range of values r and δ. These results demonstrate that amplification of natural selection depends on the specific mechanisms of the evolutionary process. Extensive literature exists on amplifiers of natural selection for the Birth-death Moran process, but no amplifiers are known for the death-Birth Moran process. Here we show that if amplifiers exist under death-Birth updating, they must be bounded and transient. Boundedness implies weak amplification, and transience implies amplification for only a limited range of the mutant fitness advantage. These results demonstrate that amplification depends on the specific mechanisms of the evolutionary process.
Collapse
Affiliation(s)
| | | | | | - Martin A. Nowak
- Program for Evolutionary Dynamics, Department of Organismic and Evolutionary Biology, Department of Mathematics, Harvard University, Cambridge, Massachusetts, United States of America
- * E-mail:
| |
Collapse
|
38
|
Allen B, Sample C, Jencks R, Withers J, Steinhagen P, Brizuela L, Kolodny J, Parke D, Lippner G, Dementieva YA. Transient amplifiers of selection and reducers of fixation for death-Birth updating on graphs. PLoS Comput Biol 2020; 16:e1007529. [PMID: 31951612 PMCID: PMC6968840 DOI: 10.1371/journal.pcbi.1007529] [Citation(s) in RCA: 23] [Impact Index Per Article: 5.8] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/01/2019] [Accepted: 10/30/2019] [Indexed: 11/30/2022] Open
Abstract
The spatial structure of an evolving population affects the balance of natural selection versus genetic drift. Some structures amplify selection, increasing the role that fitness differences play in determining which mutations become fixed. Other structures suppress selection, reducing the effect of fitness differences and increasing the role of random chance. This phenomenon can be modeled by representing spatial structure as a graph, with individuals occupying vertices. Births and deaths occur stochastically, according to a specified update rule. We study death-Birth updating: An individual is chosen to die and then its neighbors compete to reproduce into the vacant spot. Previous numerical experiments suggested that amplifiers of selection for this process are either rare or nonexistent. We introduce a perturbative method for this problem for weak selection regime, meaning that mutations have small fitness effects. We show that fixation probability under weak selection can be calculated in terms of the coalescence times of random walks. This result leads naturally to a new definition of effective population size. Using this and other methods, we uncover the first known examples of transient amplifiers of selection (graphs that amplify selection for a particular range of fitness values) for the death-Birth process. We also exhibit new families of “reducers of fixation”, which decrease the fixation probability of all mutations, whether beneficial or deleterious. Natural selection is often thought of as “survival of the fittest”, but random chance plays a significant role in which mutations persist and which are eliminated. The balance of selection versus randomness is affected by spatial structure—how individuals are arranged within their habitat. Some structures amplify the effects of selection, so that only the fittest mutations are likely to persist. Others suppress the effects of selection, making the survival of genes primarily a matter of random chance. We study this question using a mathematical model called the “death-Birth process”. Previous studies have found that spatial structure rarely, if ever, amplifies selection for this process. Here we report that spatial structure can indeed amplify selection, at least for mutations with small fitness effects. We also identify structures that reduce the spread of any new mutation, whether beneficial or deleterious. Our work introduces new mathematical techniques for assessing how population structure affects natural selection.
Collapse
Affiliation(s)
- Benjamin Allen
- Department of Mathematics, Emmanuel College, Boston, Massachusetts, United States of America
- * E-mail:
| | - Christine Sample
- Department of Mathematics, Emmanuel College, Boston, Massachusetts, United States of America
| | - Robert Jencks
- Department of Mathematics, Emmanuel College, Boston, Massachusetts, United States of America
| | - James Withers
- Department of Mathematics, Emmanuel College, Boston, Massachusetts, United States of America
| | - Patricia Steinhagen
- Department of Mathematics, Emmanuel College, Boston, Massachusetts, United States of America
| | - Lori Brizuela
- Department of Mathematics, Emmanuel College, Boston, Massachusetts, United States of America
| | - Joshua Kolodny
- Department of Mathematics, Emmanuel College, Boston, Massachusetts, United States of America
| | - Darren Parke
- Department of Mathematics, Emmanuel College, Boston, Massachusetts, United States of America
| | - Gabor Lippner
- Department of Mathematics, Northeastern University, Boston, Massachusetts, United States of America
| | - Yulia A. Dementieva
- Department of Mathematics, Emmanuel College, Boston, Massachusetts, United States of America
| |
Collapse
|
39
|
Carja O, Creanza N. The evolutionary advantage of cultural memory on heterogeneous contact networks. Theor Popul Biol 2019; 129:118-125. [DOI: 10.1016/j.tpb.2018.09.006] [Citation(s) in RCA: 6] [Impact Index Per Article: 1.2] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/09/2018] [Revised: 07/09/2018] [Accepted: 09/29/2018] [Indexed: 11/28/2022]
|
40
|
Xiao Y, Wu B. Close spatial arrangement of mutants favors and disfavors fixation. PLoS Comput Biol 2019; 15:e1007212. [PMID: 31525178 PMCID: PMC6746358 DOI: 10.1371/journal.pcbi.1007212] [Citation(s) in RCA: 5] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/08/2019] [Accepted: 06/25/2019] [Indexed: 11/26/2022] Open
Abstract
Cooperation is ubiquitous across all levels of biological systems ranging from microbial communities to human societies. It, however, seemingly contradicts the evolutionary theory, since cooperators are exploited by free-riders and thus are disfavored by natural selection. Many studies based on evolutionary game theory have tried to solve the puzzle and figure out the reason why cooperation exists and how it emerges. Network reciprocity is one of the mechanisms to promote cooperation, where nodes refer to individuals and links refer to social relationships. The spatial arrangement of mutant individuals, which refers to the clustering of mutants, plays a key role in network reciprocity. Besides, many other mechanisms supporting cooperation suggest that the clustering of mutants plays an important role in the expansion of mutants. However, the clustering of mutants and the game dynamics are typically coupled. It is still unclear how the clustering of mutants alone alters the evolutionary dynamics. To this end, we employ a minimal model with frequency independent fitness on a circle. It disentangles the clustering of mutants from game dynamics. The distance between two mutants on the circle is adopted as a natural indicator for the clustering of mutants or assortment. We find that the assortment is an amplifier of the selection for the connected mutants compared with the separated ones. Nevertheless, as mutants are separated, the more dispersed mutants are, the greater the chance of invasion is. It gives rise to the non-monotonic effect of clustering, which is counterintuitive. On the other hand, we find that less assortative mutants speed up fixation. Our model shows that the clustering of mutants plays a non-trivial role in fixation, which has emerged even if the game interaction is absent. Evolutionary dynamics on networks are key for biological and social evolution. Typically, the clustering mutants on networks can dramatically alter the direction of selection. Previous studies on the assortment of mutants assume that individuals interact in a frequency-dependent way. It is hard to tell how assortment alone alters the evolutionary fate. We establish a minimal network model to disentangle the assortment from the game interaction. We find that for weak selection limit, the assortment of mutants plays little role in fixation probability. For strong selection limit, connected mutants, i.e., the maximum assortment, are best for fixation. When the mutants are separated by only one wild-type individual, it is worse off than that separated by more than one wild-type individual in fixation probability. Our results show the nontrivial yet fundamental effect of the clustering on fixation. Noteworthily, it has already arisen, even if the game interaction is absent.
Collapse
Affiliation(s)
- Yunming Xiao
- School of Sciences, Beijing University of Posts and Telecommunications, Beijing, China
| | - Bin Wu
- School of Sciences, Beijing University of Posts and Telecommunications, Beijing, China
- * E-mail:
| |
Collapse
|
41
|
Motion, fixation probability and the choice of an evolutionary process. PLoS Comput Biol 2019; 15:e1007238. [PMID: 31381556 PMCID: PMC6746388 DOI: 10.1371/journal.pcbi.1007238] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/15/2019] [Revised: 09/16/2019] [Accepted: 07/02/2019] [Indexed: 11/21/2022] Open
Abstract
Seemingly minor details of mathematical and computational models of evolution are known to change the effect of population structure on the outcome of evolutionary processes. For example, birth-death dynamics often result in amplification of selection, while death-birth processes have been associated with suppression. In many biological populations the interaction structure is not static. Instead, members of the population are in motion and can interact with different individuals at different times. In this work we study populations embedded in a flowing medium; the interaction network is then time dependent. We use computer simulations to investigate how this dynamic structure affects the success of invading mutants, and compare these effects for different coupled birth and death processes. Specifically, we show how the speed of the motion impacts the fixation probability of an invading mutant. Flows of different speeds interpolate between evolutionary dynamics on fixed heterogeneous graphs and well-stirred populations; this allows us to systematically compare against known results for static structured populations. We find that motion has an active role in amplifying or suppressing selection by fragmenting and reconnecting the interaction graph. While increasing flow speeds suppress selection for most evolutionary models, we identify characteristic responses to flow for the different update rules we test. In particular we find that selection can be maximally enhanced or suppressed at intermediate flow speeds. Whether a mutation spreads in a population or not is one of the most important questions in biology. The evolution of cancer and antibiotic resistance, for example, are mediated by invading mutants. Recent work has shown that population structure can have important consequences for the outcome of evolution. For instance, a mutant can have a higher or a lower chance of invasion than in unstructured populations. These effects can depend on seemingly minor details of the evolutionary model, such as the order of birth and death events. Many biological populations are in motion, for example due to external stirring. Experimentally this is known to be important; the performance of mutants in E. coli populations, for example, depends on the rate of mixing. Here, we focus on simulations of populations in a flowing medium, and compare the success of a mutant for different flow speeds. We contrast different evolutionary models, and identify what features of the evolutionary model affect mutant success for different speeds of the flow. We find that the chance of mutant invasion can be at its highest (or lowest) at intermediate flow speeds, depending on the order in which birth and death events occur in the evolutionary process.
Collapse
|
42
|
Correction: Most Undirected Random Graphs Are Amplifiers of Selection for Birth-Death Dynamics, but Suppressors of Selection for Death-Birth Dynamics. PLoS Comput Biol 2019; 15:e1007143. [PMID: 31199801 PMCID: PMC6568378 DOI: 10.1371/journal.pcbi.1007143] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Download PDF] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/19/2022] Open
|
43
|
Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. Population structure determines the tradeoff between fixation probability and fixation time. Commun Biol 2019; 2:138. [PMID: 31044163 PMCID: PMC6478818 DOI: 10.1038/s42003-019-0373-y] [Citation(s) in RCA: 24] [Impact Index Per Article: 4.8] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/07/2018] [Accepted: 03/07/2019] [Indexed: 12/04/2022] Open
Abstract
The rate of biological evolution depends on the fixation probability and on the fixation time of new mutants. Intensive research has focused on identifying population structures that augment the fixation probability of advantageous mutants. But these amplifiers of natural selection typically increase fixation time. Here we study population structures that achieve a tradeoff between fixation probability and time. First, we show that no amplifiers can have an asymptotically lower absorption time than the well-mixed population. Then we design population structures that substantially augment the fixation probability with just a minor increase in fixation time. Finally, we show that those structures enable higher effective rate of evolution than the well-mixed population provided that the rate of generating advantageous mutants is relatively low. Our work sheds light on how population structure affects the rate of evolution. Moreover, our structures could be useful for lab-based, medical, or industrial applications of evolutionary optimization.
Collapse
Affiliation(s)
| | | | | | - Martin A. Nowak
- Program for Evolutionary Dynamics, Department of Organismic and Evolutionary Biology, Department of Mathematics, Harvard University, Cambridge, MA 02138 USA
| |
Collapse
|
44
|
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. [PMID: 31044162 PMCID: PMC6478964 DOI: 10.1038/s42003-019-0374-x] [Citation(s) in RCA: 17] [Impact Index Per Article: 3.4] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/30/2018] [Accepted: 03/07/2019] [Indexed: 11/25/2022] Open
Abstract
Population structure can be modeled by evolutionary graphs, which can have a substantial influence on the fate of mutants. Individuals are located on the nodes of these graphs, competing to take over the graph via the links. Applications for this framework range from the ecology of river systems and cancer initiation in colonic crypts to biotechnological search for optimal mutations. In all these applications, both the probability of fixation and the associated time are of interest. We study this problem for all undirected and unweighted graphs up to a certain size. We devise a genetic algorithm to find graphs with high or low fixation probability and short or long fixation time and study their structure searching for common themes. Our work unravels structural properties that maximize or minimize fixation probability and time, which allows us to contribute to a first map of the universe of evolutionary graphs.
Collapse
Affiliation(s)
- Marius Möller
- Department of Evolutionary Theory, Max Planck Institute for Evolutionary Biology, D-24306 Plön, Germany
- Complex Systems and Networks Research Group, School of Mathematical Sciences, Queen Mary University of London, Mile End Road, London, E1 4NS UK
| | - Laura Hindersin
- Department of Evolutionary Theory, Max Planck Institute for Evolutionary Biology, D-24306 Plön, Germany
| | - Arne Traulsen
- Department of Evolutionary Theory, Max Planck Institute for Evolutionary Biology, D-24306 Plön, Germany
| |
Collapse
|
45
|
Hajihashemi M, Aghababaei Samani K. Fixation time in evolutionary graphs: A mean-field approach. Phys Rev E 2019; 99:042304. [PMID: 31108590 DOI: 10.1103/physreve.99.042304] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/13/2018] [Indexed: 06/09/2023]
Abstract
Using an analytical method we calculate average conditional fixation time of mutants in a general graph-structured population of two types of species. The method is based on Markov chains and uses a mean-field approximation to calculate the corresponding transition matrix. Analytical results are compared with the results of simulation of the Moran process on a number of network structures.
Collapse
Affiliation(s)
- Mahdi Hajihashemi
- Department of Physics, Isfahan University of Technology, Isfahan 84156-83111, Iran
| | - Keivan Aghababaei Samani
- Department of Physics, Isfahan University of Technology, Isfahan 84156-83111, Iran
- International Institute for Applied System Analysis (IIASA), Schlossolatz 1, A-2361 Laxenburg, Austria
| |
Collapse
|
46
|
Richter H. Properties of network structures, structure coefficients, and benefit-to-cost ratios. Biosystems 2019; 180:88-100. [PMID: 30914346 DOI: 10.1016/j.biosystems.2019.03.005] [Citation(s) in RCA: 10] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/17/2018] [Revised: 02/24/2019] [Accepted: 03/21/2019] [Indexed: 12/31/2022]
Abstract
In structured populations the spatial arrangement of cooperators and defectors on the interaction graph together with the structure of the graph itself determines the game dynamics and particularly whether or not fixation of cooperation (or defection) is favored. For networks described by regular graphs and for a single cooperator (and a single defector) the question of fixation can be addressed by a single parameter, the structure coefficient. This quantity is invariant with respect to the location of the cooperator on the graph and also does not vary over different networks. We may therefore consider it to be generic for regular graphs and call it the generic structure coefficient. For two and more cooperators (or several defectors) fixation properties can also be assigned by structure coefficients. These structure coefficients, however, depend on the arrangement of cooperators and defectors which we may interpret as a configuration of the game. Moreover, the coefficients are specific for a given interaction network modeled as a regular graph, which is why we may call them specific structure coefficients. In this paper, we study how specific structure coefficients vary over interaction graphs and analyze how spectral properties of interaction networks relate to specific structure coefficients. We also discuss implications for the benefit-to-cost ratios of donation games.
Collapse
Affiliation(s)
- Hendrik Richter
- HTWK Leipzig University of Applied Sciences, Faculty of Electrical Engineering and Information Technology, Postfach 301166, D-04251 Leipzig, Germany.
| |
Collapse
|
47
|
Overton CE, Broom M, Hadjichrysanthou C, Sharkey KJ. Methods for approximating stochastic evolutionary dynamics on graphs. J Theor Biol 2019; 468:45-59. [PMID: 30772340 DOI: 10.1016/j.jtbi.2019.02.009] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/20/2018] [Revised: 02/07/2019] [Accepted: 02/13/2019] [Indexed: 10/27/2022]
Abstract
Population structure can have a significant effect on evolution. For some systems with sufficient symmetry, analytic results can be derived within the mathematical framework of evolutionary graph theory which relate to the outcome of the evolutionary process. However, for more complicated heterogeneous structures, computationally intensive methods are required such as individual-based stochastic simulations. By adapting methods from statistical physics, including moment closure techniques, we first show how to derive existing homogenised pair approximation models and the exact neutral drift model. We then develop node-level approximations to stochastic evolutionary processes on arbitrarily complex structured populations represented by finite graphs, which can capture the different dynamics for individual nodes in the population. Using these approximations, we evaluate the fixation probability of invading mutants for given initial conditions, where the dynamics follow standard evolutionary processes such as the invasion process. Comparisons with the output of stochastic simulations reveal the effectiveness of our approximations in describing the stochastic processes and in predicting the probability of fixation of mutants on a wide range of graphs. Construction of these models facilitates a systematic analysis and is valuable for a greater understanding of the influence of population structure on evolutionary processes.
Collapse
Affiliation(s)
- Christopher E Overton
- Department of Mathematical Sciences, University of Liverpool, Mathematical Sciences Building, Liverpool L69 7ZL, UK.
| | - Mark Broom
- Department of Mathematics, City, University of London, Northampton Square, London EC1V 0HB, UK
| | - Christoforos Hadjichrysanthou
- Department of Infectious Disease Epidemiology, School of Public Health, Imperial College London, St Mary's Campus, Norfolk Place, London W2 1PG, UK
| | - Kieran J Sharkey
- Department of Mathematical Sciences, University of Liverpool, Mathematical Sciences Building, Liverpool L69 7ZL, UK
| |
Collapse
|
48
|
Kaveh K, McAvoy A, Nowak MA. Environmental fitness heterogeneity in the Moran process. ROYAL SOCIETY OPEN SCIENCE 2019; 6:181661. [PMID: 30800394 PMCID: PMC6366185 DOI: 10.1098/rsos.181661] [Citation(s) in RCA: 5] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 10/02/2018] [Accepted: 11/30/2018] [Indexed: 06/09/2023]
Abstract
Many mathematical models of evolution assume that all individuals experience the same environment. Here, we study the Moran process in heterogeneous environments. The population is of finite size with two competing types, which are exposed to a fixed number of environmental conditions. Reproductive rate is determined by both the type and the environment. We first calculate the condition for selection to favour the mutant relative to the resident wild-type. In large populations, the mutant is favoured if and only if the mutant's spatial average reproductive rate exceeds that of the resident. But environmental heterogeneity elucidates an interesting asymmetry between the mutant and the resident. Specifically, mutant heterogeneity suppresses its fixation probability; if this heterogeneity is strong enough, it can even completely offset the effects of selection (including in large populations). By contrast, resident heterogeneity has no effect on a mutant's fixation probability in large populations and can amplify it in small populations.
Collapse
|
49
|
Alcalde Cuesta F, González Sequeiros P, Lozano Rojo Á. Evolutionary regime transitions in structured populations. PLoS One 2018; 13:e0200670. [PMID: 30475815 PMCID: PMC6261048 DOI: 10.1371/journal.pone.0200670] [Citation(s) in RCA: 7] [Impact Index Per Article: 1.2] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/26/2018] [Accepted: 11/04/2018] [Indexed: 02/05/2023] Open
Abstract
The evolutionary dynamics of a finite population where resident individuals are replaced by mutant ones depends on its spatial structure. Usually, the population adopts the form of an undirected graph where the place occupied by each individual is represented by a vertex and it is bidirectionally linked to the places that can be occupied by its offspring. There are undirected graph structures that act as amplifiers of selection increasing the probability that the offspring of an advantageous mutant spreads through the graph reaching any vertex. But there also are undirected graph structures acting as suppressors of selection where this probability is less than that of the same individual placed in a homogeneous population. Here, firstly, we present the distribution of these evolutionary regimes for all undirected graphs with N ≤ 10 vertices. Some of them exhibit transitions between different regimes when the mutant fitness increases. In particular, as it has been already observed for small-order random graphs, we show that most graphs of order N ≤ 10 are amplifiers of selection. Secondly, we describe examples of amplifiers of order 7 that become suppressors from some critical value. In fact, for graphs of order N ≤ 7, we apply computer-aided techniques to symbolically compute their fixation probability and then their evolutionary regime, as well as the critical values for which they change their regime. Thirdly, the same technique is applied to some families of highly symmetrical graphs as a mean to explore methods of suppressing selection. The existence of suppression mechanisms that reverse an amplification regime when fitness increases could have a great interest in biology and network science. Finally, the analysis of all graphs from order 8 to order 10 reveals a complex and rich evolutionary dynamics, with multiple transitions between different regimes, which have not been examined in detail until now.
Collapse
Affiliation(s)
- Fernando Alcalde Cuesta
- Instituto de Matemáticas, Universidade de Santiago de Compostela, E-15782 Santiago de Compostela, Spain
- GeoDynApp - ECSING Group, E-15782 Santiago de Compostela, Spain
| | - Pablo González Sequeiros
- Departamento de Didácticas Aplicadas, Facultade de Formación do Profesorado, Universidade de Santiago de Compostela, Avda. Ramón Ferreiro s/n, E-27002 Lugo, Spain
- GeoDynApp - ECSING Group, E-15782 Santiago de Compostela, Spain
| | - Álvaro Lozano Rojo
- Centro Universitario de la Defensa, Academia General Militar, Ctra. Huesca s/n, E-50090 Zaragoza, Spain
- IUMA, Universidad de Zaragoza, Pedro Cerbuna 12, E-50009 Zaragoza, Spain
- GeoDynApp - ECSING Group, E-15782 Santiago de Compostela, Spain
| |
Collapse
|
50
|
Giaimo S, Arranz J, Traulsen A. Invasion and effective size of graph-structured populations. PLoS Comput Biol 2018; 14:e1006559. [PMID: 30419017 PMCID: PMC6258371 DOI: 10.1371/journal.pcbi.1006559] [Citation(s) in RCA: 13] [Impact Index Per Article: 2.2] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/07/2018] [Revised: 11/26/2018] [Accepted: 10/09/2018] [Indexed: 11/19/2022] Open
Abstract
Population structure can strongly affect evolutionary dynamics. The most general way to describe population structures are graphs. An important observable on evolutionary graphs is the probability that a novel mutation spreads through the entire population. But what drives this spread of a mutation towards fixation? Here, we propose a novel way to understand the forces driving fixation by borrowing techniques from evolutionary demography to quantify the invasion fitness and the effective population size for different graphs. Our method is very general and even applies to weighted graphs with node dependent fitness. However, we focus on analytical results for undirected graphs with node independent fitness. The method will allow to conceptually integrate evolutionary graph theory with theoretical genetics of structured populations. Evolving populations, companies, social circles are networks in which genes, resources and ideas circulate. Imagine a useful novelty is introduced in the network: a favorable mutation, a new product concept or a smart idea. Will this novelty be retained and propagated through the network or rather lost? Using tools originally devised for demographic research, we model the dynamics of the very initial spread of a useful novelty in a network. The network structure has a strong impact on these dynamics by affecting the effective network size through random effects. This effective network size, which correlates with the probability that a novelty spreads and is different from the actual size (i.e. number of nodes), varies with network structure. The effective size can even become independent of the actual network size and thus remain very small even for huge networks.
Collapse
Affiliation(s)
- Stefano Giaimo
- Evolutionary Theory Department, Max Planck Institute for Evolutionary Biology, Plön, Germany
- * E-mail:
| | - Jordi Arranz
- Evolutionary Theory Department, Max Planck Institute for Evolutionary Biology, Plön, Germany
| | - Arne Traulsen
- Evolutionary Theory Department, Max Planck Institute for Evolutionary Biology, Plön, Germany
| |
Collapse
|