Optimization of blast seed indexing in the alignment of DNA sequences with GPU using CUDA

Franklin Luis Antonio Cruz Gamero, Juan Carlos Gutierrez Caceres

Resultado de la investigación: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva


In the alignment of biological sequences such as DNA, RNA and proteins, different algorithms are used, mainly the Basic Local Alignment Search Tool (BLAST), which has two phases, a heuristic phase of seed indexing and another extension phase with a comparison of sequences using the Smith-Waterman (SW) algorithm, which allows the alignment of a short sequence 'query' with a long reference sequence 'db' in a very fast way in relation to other algorithms of alignment. This work proposes to use a two-dimensional matrix instead of a sparse matrix as a hash table for the storage of the seed index obtained, as well as the use of the GPU of our graphic card to optimize the planting, it reduces 11.24 % of the time of processing of seed indexing phase of the BLAST, presenting the use of GPU with CUDA a better performance in processing time than the sequential implementation and another multi CPUs using threads with OPENMP. Our algorithm has a complexity in time of O(1) to obtain the seeds identical to the pattern key. The performance is greater when the length of the hash key increases. For its evaluation tests we used a laptop core i7 of 16gb of RAM and a graphic card of 384 cores with C++ programming language and CUDA. Alignment tests were performed using real DNA sequences obtained from the National Center for Biotechnology Information (NCBI) and ENSEMBL in FASTA format with reference sequences of up to 1.3 Gb, such as the complete genome of the hen (Gallus gallus) that has 1 230 258 557 base pairs (bp) and with a query sequence of 140 bp, which was indexed with a 5 bp key in 1074 milliseconds using GPU.

Idioma originalInglés
Título de la publicación alojadaProceedings - 2018 44th Latin American Computing Conference, CLEI 2018
EditorialInstitute of Electrical and Electronics Engineers Inc.
Número de páginas6
ISBN (versión digital)9781728104379
EstadoPublicada - oct. 2018
Evento44th Latin American Computing Conference, CLEI 2018 - Sao Paulo, Brasil
Duración: 1 oct. 20185 oct. 2018

Serie de la publicación

NombreProceedings - 2018 44th Latin American Computing Conference, CLEI 2018


Conferencia44th Latin American Computing Conference, CLEI 2018
CiudadSao Paulo

Nota bibliográfica

Publisher Copyright:
© 2018 IEEE.


Profundice en los temas de investigación de 'Optimization of blast seed indexing in the alignment of DNA sequences with GPU using CUDA'. En conjunto forman una huella única.

Citar esto