title: Using GPUs for the exact alignment of short-read genetic sequences by means of the Burrows-Wheeler transform.
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.
authors.affiliation: Centro Mixto CSIC, Instituto de Instrumentación para Imagen Molecular Valencia-I3M, Universitat Politècnica de València-CIEMAT, Camino de Vera s/n, València 46022, Spain. josator@i3m.upv.es
authors.forename: José
authors.initials: J
authors.lastname: Salavert Torres
authors.forename: Ignacio
authors.initials: I
authors.lastname: Blanquer Espert
authors.forename: Andrés Tomás
authors.initials: AT
authors.lastname: Domínguez
authors.forename: Vicente
authors.initials: V
authors.lastname: Hernández García
authors.forename: Ignacio
authors.initials: I
authors.lastname: Medina Castelló
authors.forename: Joaquín
authors.initials: J
authors.lastname: Tárraga Giménez
authors.forename: Joaquín
authors.initials: J
authors.lastname: Dopazo Blázquez
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology / Q000379:methods*; D003196:Computer Graphics; D044962:Data Compression / Q000379:methods*; D004331:Drosophila melanogaster / Q000235:genetics; D017344:Genes, Insect; D007091:Image Processing, Computer-Assisted / Q000379:methods*; D008957:Models, Genetic; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods