Amplifiers and Suppressors of Selection for the Moran Process on Undirected Graphs

George Giakkoupis 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : We consider the classic Moran process modeling the spread of genetic mutations, as extended to structured populations by Lieberman et al. (Nature, 2005). In this process, individuals are the vertices of a connected graph G. Initially, there is a single mutant vertex, chosen uniformly at random. In each step, a random vertex is selected for reproduction with a probability proportional to its fitness: mutants have fitness r > 1, while non-mutants have fitness 1. The vertex chosen to reproduce places a copy of itself to a uniformly random neighbor in G, replacing the individual that was there. The process ends when the mutation either reaches fixation (i.e., all vertices are mutants), or gets extinct. The principal quantity of interest is the probability with which each of the two outcomes occurs. A problem that has received significant attention recently concerns the existence of families of graphs, called strong amplifiers of selection, for which the fixation probability tends to 1 as the order n of the graph increases, and the existence of strong suppressors of selection, for which this probability tends to 0. For the case of directed graphs, it is known that both strong amplifiers and suppressors exist. For the case of undirected graphs, however, the problem has remained open, and the general belief has been that neither strong amplifiers nor suppressors exist. In this paper we disprove this belief, by providing the first examples of such graphs. The strong amplifier we present has fixation probability 1 − ˜ O(n^ −1/3), and the strong suppressor has fixation probability ˜O(n^−1/4). Both graph constructions are surprisingly simple. We also prove a general upper bound of 1 − ˜Ω(n^−1/3) on the fixation probability of any undirected graph. Hence, our strong amplifier is existentially optimal.
Type de document :
Pré-publication, Document de travail
2016
Liste complète des métadonnées

Littérature citée [41 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01393044
Contributeur : George Giakkoupis <>
Soumis le : samedi 5 novembre 2016 - 23:57:11
Dernière modification le : mercredi 16 mai 2018 - 11:23:14
Document(s) archivé(s) le : lundi 6 février 2017 - 13:10:52

Fichier

moran-fixation.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01393044, version 1

Citation

George Giakkoupis. Amplifiers and Suppressors of Selection for the Moran Process on Undirected Graphs. 2016. 〈hal-01393044〉

Partager

Métriques

Consultations de la notice

261

Téléchargements de fichiers

106