A practical introduction to the tree sequence:
June 2023
Genomes
- are very big (\(10^7\)–\(10^{12}\) nucleotides)
- reflect past history and process
Meiosis & Recombination
You have two copies of each autosome, one from each parent.
When you make a gamete, the copies recombine,
and copying errors lead to mutations.
from gcbias.org
Tracing back the ancestry of some chromosomes:
- blocks labeled by who inherits from them
- blocks can split
- or coalesce,
- and mutations lead to differences.
Result: a labeled genealogy containing all the genealogical trees.
Tracing back the ancestry of some chromosomes:
- blocks labeled by who inherits from them
- blocks can split
- or coalesce,
- and mutations lead to differences.
Result: a labeled genealogy containing all the genealogical trees.
Tracing back the ancestry of some chromosomes:
- blocks labeled by who inherits from them
- blocks can split
- or coalesce,
- and mutations lead to differences.
Result: a labeled genealogy containing all the genealogical trees.
Tracing back the ancestry of some chromosomes:
- blocks labeled by who inherits from them
- blocks can split
- or coalesce,
- and mutations lead to differences.
Result: a labeled genealogy containing all the genealogical trees.
Tracing back the ancestry of some chromosomes:
- blocks labeled by who inherits from them
- blocks can split
- or coalesce,
- and mutations lead to differences.
Result: a labeled genealogy containing all the genealogical trees.
Tracing back the ancestry of some chromosomes:
- blocks labeled by who inherits from them
- blocks can split
- or coalesce,
- and mutations lead to differences.
Result: a labeled genealogy containing all the genealogical trees.
Tracing back the ancestry of some chromosomes:
- blocks labeled by who inherits from them
- blocks can split
- or coalesce,
- and mutations lead to differences.
Result: a labeled genealogy containing all the genealogical trees.
Tracing back the ancestry of some chromosomes:
- blocks labeled by who inherits from them
- blocks can split
- or coalesce,
- and mutations lead to differences.
Result: a labeled genealogy containing all the genealogical trees.
History is a sequence of trees
For a set of sampled chromosomes, at each position along the genome there is a genealogical tree that says how they are related.
The succinct tree sequence
is a way to succinctly describe this, er, sequence of trees
and the resulting genome sequences.
by Jerome Kelleher, in Kelleher, Etheridge, and McVean
Example: three samples; two trees; two variant sites
The result: an encoding of the genomes and all the genealogical trees.
File sizes
100Mb chromosomes; from Kelleher et al 2018, Inferring whole-genome histories in large population datasets, Nature Genetics
For \(N\) samples genotyped at \(M\) sites
Genotype matrix: \(O(NM)\)
\(N \times M\) things.
Tree sequence: \(O(N + T + M)\)
- \(2N-2\) edges for the first tree
- \(\sim 4\) edges per each of \(T\) trees
- \(M\) mutations
Fast genotype statistics
Tree recording strategy
Every time an individual is born, we must:
- add each gamete to the Node Table,
- add entries to the Edge Table recording which parent each gamete inherited each bit of genome from, and
- add any new selected mutations to the Mutation Table and (if necessary) their locations to the Site Table.
This produces waaaaay too much data.
Software
Everything is efficient, open, and tested.
tskit: tree sequence toolsstdpopsim: a library of “standard” simulation toolsmsprime: coalescent simulator,SLiM: forwards evolutionary simulator