The Kingman Coalescent as aDensity on a Space of Trees
Lena Walter
Freie Universität Berlin
July 31st, 2018
joint work with Christian Haase

Contents
1

The Kingman n-coalescent

2

Space of Trees

3

A Density

4

Connection to Tropical Geometry

5

Further Directions

Contents
1

The Kingman n-coalescent

2

Space of Trees

3

A Density

4

Connection to Tropical Geometry

5

Further Directions

The Kingman n-coalescent

The Kingman n-coalescentpopulation genetic model:

The Kingman n-coalescentpopulation genetic model:
Wright-Fisher 30’s

The Kingman n-coalescentpopulation genetic model:
Wright-Fisher 30’s
fixed population size

The Kingman n-coalescentpopulation genetic model:
Wright-Fisher 30’s
fixed population size
non-overlapping
generations

The Kingman n-coalescentpopulation genetic model:
Wright-Fisher 30’s
fixed population size
non-overlapping
generations
no recombination

The Kingman n-coalescentpopulation genetic model:
Wright-Fisher 30’s
→ sample n individuals froma population of N

The Kingman n-coalescentpopulation genetic model:
Wright-Fisher 30’s
→ sample n individuals froma population of N
→ trace ancestry backwards
in timeThe Kingman n-coalescentpopulation genetic model:
Wright-Fisher 30’s
→ sample n individuals froma population of N
→ trace ancestry backwards
in timeThe Kingman n-coalescentpopulation genetic model:
Wright-Fisher 30’s
→ sample n individuals froma population of N
→ trace ancestry backwards
in timeThe Kingman n-coalescentpopulation genetic model:
Wright-Fisher 30’s
→ sample n individuals froma population of N
→ trace ancestry backwards
in timeThe Kingman n-coalescentpopulation genetic model:
Wright-Fisher 30’s
→ sample n individuals froma population of N→ trace ancestry backwards
in timeMRCA (Most Recent Common Ancestor)?

The Kingman n-coalescent
MRCA (Most Recent CommonAncestor)?
Consider two lineages:

The Kingman n-coalescent
MRCA (Most Recent CommonAncestor)?
Consider two lineages:
P(c. 1 generation ago) = N1

The Kingman n-coalescent
MRCA (Most Recent CommonAncestor)?
Consider two lineages:
P(c. 1 generation ago) = N1
P(c. 2 generations ago) = 1 − N1

 1N

The Kingman n-coalescent
MRCA (Most Recent CommonAncestor)?
Consider two lineages:
P(c. 1 generation ago) = N1P(c. 2 generations ago) = 1 − N1..
.
P(c. t generations ago) =t−1 1
1 − N1N

 1N

The Kingman n-coalescent
MRCA (Most Recent CommonAncestor)?
Consider two lineages:
P(c. 1 generation ago) = N1
P(c. 2 generations ago) = 1 − N1..
.
P(c. t generations ago) =t−1 1
1 − N1N→ geometric distribution

 1N

The Kingman n-coalescent
MRCA (Most Recent CommonAncestor)?
Consider two lineages:
P(c. 1 generation ago) = N1P(c. 2 generations ago) = 1 − N1..
.
P(c. t generations ago) =t−1 1
1 − N1
N→ geometric distribution

Theorem[Kingman ’82]
For N → ∞ this will converge to the Kingman n-coalescent.

 1N

The Kingman n-coalescent→ consider their genealogy as a binary rooted equidistant n-tree

The Kingman n-coalescent→ consider their genealogy as a binary rooted equidistant n-tree

The Kingman n-coalescent→ consider their genealogy as a binary rooted equidistant n-tree

The Kingman n-coalescent→ consider their genealogy as a binary rooted equidistant n-tree

