Abstract
Aligning biological sequences against a protein database is an im- portant step of bioinformatics research and applications. Due to the rapid growth of sequencing technologies, sequence data becomes more difficult to handle. BLASTX, a software provided by NCBI, is the most popular alignment tool due to its high sensitivity. However, it is too slow in aligning large dataset with database. In 2015, DIAMOND, a software proposed by Buchfink, Xie, and Huson (Nature Methods, 2015), speeds up the alignment process significantly while maintaining similar sensitivity as BLASTX. How- ever, DIAMOND is still slow when the query data is large. Several acceleration techniques have been studied to improve the speed of DIAMOND. For instance, AC-DIAMOND (Mai et al., Proc. BIBE, 2016) utilizes CPU SIMD instructions and reports a 4-fold overall speedup over DIAMOND; HAMOND (Yu et al., J. Biotechnology, 2017) parallelizes DIAMOND on Hadoop distributed system. Despite the many recent successes in applying GPU technology to speed up algorithms, there is no GPU-accelerated version of DIA- MOND. In this thesis, we present CU-DIAMOND, an efficient GPU acceleration of DIAMOND. Experimental results show that CU- DIAMOND achieves a 10-fold speedup in the most time-consuming alignment part of DIAMOND, and gains a 4-fold overall speedup over DIAMOND (and a 33% speedup over AC-DIAMOND), while sensitivity remains the same.