Evolutionary Graph Theory

16 Oct 2024, 09:00 → 18 Oct 2024, 17:00 Europe/Berlin

Researchers in evolutionary graph theory come from diverse backgrounds, covering applied mathematics, theoretical computer science, population genetics, theoretical physics, and experimental evolution.
As a result, motivations and research directions within the field are equally diverse.
We aim for a focused meeting, bringing the scientists in evolutionary graph theory together.

The workshop should allow for sharing recent advances in the field and set the course for the future.
This meeting can also be envisioned as the "Future of Evolutionary Graph Theory" gathering.

Venue: Max Planck Institute for Evolutionary Biology, Plön, Germany.

Confirmed speakers are:

• Anne-Florence Bitbol,  EPFL, Switzerland
• Mark Broom, City University of London, UK        
• Oana Carja, Carnegie Mellon University, USA
• Christoph Hauert, University of British Columbia, Canada      
• Rees Kassen, McGill University, Canada    
• Joachim Krug, University of Cologne, Germany   
• Natalia Komarova, University of California, San Diego, USA
• Andreas Pavlogiannis, Aarhus University, Denmark
• Cornelia Pokalyuk, University of Lübeck, Germany
• Josef Tkadlec, Charles University, Czech Republic  

 

Organizers: Nikhil Sharma (MPI Plön) and Arne Traulsen (MPI Plön).

Wednesday 16 October

09:15 Registration and Coffee

1 Welcome note and introduction to Evolutionary Graph Theory at MPI Plön

Speaker: Arne Traulsen

Session: 1

Convener: Arne Traulsen (MPI for Evolutionary Biology)

2 20th Anniversary of Evolutionary Amplifiers

A review of the discovery of the surprising dynamical properties of evolutionary amplifiers (Lieberman, Hauert & Nowak, 2005). In the spatial Moran process the geometrical arrangement of individuals can have surprising effects on the evolutionary dynamics. The key determinants of the evolutionary process in finite populations are the fixation probabilities and times. Both can be significantly affected by the geometrical arrangement of individuals. This contrasts and indeed refutes the conjectures by Maruyama (1970) and Slatkin (1981) stating that fixation probabilities are independent of population structure. Most intriguingly, the geometrical arrangement of individuals alone can amplify selection and suppress random drift. In fact, for strong amplifiers the fixation probability converges to certainty for beneficial mutants with an arbitrarily small advantage over the resident and sufficiently large structures. This claim was later challenged for the super-star graph (Diaz et al. 2013). The resolution turned out to be unexpectedly challenging but revealed further interesting and fairly subtle dynamical features of the super-star graph (Jamieson-Lane & Hauert, 2015).

Speaker: Christoph Hauert (University of British Columbia)

3 Discussion: A brief overview of EGT + 2 questions.

Speaker: Nikhil Sharma (MPI for Evolutionary Biology)

12:30 Lunch

Session: 2

Convener: Nikhil Sharma (MPI for Evolutionary Biology)

4 Fixation times of the Moran process

Moran process is a classic random process that models the competition of two or more types of individuals on a network-structured population. The individuals reproduce, the offspring migrate along the edges of the network, and they replace the neighbors. In the absence of mutation, one of the types eventually triumphs over the whole network. We survey the existing results on the time (that is, the number of steps of the Moran process) until this occurs. We consider various regimes (directed vs. undirected networks, neutral vs. strong selection, Birth-death vs. death-Birth updating) and highlight some outstanding open questions.

Speaker: Josef Tkadlec (Charles University, Prague)

5 Fixation time in Moran process under strong selection

Lenka Kopfová, Josef Tkadlec

We study modified version of the Moran process that corresponds to the strong selection, as in the dynamics of invasive species. In this process, only the mutant individuals spread and eventually conquer the whole population. The key quantity that we study is the so-called fixation time, which is the expected time until all individuals become mutants. We give tight upper and lower bounds for fixation time on a general population structure and refine them for some classes. Additionally, we compute the precise fixation times on some specific population structures.

Speaker: Lenka Kopfova (ISTA)

6 Fixation times on directed graphs

David Brewster, Martin Nowak, Josef Tkadlec

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.

Speaker: David Brewster (Harvard University)

7 Amplifiers of selection for the Moran process with both Birth-death and death-Birth updating

