An Exact Matching Approach for High Throughput Sequencing Based on BWT and GPUs

In recent years, Burrows-Wheeler Transformation (BWT) has become a popular method for sequence alignment in bioinformatics applications. Several multithreaded programs such Bowtie, BWA and SOAP2 are developed to make DNA sequencing fast. However, as the requests from patients grow extremely fast, current machines for analysis, most of which are CPUs, becomes more incapable in providing sufficient computational powers. In 2010, the graphics card company NVIDIA released its new Fermi architecture and several series of brands to meet the need for general-purpose parallel computing, which provide dozens to hundreds time of computation power increase compared to single CPU. In this paper, Burrows-Wheeler Transformation (BTW) is analyzed thoroughly and several optimizations are proposed for exact sequence matching. Also, efficient High Throughput Sequencing (HTS) models on both CPU and GPU are developed for practical applications. Experimental results have demonstrated the effectiveness of our algorithm and the great potentials of GPUs in the sequence alignment area.