Premium
Phase transitions of the Moran process and algorithmic consequences
Author(s) -
Goldberg Leslie,
Lapinskas John,
Richerby David
Publication year - 2020
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20890
Subject(s) - combinatorics , mathematics , vertex (graph theory) , bounded function , fixation (population genetics) , exponential function , discrete mathematics , random graph , chordal graph , graph , biology , mathematical analysis , biochemistry , gene
The Moran process is a random process that models the spread of genetic mutations through graphs. On connected graphs, the process eventually reaches “fixation,” where all vertices are mutants, or “extinction,” where none are. Our main result is an almost‐tight upper bound on expected absorption time. For all ϵ >0, we show that the expected absorption time on an n ‐vertex graph is o ( n 3+ ϵ ). Specifically, it is at mostn 3e O ( ( log log n ) 3 ) , and there is a family of graphs where it is Ω( n 3 ). In proving this, we establish a phase transition in the probability of fixation, depending on the mutants' fitness r . We show that no similar phase transition occurs for digraphs, where it is already known that the expected absorption time can be exponential. Finally, we give an improved fully polynomial randomized approximation scheme (FPRAS) for approximating the probability of fixation. On degree‐bounded graphs where some basic properties are given, its running time is independent of the number of vertices.