title: Accelerating pairwise statistical significance estimation for local alignment by harvesting GPU's power.
abstract: BACKGROUND
  Pairwise statistical significance has been recognized to be able to accurately identify related sequences, which is a very important cornerstone procedure in numerous bioinformatics applications. However, it is both computationally and data intensive, which poses a big challenge in terms of performance and scalability.
  
  
  RESULTS
  We present a GPU implementation to accelerate pairwise statistical significance estimation of local sequence alignment using standard substitution matrices. By carefully studying the algorithm's data access characteristics, we developed a tile-based scheme that can produce a contiguous data access in the GPU global memory and sustain a large number of threads to achieve a high GPU occupancy. We further extend the parallelization technique to estimate pairwise statistical significance using position-specific substitution matrices, which has earlier demonstrated significantly better sequence comparison accuracy than using standard substitution matrices. The implementation is also extended to take advantage of dual-GPUs. We observe end-to-end speedups of nearly 250 (370) × using single-GPU Tesla C2050 GPU (dual-Tesla C2050) over the CPU implementation using Intel Corei7 CPU 920 processor.
  
  
  CONCLUSIONS
  Harvesting the high performance of modern GPUs is a promising approach to accelerate pairwise statistical significance estimation for local sequence alignment.
authors.affiliation: School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China. yuhongzhang@uestc.edu.cn
authors.forename: Yuhong
authors.initials: Y
authors.lastname: Zhang
authors.forename: Sanchit
authors.initials: S
authors.lastname: Misra
authors.forename: Ankit
authors.initials: A
authors.lastname: Agrawal
authors.forename: Md Mostofa Ali
authors.initials: MM
authors.lastname: Patwary
authors.forename: Wei-Keng
authors.initials: WK
authors.lastname: Liao
authors.forename: Zhiguang
authors.initials: Z
authors.lastname: Qin
authors.forename: Alok
authors.initials: A
authors.lastname: Choudhary
mesh_terms: D000465:Algorithms; D003196:Computer Graphics / Q000295:instrumentation*; D016415:Sequence Alignment / Q000295:instrumentation / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000295:instrumentation / Q000379:methods*; D012984:Software