Accelerating pairwise statistical significance estimation for local alignment by harvesting GPU's power.

Yuhong Zhang*, Sanchit Misra, Ankit Agrawal, Md Mostofa Ali Patwary, Wei Keng Liao, Zhiguang Qin, Alok Choudhary

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

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. 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. Harvesting the high performance of modern GPUs is a promising approach to accelerate pairwise statistical significance estimation for local sequence alignment.

Original languageEnglish (US)
Article numberS3
Pages (from-to)S3
JournalBMC bioinformatics
Volume13 Suppl 5
DOIs
StatePublished - 2012

ASJC Scopus subject areas

  • Applied Mathematics
  • Molecular Biology
  • Structural Biology
  • Biochemistry
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Accelerating pairwise statistical significance estimation for local alignment by harvesting GPU's power.'. Together they form a unique fingerprint.

Cite this