@article {522, title = {Using GPUs for the exact alignment of short-read genetic sequences by means of the Burrows-Wheeler transform.}, journal = {IEEE/ACM Trans Comput Biol Bioinform}, volume = {9}, year = {2012}, month = {2012 Jul-Aug}, pages = {1245-56}, 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.

}, keywords = {Algorithms, Animals, Computational Biology, Computer Graphics, Data Compression, Drosophila melanogaster, Genes, Insect, Image Processing, Computer-Assisted, Models, Genetic, Sequence Alignment, Sequence Analysis, DNA}, issn = {1557-9964}, doi = {10.1109/TCBB.2012.49}, author = {Salavert Torres, Jose and Blanquer Espert, Ignacio and Dom{\'\i}nguez, Andr{\'e}s Tom{\'a}s and Hern{\'a}ndez Garc{\'\i}a, Vicente and Medina Castell{\'o}, Ignacio and T{\'a}rraga Gim{\'e}nez, Joaqu{\'\i}n and Dopazo Bl{\'a}zquez, Joaqu{\'\i}n} }