AG 1, AG 3, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

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.

Holger Dell

--email hidden

passcode not visible

logged in users only