Friday 24th November 2017 at 2 pm, IBC Campus St Priest BAT5-01.124
Prof. Dr. Tobias MarschallMax-Planck-Institut für Informatik
Algorithms for Computational Genomics
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. Recent advances on fixed-parameter tractable (FPT) algorithm allow us to (quickly) solve practically relevant instances of this NP-hard problem optimally. 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.