Fast gap-affine pairwise alignment using the wavefront algorithm
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)
Moreto, Miquel (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)

Date:	2020
Abstract:	Pairwise alignment of sequences is a fundamental method in modern molecular biology, implemented within multiple bioinformatics tools and libraries. Current advances in sequencing technologies press for the development of faster pairwise alignment algorithms that can scale with increasing read lengths and production yields. In this article, we present the wavefront alignment algorithm (WFA), an exact gap-affine algorithm that takes advantage of homologous regions between the sequences to accelerate the alignment process. As opposed to traditional dynamic programming algorithms that run in quadratic time, the WFA runs in time O (ns), proportional to the read length n and the alignment score s, using memory. Furthermore, our algorithm exhibits simple data dependencies that can be easily vectorized, even by the automatic features of modern compilers, for different architectures, without the need to adapt the code. We evaluate the performance of our algorithm, together with other state-of-the-art implementations. As a result, we demonstrate that the WFA runs 20-300× faster than other methods aligning short Illumina-like sequences, and 10-100× faster using long noisy reads like those produced by Oxford Nanopore Technologies.
Grants:	European Commission 825111 Agencia Estatal de Investigación TIN2017-84553-C2-1-R 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 Ministerio de Economía y Competitividad RYC-2016-21104
Rights:	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, sempre que no sigui amb finalitats comercials, i sempre que es reconegui l'autoria de l'obra original.
Language:	Anglès
Document:	Article ; recerca ; Versió publicada
Published in:	Bioinformatics, Vol. 37, Issue 4 (February 2020) , p. 456-463, ISSN 1367-4811

DOI: 10.1093/bioinformatics/btaa777
PMID: 32915952

8 p, 710.7 KB

The record appears in these collections:
Articles > Research articles
Articles > Published articles