Fixation times on directed graphs

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\ge 1$. Third, we identify a broad class of directed graphs with fast fixation times for any $r\ge 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.

22 pages, 5 figures

References in corpus (12)

• Evolutionary dynamics on any population structure
• Spatial model predicts dispersal and cell turnover cause reduced intra-tumor heterogeneity
• Voter Models on Heterogeneous Networks
• Most undirected random graphs are amplifiers of selection for Birth-death dynamics, but suppressors of selection for death-Birth dynamics
• Limits on amplifiers of natural selection under death-Birth updating
• Reproductive Value in Graph-structured Populations
• Transient amplifiers of selection and reducers of fixation for death-Birth updating on graphs
• Stochastic slowdown in evolutionary processes
• Approximating Fixation Probabilities in the Generalized Moran Process
• Environmental Evolutionary Graph Theory
• On the Fixation Probability of Superstars
• Environmental fitness heterogeneity in the Moran process

Cited by in corpus (1)

• Maintaining diversity in structured populations