Phase transitions of the Moran process and algorithmic consequences
From MaRDI portal
Publication:5113950
DOI10.1002/RSA.20890zbMATH Open1444.92072arXiv1804.02293OpenAlexW2982391597MaRDI QIDQ5113950FDOQ5113950
John Lapinskas, David Richerby, Leslie Ann Goldberg
Publication date: 19 June 2020
Published in: Random Structures \& Algorithms (Search for Journal in Brave)
Abstract: The Moran process is a random process that models the spread of genetic mutations through graphs. If the graph is connected, the process eventually reaches "fixation", where every vertex is a mutant, or "extinction", where no vertex is a mutant. Our main result is an almost-tight bound on expected absorption time. For all epsilon > 0, we show that the expected absorption time on an n-vertex graph is o(n^(3+epsilon)). In fact, we show that it is at most n^3 * exp(O((log log n)^3)) and that there is a family of graphs where it is Omega(n^3). In the course of proving our main result, we also establish a phase transition in the probability of fixation, depending on the fitness parameter r of the mutation. We show that no similar phase transition occurs for digraphs, where it is already known that the expected absorption time can also be exponential. Finally, we give an improved FPRAS for approximating the probability of fixation. Its running time is independent of the size of the graph when the maximum degree is bounded and some basic properties of the graph are given.
Full work available at URL: https://arxiv.org/abs/1804.02293
Cited In (4)
- A survey of the modified Moran process and evolutionary graph theory
- Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process
- An extension of the Moran process using type-specific connection graphs
- Towards the prediction of critical transitions in spatially extended populations with cubical homology
This page was built for publication: Phase transitions of the Moran process and algorithmic consequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113950)
