Accelerating Edit-Distance Sequence Alignment on GPU Using the Wavefront Algorithm
Aguado Puig, Quim (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
Marco-Sola, Santiago (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
Moure, Juan C (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
Castells-Rufas, David (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
Alvarez, Lluc (Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors)
Espinosa, Antonio (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
Moreto, Miquel (Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors)

Data:	2022
Resum:	Sequence alignment remains a fundamental problem with practical applications ranging from pattern recognition to computational biology. Traditional algorithms based on dynamic programming are hard to parallelize, require significant amounts of memory, and fail to scale for large inputs. This work presents eWFA-GPU, a GPU (graphics processing unit)-accelerated tool to compute the exact edit-distance sequence alignment based on the wavefront alignment algorithm (WFA). This approach exploits the similarities between the input sequences to accelerate the alignment process while requiring less memory than other algorithms. Our implementation takes full advantage of the massive parallel capabilities of modern GPUs to accelerate the alignment process. In addition, we propose a succinct representation of the alignment data that successfully reduces the overall amount of memory required, allowing the exploitation of the fast shared memory of a GPU. Our results show that our GPU implementation outperforms by 3- 9× the baseline edit-distance WFA implementation running on a 20 core machine. As a result, eWFA-GPU is up to 265 times faster than state-of-the-art CPU implementation, and up to 56 times faster than state-of-the-art GPU implementations.
Ajuts:	European Commission 825111 Agencia Estatal de Investigación PID2020-113614RB-C21 Ministerio de Economía y Competitividad TIN2015-65316-P Agència de Gestió d'Ajuts Universitaris i de Recerca 2017/SGR-313 Agència de Gestió d'Ajuts Universitaris i de Recerca 2017/SGR-1328 Agència de Gestió d'Ajuts Universitaris i de Recerca 2017/SGR-1414 Agencia Estatal de Investigación RYC-2016-21104
Drets:	Aquest document està subjecte a una llicència d'ús Creative Commons. Es permet la reproducció total o parcial, la distribució, la comunicació pública de l'obra i la creació d'obres derivades, fins i tot amb finalitats comercials, sempre i quan es reconegui l'autoria de l'obra original.
Llengua:	Anglès
Document:	Article ; recerca ; Versió publicada
Matèria:	Graphics processing units ; Memory management ; Heuristic algorithms ; Bioinformatics ; Time complexity ; Genomics
Publicat a:	IEEE Access, Vol. 10 (June 2022) , p. 63782-63796, ISSN 2169-3536

DOI: 10.1109/ACCESS.2022.3182714

15 p, 1.2 MB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats