Nejvíce citovaný článek - PubMed ID 38551989
Amplifiers of selection for the Moran process with both Birth-death and death-Birth updating
We examine population structures for their ability to maintain diversity in neutral evolution. We use the general framework of evolutionary graph theory and consider birth-death (bd) and death-birth (db) updating. The population is of size N. Initially all individuals represent different types. The basic question is: what is the time T N until one type takes over the population? This time is known as consensus time in computer science and as total coalescent time in evolutionary biology. For the complete graph, it is known that T N is quadratic in N for db and bd. For the cycle, we prove that T N is cubic in N for db and bd. For the star, we prove that T N is cubic for bd and quasilinear ( N log N ) for db. For the double star, we show that T N is quartic for bd. We derive upper and lower bounds for all undirected graphs for bd and db. We also show the Pareto front of graphs (of size N = 8 ) that maintain diversity the longest for bd and db. Further, we show that some graphs that quickly homogenize can maintain high levels of diversity longer than graphs that slowly homogenize. For directed graphs, we give simple contracting star-like structures that have superexponential time scales for maintaining diversity.
- Klíčová slova
- diversity, evolutionary dynamics, graphs, moran process, random walk,
- Publikační typ
- časopisecké články MeSH
Moran Birth-death process is a standard stochastic process that is used to model natural selection in spatially structured populations. A newly occurring mutation that invades a population of residents can either fixate on the whole population or it can go extinct due to random drift. The duration of the process depends not only on the total population size n, but also on the spatial structure of the population. In this work, we consider the Moran process with a single type of individuals who invade and colonize an otherwise empty environment. Mathematically, this corresponds to the setting where the residents have zero reproduction rate, thus they never reproduce. The spatial structure is represented by a graph. We present two main contributions. First, in contrast to the Moran process in which residents do reproduce, we show that the colonization time is always at most a polynomial function of the population size n. Namely, we show that colonization always takes at most [Formula: see text] expected steps, and for each n, we identify the slowest graph where it takes exactly that many steps. Moreover, we establish a stronger bound of roughly [Formula: see text] steps for undirected graphs and an even stronger bound of roughly [Formula: see text] steps for so-called regular graphs. Second, we discuss various complications that one faces when attempting to measure fixation times and colonization times in spatially structured populations, and we propose to measure the real duration of the process, rather than counting the steps of the classic Moran process.
- MeSH
- hustota populace MeSH
- lidé MeSH
- mutace MeSH
- počítačová simulace MeSH
- populační dynamika * MeSH
- selekce (genetika) MeSH
- stochastické procesy MeSH
- výpočetní biologie MeSH
- Check Tag
- lidé MeSH
- Publikační typ
- časopisecké články MeSH
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.
