The effect of graph structure on the dynamics of a stochastic evolutionary 
process

Hindersin, Laura

FreigabegeschichteDetailsÜbersicht

The effect of graph structure on the dynamics of a stochastic evolutionary process

Hindersin, L. (2018). The effect of graph structure on the dynamics of a stochastic evolutionary process. PhD Thesis, University of Lübeck, Lübeck.

Item is Freigegeben

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:

Datensatz-Permalink: https://hdl.handle.net/21.11116/0000-0001-546F-5 Versions-Permalink: https://hdl.handle.net/21.11116/0000-0003-F496-0

Genre: Hochschulschrift

ausblenden:

Urheber:
Hindersin, Laura¹, Autor
Traulsen, Arne¹, Gutachter

Affiliations:
1Department Evolutionary Theory, Max Planck Institute for Evolutionary Biology, Max Planck Society, ou_1445641

Inhalt

einblenden:

ausblenden:

Schlagwörter: -

Zusammenfassung: Evolutionary graph theory is the study of how spatial population structure
affects evolutionary processes. The nodes of the graph are inhabited by individuals,
e.g. cells. The links between nodes represent possibilities for these
individuals to spread. We study the Moran process, where there is one birth
and death event per time step. In the most commonly used updating mechanism,
birth happens with probability proportional to the individual’s fitness.
The individual giving birth then randomly replaces one of its neighbors by an
identical copy of itself. Initially, the network is inhabited entirely by wild-type
individuals with fitness 1 and one mutant with relative fitness r > 0. One
interesting property of this system is the probability with which the mutant
will give rise to a lineage that takes over the whole network, the so-called
fixation probability. There are certain networks that can increase or decrease
this probability compared to the unstructured case, called amplifiers and suppressors
of selection, respectively.
We find that most small undirected random graphs are amplifiers of selection.
If we however change the updating rule to remove a random individual
first and subsequently let its neighbors compete for the empty slot according
to their fitness, this completely changes the result. Under death-birth
updating, almost all undirected random graphs are suppressors of selection.
Another evolutionary outcome of interest is the expected time this process
takes until the mutants fixate in the population. Since it is known that certain
amplifier graphs also increase the time to fixation, we are interested in the
specific effect of graph structure on fixation time. We show that this fixation
time can both increase or decrease when removing a link from a graph.
Often, the fixation probability and time are either calculated analytically
for simple cases or simulated for larger or more complicated graphs. We
use standard Markov chain methods to numerically solve the system which
has advantages over both analytical calculations and simulations. For this,
we provide code to automate the part of creating the transition matrix for
arbitrary graph structure.
Lastly, we apply this abstract model to a conceptual question in biology,
namely to cancer initiation. We are interested to find a graph which would
provide an optimal tissue structure to prevent cancer mutations from spreading
through the whole graph. Surprisingly, we conclude that it is not always
the strongest suppressor of selection that works best at preventing this. But
instead it highly depends on the fitness distribution of newly arising mutations
and on the detailed update mechanism.

Details

einblenden:

ausblenden:

Sprache(n): eng - English

Datum: Angenommen: 2018-02-20Erschienen: 2018-02-20

Publikationsstatus: Erschienen

Seiten: 105

Ort, Verlag, Ausgabe: Lübeck : University of Lübeck

Inhaltsverzeichnis: Contents
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Evolutionary graph theory . . . . . . . . . . . . . . . . . . . . 3
1.2.1 The Moran process . . . . . . . . . . . . . . . . . . . . 3
1.2.2 The Moran process on graphs . . . . . . . . . . . . . . 5
1.2.3 Amplification and suppression of selection . . . . . . . 6
1.3 Contribution of this thesis . . . . . . . . . . . . . . . . . . . . 9
2 Counterintuitive properties of the fixation time 11
2.1 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 The Moran process in well-mixed populations . . . . . 13
2.2.2 The Moran process in structured populations . . . . . 14
2.2.3 A general approach to calculate probabilities and times
of fixation . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.1 Analytical results for small networks . . . . . . . . . . 17
2.3.2 Numerical simulations for larger networks . . . . . . . 28
2.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3 Amplifiers and suppressors of selection 33
3.1 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3.1 Fixation probabilities in well-mixed populations . . . . 36
3.3.2 Numerical procedure . . . . . . . . . . . . . . . . . . . 38
3.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4.1 Birth-death . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4.2 death-Birth . . . . . . . . . . . . . . . . . . . . . . . . 43
3.4.3 Directed graphs . . . . . . . . . . . . . . . . . . . . . . 46
3.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4 Numerical method and algorithm 51
4.1 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3 Software description . . . . . . . . . . . . . . . . . . . . . . . 53
4.3.1 Computing the transition matrix from the adjacency
matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3.2 Fixation probability . . . . . . . . . . . . . . . . . . . 55
4.3.3 Fixation time . . . . . . . . . . . . . . . . . . . . . . . 56
4.3.4 Computational limitations and performance . . . . . . 58
4.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5 Application to a question in cancer initiation 63
5.1 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.3 Fixation of novel mutations . . . . . . . . . . . . . . . . . . . 66
5.4 The distribution of fitness effects of cancer mutations . . . . . 69
5.5 Population structures and their effect on fixation probabilities 72
5.6 Double mutations . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6 Discussion 81
6.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.2 Open questions . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.3 Applicability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Bibliography 91

Art der Begutachtung: -

Identifikatoren: Anderer: Diss/12914

Art des Abschluß: Doktorarbeit