The Kingman n-coalescent→ consider their genealogy as a binary rooted equidistant n-tree
Discrete: Choosing pairs to coalesceThe Kingman n-coalescent→ consider their genealogy as a binary rooted equidistant n-tree
Discrete: Choosing pairs to coalesceThe Kingman n-coalescent→ consider their genealogy as a binary rooted equidistant n-tree
Tj = time during which there are exactly j lineages in the sample
Discrete: Choosing pairs to coalesceThe Kingman n-coalescent→ consider their genealogy as a binary rooted equidistant n-tree
Tj = time during which there are exactly j lineages in the sample
Discrete: Choosing pairs to coalesceContinuous: Exponentially distributed waiting times Tj ∼ Exp 2j

Contents
1The Kingman n-coalescent

2

Space of Trees

3

A Density

4

Connection to Tropical Geometry

5

Further Directions

Space of Trees
Coarse combinatorial types of binary rooted equidistant 4-trees

Space of Trees
Coarse combinatorial types of binary rooted equidistant 4-trees

Space of Trees
Fine combinatorial types of binary rooted equidistant 4-trees

Space of TreesSpace of Trees→ Parametrization?

Space of Trees→ Parametrization
globalSpace of Trees→ Parametrization
globalDefinition(n2)
MUMn := { d ∈ R≥0: ∀i, j, k : max {dij , dik , djk }is attained at least twice}
Metrics that are UltraMetrics

Space of Trees→ Parametrization
globallocal

Definition(n2)
MUMn := { d ∈ R≥0: ∀i, j, k : max {dij , dik , djk }is attained at least twice}
Metrics that are UltraMetrics

Space of Trees→ Parametrization
global: coordinates
dab , dac , dbc

Space of Trees→ Parametrization
global: coordinates
dab , dac , dbc

Space of Trees→ Parametrization
global: coordinates
dab , dac , dbc

Space of Trees→ Parametrization
global: coordinates
dab , dac , dbc→ one cone for eachcombinatorial type

Space of Trees→ Parametrization
global: coordinates
dab , dac , dbc→ one cone for eachcombinatorial type

Space of Trees→ Parametrization
global: coordinates
dab , dac , dbc→ one cone for eachcombinatorial type

Space of Trees→ Parametrization
global: coordinates
dab , dac , dbc→ one cone for eachcombinatorial type

Space of Trees→ Parametrization
global: coordinates
dab , dac , dbc→ one cone for eachcombinatorial type
local:
coordinates T2 , T3

Contents
1

The Kingman n-coalescent

2

Space of Trees

3

A Density

4

Connection to Tropical Geometry

5

Further Directions

A Density

Proposition [Haase, W.]
The Kingman n-coalescent is given by the continuous densityρn (T2 , . . . , Tn ) =n  Yjj=2

   j
exp −
Tj .
22

Contents
1

The Kingman n-coalescent

2

Space of Trees

3

A Density

4

Connection to Tropical Geometry

5

Further DirectionsConnection to Tropical Geometry

DefinitionnMUMn := { d ∈ R≥0 (2) : ∀i, j, k : max {dij , dik , djk }is attained at least twice}
Metrics that are Ultrametrics

Connection to Tropical Geometry
Definition
nDUMn := { d ∈ R(2) : ∀i, j, k : max {dij , dik , djk }is attained at least twice}
Dissimilarity maps that are UltraMetrics

Connection to Tropical Geometry
Definition
nDUMn := { d ∈ R(2) : ∀i, j, k : max {dij , dik , djk }is attained at least twice}
Dissimilarity maps that are UltraMetrics

Definition
A dissimilarity map on [n] is a map δ : [n] × [n] → R such that
δ(i, i) = 0 for all i ∈ [n], and δ(i, j) = δ(j, i) for all i, j ∈ [n].

Connection to Tropical Geometry
Definition
nDUMn := { d ∈ R(2) : ∀i, j, k : max {dij , dik , djk }is attained at least twice}
Dissimilarity maps that are UltraMetrics

