# Item

ITEM ACTIONSEXPORT

Released

Thesis

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

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

Cite as: https://hdl.handle.net/21.11116/0000-0001-546F-5

##### Abstract

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.

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.