Jakub Svoboda, Soham Joshi, Josef Tkadlec, Krishnendu Chatterjee

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\in(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.

Speaker: Jakub Svoboda (ISTA)

15:20 Coffee Break

Session: 3

Convener: Jakub Svoboda (ISTA)

8 Maximizing the Fixation Probability: Optimization Problems in EGT

Suppose that mutant invasion starts with $k$ mutants distributed over a population structure. Which $k$ locations should we choose for the initial mutants so as to maximize their fixation probability?

In another setting, suppose that selection pressure is only present on a few locations in a population structure, therefore mutants have an advantage only when reproducing on these locations. Suppose, also, that we can control which locations feel the selection. Alas, we cannot choose all locations, but only $k$ of them. Which $k$ locations should we choose so as to maximize the fixation probability of a randomly arising mutant?

Optimization questions like the above are standard in popular stochastic diffusion models such as in SIR and IC/IM, but have not been studied in the context of EGT. In this talk, I will present some of our early steps in this direction, including exciting results we proved, and annoying questions that persisted our efforts.

Speaker: Andreas Pavlogiannis (Aarhus University)

9 Seed Selection in the Heterogeneous Moran Process

Petros Petsinis, Andreas Pavlogiannis, Josef Tkadlec, Panagiotis Karras

The Moran process is a classic stochastic process that models the rise and takeover of novel traits in network-structured populations. In biological terms, a set of mutants, each with fitness m∈(0,∞) invade a population of residents with fitness 1. Each agent reproduces at a rate proportional to its fitness and each offspring replaces a random network neighbor. The process ends when the mutants either fixate (take over the whole population) or go extinct. The fixation probability measures the success of the invasion. To account for environmental heterogeneity, we study a generalization of the Standard process, called the Heterogeneous Moran process. Here, the fitness of each agent is determined both by its type (resident/mutant) and the node it occupies. We study the natural optimization problem of seed selection: given a budget k, which k agents should initiate the mutant invasion to maximize the fixation probability? We show that the problem is strongly inapproximable: it is NP-hard to distinguish between maximum fixation probability 0 and 1. We then focus on mutant-biased networks, where each node exhibits at least as large mutant fitness as resident fitness. We show that the problem remains NP-hard, but the fixation probability becomes submodular, and thus the optimization problem admits a greedy (1−1/e)-approximation. An experimental evaluation of the greedy algorithm along with various heuristics on real-world data sets corroborates our results. (Optinal Talk Presentation) (Arxiv version: https://arxiv.org/pdf/2404.15986)

Speaker: Petros Petsinis (Aarhus University)

10 Mathematical modeling of spatial evolution: biomedical applications

Evolutionary dynamics are sensitive to the type of ecological interactions that drive reproduction and death. In this talk I will discuss how spatial interactions may change the laws of evolution. First I will describe spatial invasion dynamics and derive a number of scaling laws that describe the growth of disadvantageous, neutral, and advantageous mutants in growing populations. Applications of these laws to bacterial growth and carcinogenesis will be discussed. I will then talk about spatial enemy-victim dynamics. The literature about mutant invasion and fixation typically assumes populations to exist in isolation from their ecosystem. Yet, populations are part of ecological communities, and enemy-victim (e.g. pathogen-host) interactions are particularly common. I will use spatially explicit, computational pathogen-host models (with wild-type and mutant hosts) to re-visit the established theory about mutant fixation, where the pathogen equally attacks both wild-type and mutant individuals. Mutant fitness is assumed to be unrelated to infection. I will show that pathogen presence substantially weakens selection, increasing the fixation probability of disadvantageous mutants and decreasing it for advantageous mutants. A mathematical approach of coarse-grained approximation can be used to shed light onto this finding, which has relevance for phage therapies and antibiotic resistance. These results imply that the deleterious mutant burden in natural populations might be higher than expected from traditional theory.

Speaker: Natalia Komarova (University of California, San Diego)

18:00 Dinner

11 Discussion: Finalizing the 2 questions

Thursday 17 October

Session: 4

Convener: Diogo Pires (City, University of London)

12 Mutant fate in deme-structured populations on graphs

Evolutionary graph theory has shown that population structure can strongly impact evolution, in particular by affecting the fixation probability of mutants. Natural microbial populations often have complex spatial structures, where these effects can be crucial. However, making the link with update rules is not always easy. We proposed a model for describing deme-structured populations on graphs, with a well-mixed deme on each node of the graph. By tuning migration asymmetry in the rare migration regime, the star graph transitions from amplifying to suppressing natural selection, and the predictions of evolutionary graph theory are recovered for specific migration asymmetries. When increasing the frequency of migrations, suppression of selection becomes pervasive. Our model also provides an advance toward connecting theoretical predictions to recent experiments considering spatially structured populations.

Speaker: Ann-Florence Bitbol (EPFL, Switzerland)

13 Spatial structure facilitates evolutionary rescue by cost-free drug resistance

Cecilia Fruet, Ella Müller, Claude Loverdo, Anne-Florence Bitbol

A population composed only of drug-sensitive bacteria cannot survive the addition of a biostatic drug at a sufficiently high concentration and for sufficiently long. However, if at least one resistant bacterium is present before drug addition, it can lead to population rescue through resistance. How does spatial structure impact the survival of a bacterial population upon biostatic drug addition? We considered a minimal individual based model, starting with only sensitive bacteria, and focused on de novo appearance of resistance, with resistant mutants arising from mutations upon division. When including a substantial fitness cost of resistance, we did not observe any impact of structure in our minimal model. Therefore, we focused on neutral resistance mutations. This case is relevant because resistance mutations are often effectively neutral, e.g. at low drug concentrations. As a minimal model of spatial structure, we considered a clique structure with per-capita migration rate γ. This structure becomes a well-mixed population for large γ, and a fully structured population with isolated demes if γ is zero.

We found that the probability that the population survives upon biostatic drug application after a variable amount of time is affected by population structure. This is due to the different system composition for the different population structures at a given time. Although the survival probability is maximum in the structured population at all times, once the drug is applied, the demes that have no preexisting resistant mutants will go extinct. Conversely, as soon as one allows bacteria to migrate, mutants can spread in the whole system. We calculated analytically the time to colonize the next deme due to migrations, allowing us to compare timescales in the process. Overall, we found that in a minimal model, spatial structure can favor the survival of a bacterial population by de novo resistance upon application of a biostatic drug. Our main conclusions also extend to biostatic drugs and to other structures (lattice, star).

Speaker: Cecilia Fruet (EPFL)

14 Bridging Wright-Fisher and Moran models

Arthur Alexandre, Alia Abbara, Cecilia Fruet, Claude Loverdo, Anne-Florence Bitbol

The Wright-Fisher model and the Moran model are both widely used in population genetics. They describe the time evolution of the frequency of an allele in a well-mixed population with fixed size. We propose a simple and tractable model which bridges the Wright-Fisher and the Moran descriptions. We assume that a fixed fraction of the population is updated at each discrete time step. In this model, we determine the fixation probability of a mutant in the diffusion approximation, as well as the effective population size. We generalize our model, first by taking into account fluctuating updated fractions or individual lifetimes, and then by incorporating selection on the lifetime as well as on the reproductive fitness.

Speaker: Arthur Alexandre (EPFL)

15 Mutant dynamics in spatially structured populations: the role of non-mixing and mixing transfer strategies

Ernesto Berríos-Caro and Hildegard Uecker

Meta-populations often exhibit complex spatial structures. Migration between environments plays a crucial role in shaping mutant dynamics. Motivated by bacterial evolution experiments, we develop a model of spatially structured populations on graphs, incorporating between-deme migration and periodic bottlenecks. We explore two key scenarios: one without mixing between demes, where bottlenecks occur independently within each deme, and another with mixing, where meta-populations from different demes are pooled together prior to bottlenecks. We find that mixing offers no advantage to mutants in the absence of interactions between wildtype and mutant sub-populations. Through a branching process approach, we demonstrate that the establishment probability is identical in both scenarios. Differences arise when interactions between sub-populations are introduced. We examine two types of interactions: competition during growth, driven by resource availability, and competition during bottlenecks, where a fixed bottleneck size limits population numbers. Notably, differences between non-mixing and mixing scenarios become apparent only when stochastic effects are considered, either in the population growth or bottlenecks. We explore approaches where one of the sources is stochastic while the other is deterministic. Our results offer insights into how spatial structure and stochastic effects shape evolutionary dynamics, opening avenues for direct experimental validation.

Speaker: Ernesto Berríos-Caro (MPI for Evolutionary Biology)

10:50 Coffee Break

Session: 5

Convener: Arthur Alexandre (EPFL, Lausanne)

16 Network topology accelerates adaptive evolution and increases genetic parallelism in experimental metapopulations of Pseudomonas aeruginosa

Natural populations are often spatially structured, meaning they are best described as metapopulations composed of subpopulations connected by migration. We know little about how the topology of connections in metapopulations impacts adaptive evolution. Models based on evolutionary graph theory suggest topologies that concentrate dispersing individuals through a central hub can accelerate adaptation above that of a well-mixed system, however empirical support is lacking. We provide experimental support for this claim and show acceleration is accompanied by high rates of parallel evolution resulting from a reduced probability that rare beneficial mutations are stochastically lost. Our results suggest metapopulation topology can be a potent force driving evolutionary dynamics and patterns of genomic repeatability in structured landscapes such as those involving the spread of pathogens or invasive species.

Speaker: Rees Kassen (McGill University)

17 An extension to the Moran Process to account for variable population sizes

George Berry, Christoph Hauert

We investigate an extension to the Moran process which adds ecological aspects through variable population sizes. For the original Moran process, birth and death events are correlated to maintain a constant population size. Here we decouple the two events and derive the stochastic differential equation that represents the dynamics in a well-mixed population and captures its behaviour as the population size becomes arbitrarily large. In evolutionary graph theory, two key determinants of the evolution processes are fixation probabilities and fixation times. While those are preserved for a large class of structures, some structures have been identified that act as ‘amplifiers’ of selection which suppress random drift and others that are ‘suppressors’ of selection which promote random drift. However, these features are crucially dependent on the sequence of events, such as birth-death vs death-birth – a seemingly small change with significant consequences. In our extension of the Moran process this distinction is no longer necessary or possible. Furthermore, ‘fixation’ means that only one trait remains, but ecological fluctuations will continue. We report the fixation probabilities and times for the well-mixed population, circulation graphs as well as amplifiers and suppressors, and compare them to the original Moran process.

Speaker: George Berry (University of British Columbia)

12:40 Lunch

Session: 6

Convener: Cecilia Fruet (EPFL, Lausanne)

18 Invasion of cooperative parasites in structured host populations

Certain defense mechanisms of phages against the immune system of their bacterial host rely on cooperation of phages. Motivated by this example we analysed in [BP] the spread of cooperative parasites in host populations that were structured according to a configuration model. Building on these results we consider the case of a host population which is (genuinely spatially) structured according to a random geometric graph. We identify the spatial scale at which invasion of parasites turns from being an unlikely to a highly probable event and give in the critical regime upper and lower bounds on the invasion probability.
This talk is based on joint work with Vianney Brouard, Marco Seiler and Hung Tran.

[BP] V. Brouard and C. Pokalyuk., Invasion of parasites in moderately structured host populations, Stoch. Proc. Appl., 153, pp 221-263 (2022)
[BPST] V. Brouard, C. Pokalyuk, M. Seiler and H. Tran. Spatial Invasion of Cooperative Parasites, Theor. Popul. Biol., 159, pp 35-58 (2024)

Speaker: Cornelia Pokalyuk (University of Lübeck)

Discussion Session: 1

19 Small groups + Joint discussion

18:00 Dinner

Session: 7

Convener: George Berry (University of British Columbia)

20 Clonal interference, genetic variation and the speed of evolution in structured populations

Speaker: Oana Carja (Carnegie Mellon University)

Friday 18 October

Session: 8

Convener: Natalia Slyeptsova (University of Liverpool)

21 The role of deleterious mutations in spatial and graph-structured populations

The adaptation of a population to a novel environment proceeds through the fixation of beneficial mutations and the purging of deleterious ones. Although most novel mutations are deleterious, in well-mixed populations their effects become largely negligible at large population size. By contrast, in structured populations deleterious mutations can dominate the behavior even in the limit of infinite size. In the first part of the talk I will explain this phenomenon in the context of Muller's ratchet in spatial habitats. I then move on to graph-structured populations undergoing either (stochastic) origin-fixation dynamics or (deterministic) mutation-selection dynamics. In both settings, we have identified classes of graph structures for which the effect of deleterious mutations persists or even dominates in large populations. Specifically, these are amplifiers of fixation (on which deleterious mutations fix with finite probability in the limit of infinite population size) and amplifiers of mutation (which display a nonzero mutational load at mutation-selection balance in the limit of vanishing mutation rate). The talk is based on joint work with Suman Das, Jakub Otwinowski, Su-Chan Park, Nikhil Sharma and Arne Traulsen.

Speaker: Joachim Krug (University of Cologne)

Discussion Session: 2

22 Small groups and joint discussion

13:00 Lunch

Session: 9

Convener: David Brewster (Harvard University)

23 Evolutionary graph theory: when is an evolutionary process equivalent to the Moran process?

Evolution in finite populations is often modelled using the classical Moran process and this methodology has been extended to structured populations using evolutionary graph theory. An important question in any such population is whether a rare mutant has a higher or lower fixation probability than the Moran probability, i.e. that from the original Moran model, which represents an unstructured population. As evolutionary graph theory has developed, different ways of considering the interactions between individuals through a graph and an associated matrix of weights have been considered, as have a number of important dynamics. In this talk we discuss the general criteria for when an evolutionary graph with general weights satisfies the Moran probability for a set of six common evolutionary dynamics.

Speaker: Mark Broom (City, University of London)

24 Multiplayer cooperation in networks of communities

Diogo L. Pires, Mark Broom

Community organization permeates both social and biological complex systems. To study its interplay with behavior emergence, we model mobile structured populations with multiplayer interactions. We derive general analytical methods for evolutionary dynamics under high home fidelity when populations self-organize into networks of asymptotically isolated communities. In this limit, community organization dominates over the network structure and emerging behavior is independent of network topology. We obtain the rules of multiplayer cooperation in networks of communities for different types of social dilemmas. The success of cooperation is a result of the benefits shared amongst communal cooperators outperforming the benefits reaped by defectors in mixed communities. Under weak selection, cooperation can evolve and be stable for any size and number of communities if the reward-to-cost ratio of public goods is higher than a critical value. Community organization is a solid mechanism for sustaining the evolution of cooperation under public goods dilemmas, particularly when populations are organized into a higher number of smaller communities. Commons dilemmas hold mixed results but tend to favour cooperation under larger communities. The results obtained in these two types of multiplayer social dilemmas suggest a fundamental difference between those focused on production (public goods dilemmas) and those related to the fair consumption of a preexisting resource (commons dilemmas).

Speaker: Diogo Pires (City, University of London)

25 Natural death rate drives star graphs from amplifiers to suppressors of natural selection

Natalya Slyeptsova, Christopher Overton

Evolutionary graph theory (EGT) considers evolutionary dynamics in a structured population that is represented by a graph. Fixation probability is a measure of probability that a mutation takes over the resident population. One of the major questions EGT tries to answer is how the graph structure impacts the fixation probability. It has been found that certain graphs can act as amplifiers or suppressors of selection. However, the type of update rule used in the model can impact this result. For example, the star graph is an amplifier for birth-death with fitness on birth (Bd) dynamics and is a suppressor for death-birth with fitness on birth (dB) dynamics. Typically, EGT has focused on discrete time models, which can be hard to link with realistic population dynamics. Recently, these discrete time models have been generalized to a continuous time Markov-process model based on eco-evolutionary dynamics, where the results for dB and Bd dynamics can be recreated by suppressing the ecological dynamics. This work shows that within this continuous time framework, there exists a continuous transition from Bd to dB results. Therefore, the interplay between the underlying biological parameters of birth rate, death rate, and competition, will drive the qualitative shift from amplifier (under Bd) to suppressor (under dB). Using the star graph as an example, we prove that the transition from Bd to dB depends on the magnitude of the natural death rate. By increasing the natural death rate of individuals, population structures that typically amplify selection under Bd dynamics can be driven to suppress fixation. Exploring the fundamental drivers behind this qualitative shift will provide further insights into whether population structures will amplify or suppress selection under realistic population dynamics. I am also happy to considered for a poster, if there are no more spots available for talks.

Speaker: Natalia Slyeptsova (University of Liverpool)

26 Evolutionary bet-hedging in structured populations

Kieran Sharkey, Chris Overton

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.

Speaker: Kieran Sharkey (University of Liverpool)

15:50 Farewell