Efficient Pairwise Statistical Significance Estimation for Local Sequence Alignment Using GPU
Pairwise statistical significance has been found to be quite accurate in identifying related sequences (homologs), which is a key step in numerous bioinformatics applications. However, it is computational and data intensive, particularly for a large amount of sequence data. To prevent it from becoming a performance bottleneck, the authors resort to Graphics Processing Units (GPUs) for accelerating the computation. In this paper, they present a GPU memory-access optimized implementation for a pair wise statistical significance estimation algorithm. By exploring the algorithm's data access characteristics, they developed a tile-based scheme that can produce a contiguous memory accesses pattern to GPU global memory and sustain a large number of threads to achieve a high GPU occupancy.