Fixation times on directed graphs

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.Author summary: Populations of reproducing individuals evolve by accumulating mutations. When a single individual acquires a mutation, it takes some time until the mutation spreads across the population. Depending on the structure of the population, this so-called fixation time could be relatively short or exceedingly long. The structure of biological populations can be represented by graphs. The vertices of the graph denote individuals and the edges indicate possible reproductive events. Directed graphs are defined as those graphs that have some one-way edges. It is known that very long fixation times can arise for certain directed graphs. In this work, we consider a standard process of evolutionary dynamics. We show that for many directed graphs the fixation time is short. We show that fixation time is always short in the ecological scenario describing the spread of an invasive species in an ecosystem. We also show that while advantageous mutations generally fixate faster than neutral mutations, there are interesting exceptions. Finally, we provide concrete bounds for fixation time on any population structure. Those bounds serve as guarantees for simulation-based and computational explorations of the space of all directed graphs.