Models and algorithms for haplotype phasing and variant calling

Abstract

Haplotypes have been increasingly used in genetic studies. Analysis of variations among haplotypes has many applications in population genetics and biomedical research. However, the current DNA sequencing technologies can only read short fragments (called reads) randomly drawn from complete haplotypes, and reads from two haplotypes are mixed together for diploid species like humans. Therefore, recovering the complete haplotype sequences becomes a fundamental problem in computational genomics, which requires calling variants between two haplotypes from reads. With the emerging third-generation sequencing technologies, existing reference-based approaches for haplotype phasing suffer from performance issues to handle long and error-prone reads. At the same time, reference-free methods for variant calling and haplotype phasing meet challenges when applied to large and complex genomes.

This thesis addresses a number of critical challenges in haplotype phasing and variant calling in computational genomics. Firstly, we introduce DCHap, a fast reference-based haplotype phasing algorithm that applies a divide-and-conquer strategy. This divide-and-conquer strategy improves both scalability and accuracy for handling third-generation sequencing data in haplotype phasing. Secondly, we propose an algorithm, Kmer2SNP, for reference-free variant calling using graph matching. The introduction of the heterozygous k-mer graph helps to recover SNPs between two haplotypes through the maximum weight matching. Thirdly, we describe Kmer2Haplotype, a pipeline of reference-free haplotype phasing by incorporating both short and long reads from the same individual. The problem of haplotype phasing is modeled as finding the minimum bi-partition of the haplotype-specific k-mer graph. We further design and conduct extensive experiments, and the benchmarking results show the effectiveness and efficiency of the above-proposed approaches compared to the state-of-art baselines. We finally conclude this thesis by discussing future research directions.