Using GPUs for the exact alignment of short-read genetic sequences by means of the Burrows-Wheeler transform

IEEE/ACM Trans Comput Biol Bioinform. 2012 Jul-Aug;9(4):1245-56. doi: 10.1109/TCBB.2012.49.

Abstract

General Purpose Graphic Processing Units (GPGPUs) constitute an inexpensive resource for computing-intensive applications that could exploit an intrinsic fine-grain parallelism. This paper presents the design and implementation in GPGPUs of an exact alignment tool for nucleotide sequences based on the Burrows-Wheeler Transform. We compare this algorithm with state-of-the-art implementations of the same algorithm over standard CPUs, and considering the same conditions in terms of I/O. Excluding disk transfers, the implementation of the algorithm in GPUs shows a speedup larger than 12, when compared to CPU execution. This implementation exploits the parallelism by concurrently searching different sequences on the same reference search tree, maximizing memory locality and ensuring a symmetric access to the data. The paper describes the behavior of the algorithm in GPU, showing a good scalability in the performance, only limited by the size of the GPU inner memory.

Publication types

  • Research Support, Non-U.S. Gov't

MeSH terms

  • Algorithms*
  • Animals
  • Computational Biology / methods*
  • Computer Graphics
  • Data Compression / methods*
  • Drosophila melanogaster / genetics
  • Genes, Insect
  • Image Processing, Computer-Assisted / methods*
  • Models, Genetic
  • Sequence Alignment / methods*
  • Sequence Analysis, DNA / methods