Fast and accurate short read alignment with hybrid hash-tree data structure

Abstract

Rapidly increasing amount of short read data generated by NGSs (new-generation sequencers) calls for the development of fast and accurate read alignment programs. The programs based on hash table (BLAST) and Burrows-Wheeler transform (bwa-mem) are used, and the latter is known to give superior performance. We here present a new algorithm, a hybrid of hash table and suffix tree, which we designed to speed up the alignment of short reads against large reference sequences such as human genome. The total turnaround time for processing one human genome sample (read depth of 30) is just 31 minutes with our system while that was more than 25 hours with bwa-mem/gatk. The time for aligner alone is 28 minutes for our system but around 2 hours for bwa-mem. Our new algorithm is 4.4 times faster than bwa-mem while achieving similar accuracy. Variant calling and other downstream analyses after the alignment can be done with open-source tools such as SAMtools and Genome Analysis Toolkit (gatk) packages, as well as our own fast variant caller, which is well parallelized and much faster than gatk.