Bioinformatický seminár

Tue 6 Mar. 2012, 17:20

Title: Parida (2010) Ancestral recombinations graph: a reconstructability perspective using random-graphs framework
Speaker: Martin Králik

We present a random graphs framework to study pedigree history in an ideal
(Wright Fisher) population. This framework correlates the underlying
mathematical objects in, for example, pedigree graph, mtDNA or NRY Chr
tree, ARG (Ancestral Recombinations Graph), and HUD used in literature,
into a single unified random graph framework. It also gives a natural
definition, based solely on the topology, of an ARG, one of the most
interesting as well as useful mathematical objects in this area. The
random graphs framework gives an alternative parametrization of the ARG
that does not use the recombination rate q and instead uses a parameter M
based on the (estimate of ) the number of non-mixing segments in the
extant units. This seems more natural in a setting that attempts to tease
apart the population dynamics from the biology of the units. This
framework also gives a purely topological definition of GMRCA, analogous
to MRCA on trees (which has a purely topological description i.e., it is a
root, graph-theoretically speaking, of a tree). Secondly, with a natural
extension of the ideas from random-graphs we present a sampling
(simulation) algorithm to construct random instances of ARG/unilinear
transmission graph. This is the first (to the best of the author's
knowledge) algorithm that guarantees uniform sampling of the space of ARG
instances, reflecting the ideal population model. Finally, using a measure
of reconstructability of the past historical events given a collection of
extant sequences, we conclude for a given set of extant sequences, the
joint history of local segments along a chromosome is reconstructible.