Transcript Evolutionary Graph Theory - National University of Singapore

Evolutionary Graph Theory
Uses of graphical framework
• Graph can represent relationships in a social
network of humans
• E.g. “Six degrees of separation”
George:
David’s
college
mate
You
Dad
David:
dad’s
friend
from
US
Michelle
George’
s wife
Mr. Obama
Uses of graphical framework
• It can also analyze the effect of population
structure on evolutionary dynamics…
The Basic Idea
wij
i
j
wij
i
j
• Vertices – individuals
in a population
• Edge – competitive
interaction
• wij = Probability that
an offspring of i
replaces j
• Edge can go both
directions and so
describes a digraph
The Basic Idea
• Label all the individuals in the population with
i=1,2,…,N
• Represent each with a vertex
• At each time step, choose a random individual
for reproduction
• Determine direction of edge
• Every edge has weight = wij
– wij >0 → an edge from i to j
– Wij =0 → no edge from i to j
• Hence process determined by W=[wij]; 0< wij <1
• The matrix W defines a weighted digraph
Moran Process
• Consider a homogeneous
population of size N
consisting of residents (white)
and mutants (black).
Moran Process
• At each time step, choose an
individual for reproduction
with a probability proportional
to its fitness
• Here, a resident is selected
for reproduction
Moran Process
• A randomly chosen individual
is eliminated
• Here, a mutant is selected for
death
Moran Process
• The offspring replaces
the eliminated individual.
Why Moran Process?
• Represents the simplest
possible stochastic model to
study selection in a finite
population
• Where 2 individuals are
chosen at each time step
• One for reproduction & one
for elimination
• Offspring of first replaces the
second
• Total population size, N, is
strictly constant
Moran Process
• Represented by a complete
graph with identical
weights
• An unstructured population is
given by a complete graph:
an edge btw any 2 vertices
• Evolutionary process is
equivalent to the Moran
process
Moran Process
• Fixation probability: probability that a mutant invading
a population of N -1 residents will produce a lineage that
takes over the whole population
• Fixation probability α evolution rate
• Suppose
 all resident individuals are identical and one new
mutant is introduced
 new mutant has relative fitness r, as compared to the
residents, whose fitness is 1
• Fixation probability of the mutant is then given by:
 R = (1-1/r)/(1-1/rN)
Evolutionary Suppressors
• Line
• Burst
The line
• Suppose N individuals are arranged in a linear chain:
• Each individual places its offspring into the position
immediately to its right.
• The leftmost individual is never replaced.
• Mutant can only reach fixation if it arises in the
leftmost position, which happens with probability
1/N.
• Fixation probability = 1/N, independent of r
The Burst
• A new mutant can only reach fixation if it arises
in the center:
• Probability that a randomly placed mutant
originates in the center = 1/N
• Hence fixation probability is again independent of
r, the relative fitness of the new mutant
• Represent suppressors of selection
• All mutants – irresp of their fitness – have the
same fixation probability as a neutral
mutant in the Moran process
Evolutionary Amplifiers
• Star
• Superstar
The Star
• For a large N, a mutant with
a relative fitness r has a
fixation probability
• ρ = (1-1/r2)/(1-1/r2N).
• So, a relative fitness r on a
star is equivalent to a
relative fitness r2 in the
Moran process
• Thus, a star is an amplifier
of selection
The Superstar
•
•
•
•
l=5
k=3
m=5
l= no. of leaves
m= no. of loops in a leaf
k= the length of each loop
for sufficiently large N, a
super-star of parameter k
satisfies:
• Fixation probability
• The superstar amplifies a
selective difference r to rk
• A powerful amplifier of
selection!
References
• Nowak, Martin A. “Evolutionary Graph Theory.”
Evolutionary Dynamics: exploring the equations of
life. Cambridge, Massachusetts, and London :
Belknap Press of Harvard University Press, 2006:
123-144.
• Graph images from: Lieberman, Erez and Hauert ,
Christoph and Nowak, Martin A. “Evolutionary
dynamics on graphs.” Nature. 433 (2005): 312-316.
• Image in slide #3 from:
http://en.wikipedia.org/wiki/6_degrees_of_separati
on