Can we find the family trees, or pedigrees, that relate the haplotypes of a group of individuals? Collecting the genealogical information for how individuals are related is a very time-consuming and expensive process. Methods for automating the construction of pedigrees could stream-line this process. While constructing single-generation families is relatively easy given whole genome data, reconstructing muti-generational, possibly inbred, pedigrees is much more challenging.

I will present three methods for reconstructing multi-generational pedigrees: a method for synthetic data, and two practical methods, one for outbred data and one for inbred data. In contrast to previous methods that focused on the independent estimation of relationship distances between every pair of individuals, we designed methods that aim at the reconstruction of the entire pedigree. Both practical methods out-perform the state-of-the-art and the outbreeding method is capable of reconstructing pedigrees at least six generations back in time with high accuracy.

If there is time, I will also discuss the computational complexity of likelihood calculations on pedigree graphs. It turns out that from a computational complexity perspective, haplotype data is no more helpful than genotype data, even though haplotype data certainly provides more information about inheritance.