Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Graphs on which evolution is more effective
Speaker:John Lapinskas
coming from:University of Oxford
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D3, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 28 June 2016
Duration:30 Minutes
Building:E1 4
The Moran process is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices, starting with a single mutant placed uniformly at random with some fixed fitness. If the underlying graph is strongly connected then the algorithm will eventually reach either fixation, in which all individuals are mutants, or extinction, in which no individuals are mutants. An infinite family of directed graphs is said to be "strongly amplifying" if for any fixed (beneficial) fitness, the extinction probability tends to 0 as the number of vertices increases. Strong amplification is a rather surprising property — it means that beneficial mutations propagate to the entire population with probability tending to 1 even though the initial mutant only has a fixed selective advantage. We give the first rigorous proof that there is a strongly amplifying family of directed graphs ("megastars"), with fixation probability roughly 1 - n^{-1/2}. We also prove that the other candidates extant in the literature give substantially lower fixation probabilities.
Name(s):Holger Dell
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Holger Dell, 06/21/2016 04:37 PM
Last modified:
Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Holger Dell, 06/21/2016 04:37 PM -- Created document.