1
|
Brewster DA, Nowak MA, Tkadlec J. Fixation times on directed graphs. PLoS Comput Biol 2024; 20:e1012299. [PMID: 39024375 DOI: 10.1371/journal.pcbi.1012299] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [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
|
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
|
3
|
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
|
4
|
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
|
5
|
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
|
6
|
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
|
7
|
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
|