SpecHap: a diploid phasing algorithm based on spectral graph theory

ABSTRACT Haplotype phasing is essential to study diploid eukaryotic organisms. High-throughput sequencing, including next-generation sequencing and third-generation sequencing from different technologies, brings possibilities for haplotype assembly. Although there exist multiple haplotype phasing algorithms, only a few are portable across sequencing technologies with the premise of efficiency and accuracy. Herein, we proposed SpecHap, a novel haplotype assembly tool that leverages spectral graph theory, transforming haplotype phasing into an algebraic problem. On both in silico and whole-genome-sequencing datasets, SpecHap consumed less memory and required less CPU time, yet achieved comparable accuracy comparing to state-of-art methods across all the test instances of next-generation sequencing, linked-reads, high-throughput chromosome conformation capture sequencing, PacBio single-molecule real-time sequencing and Oxford Nanopore long-reads sequencing data. Furthermore, SpecHap successfully phased an individual Ambystoma mexicanumm , a species with gigantic diploid genomes, within 6 CPU hours and 945MB peak memory usage, while other tools failed to yield results either due to a memory overflow (40GB) or a time limit excess (5 days). Our results demonstrated that SpecHap is scalable, efficient and accurate for diploid phasing, supporting diverse sequencing platforms.