A Guided Tour to Computational Haplotyping

Tobias Marschall
Algorithms for Computational Genomics, Center for Bioinformatics Saar, Germany
Friday April 21 2017, 2pm, IBC (LIRMM Bat.5), room 1/124 (see map)

 Humans and many other species are diploid. Every individual inherits two versions of each autosomal chromosome, called haplotypes, one from its mother and one from its father. Moving from (sequences of) genotypes to haplotypes is known as phasing or haplotyping. The knowledge of haplotypes is critical for addressing a variety of important questions in fundamental and clinical research. In this talk, I will highlight both algorithmic and experimental aspects of reconstructing haplotypes, with a special emphasis on recent technological advancements and their impact on the computational problems to be solved. I will briefly touch on population-based and pedigree-based phasing method, but will mostly focus on direct experimental methods that allow to reconstruct haplotypes for single individuals. Haplotype reconstruction from sequencing reads is most commonly formalized as the Minimum Error Correction (MEC) problem. We have designed a fixed-parameter tractable (FPT) algorithm that can (quickly) solve practically relevant instances of this NP-hard problem optimally. It is implemented in our WhatsHap software suite. I will present experimental results from five different platforms (PacBio, Oxford Nanopore, Hi-C, StrandSeq, and 10X Genomics) and highlight how combinations of these technologies allow to accurately reconstruct dense chromosome-length human haplotypes at manageable costs.

IBC seminars