Definition
A dissimilarity map on [n] is a map δ : [n] × [n] → R such that
δ(i, i) = 0 for all i ∈ [n], and δ(i, j) = δ(j, i) for all i, j ∈ [n].

Theorem [Ardila Klivans ’06]
DUMn /R1 = trop(matroid(Kn )) = B(Kn )The Bergman fan of a graphical matroid
complete graph K4

The Bergman fan of a graphical matroid
complete graph K4

E = {1, 2, 3, 4, 5, 6}

The Bergman fan of a graphical matroid
complete graph K4

E = {1, 2, 3, 4, 5, 6}

The Bergman fan of a graphical matroid
complete graph K4

Bases of the graphical matroid
M(K4 ) = (E , B)

E = {1, 2, 3, 4, 5, 6}

B = {{2, 4, 5}, {1, 3, 6}, {2, 4, 6},{1, 3, 5}, {2, 3, 4}, {1, 2, 4},{1, 3, 4}, {1, 2, 3}, {3, 4, 6},{2, 3, 5}, {1, 4, 5}, {1, 5, 6},{4, 5, 6}, {2, 5, 6}, {3, 5, 6}}

The Bergman fan of a graphical matroid

The Bergman fan of a graphical matroidnassign weights ω ∈ R(2) to the edges

The Bergman fan of a graphical matroidnassign weights ω ∈ R(2) to the edges

for a basis B = {b1 , . . . , br } the weight of the basis is given byωB = ωb1 + . . . + ωbrThe Bergman fan of a graphical matroid

nassign weights ω ∈ R(2) to the edges

for a basis B = {b1 , . . . , br } the weight of the basis is given byωB = ωb1 + . . . + ωbr→ Mω = collection of bases of M having minimum ω−weightThe Bergman fan of a graphical matroid
Definition
fann Bergmanon()2B(Kn ) := ω ∈ R | Mω has no loops

nassign weights ω ∈ R(2) to the edges

for a basis B = {b1 , . . . , br } the weight of the basis is given byωB = ωb1 + . . . + ωbr→ Mω = collection of bases of M having minimum ω−weightThe Bergman fan of a graphical matroid
Definition
fann Bergmanon()2B(Kn ) := ω ∈ R | Mω has no loops

nassign weights ω ∈ R(2) to the edges

for a basis B = {b1 , . . . , br } the weight of the basis is given byωB = ωb1 + . . . + ωbr→ Mω = collection of bases of M having minimum ω−weightTheorem [Ardila Klivans ’06]
A dissimilarity map is an ultrametric if and only if the corresponding
weight vector on the edges of Kn is in the Bergman fan B(Kn ).

The Bergman fan of a graphical matroid
Theorem [Ardila Klivans ’06]
A dissimilarity map is an ultrametric if and only if the corresponding
weight vector on the edges of Kn is in the Bergman fan B(Kn ).

Space of Trees
Definition
nDTMn := { d ∈ R(2) : ∀i, j, k, l :max {dij + dkl , dik + djl , dil + djk }is attained at least twice}Dissimilarity maps that are TreeMetrics

Space of Trees
DefinitionnDTMn := { d ∈ R(2) : ∀i, j, k, l :max {dij + dkl , dik + djl , dil + djk }is attained at least twice}
Dissimilarity maps that are TreeMetrics

Space of Trees
DefinitionnDTMn := { d ∈ R(2) : ∀i, j, k, l :max {dij + dkl , dik + djl , dil + djk }is attained at least twice}
Dissimilarity maps that are TreeMetrics

Theorem [Speyer Sturmfels ’03]
DTMn /R1 = trop(Gr(2, n))Contents1The Kingman n-coalescent

2

Space of Trees

3

A Density

4

Connection to Tropical Geometry

5

Further Directions

Further DirectionsN
fan with density in R( 2 ) ?

fan for species trees?
include mutations?
consider non-binary trees?

Thank you for your attention!