Phase transitions of the Moran process and algorithmic consequences

Leslie Ann Goldberg, John A Lapinskas, David Richerby

Research output: Contribution to journalArticle (Academic Journal)peer-review

Abstract

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 most n3eO((log log n)3), and there is a family of graphs where it is Ω(n3). In proving this, we establish a phase transition in the probability of fixation, depending on 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 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.
Original languageEnglish
Pages (from-to)597-647
JournalRandom Structures and Algorithms
Volume56
Issue number3
Publication statusPublished - 28 Oct 2019

Structured keywords

  • Algorithms and Complexity

Keywords

  • Moran process
  • evolutionary dynamics
  • absorption time
  • fixation probability

Fingerprint

Dive into the research topics of 'Phase transitions of the Moran process and algorithmic consequences'. Together they form a unique fingerprint.

Cite this