Optimal gap-affine alignment in O (s) space
Marco-Sola, Santiago (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
Eizenga, Jordan (University of California. Genomics Institute)
Guarracino, Andrea (University of Tennessee Health Science Center. Department of Genetics, Genomics and Informatics)
Paten, Benedict (University of California. Santa Cruz Genomics Institute)
Garrison, Erik (University of Tennessee Health Science Center. Department of Genetics, Genomics and Informatics)
Moreto, Miquel (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)

Date:	2023
Abstract:	Pairwise sequence alignment remains a fundamental problem in computational biology and bioinformatics. Recent advances in genomics and sequencing technologies demand faster and scalable algorithms that can cope with the ever-increasing sequence lengths. Classical pairwise alignment algorithms based on dynamic programming are strongly limited by quadratic requirements in time and memory. The recently proposed wavefront alignment algorithm (WFA) introduced an efficient algorithm to perform exact gap-affine alignment in time, where s is the optimal score and n is the sequence length. Notwithstanding these bounds, WFA's memory requirements become computationally impractical for genome-scale alignments, leading to a need for further improvement. In this article, we present the bidirectional WFA algorithm, the first gap-affine algorithm capable of computing optimal alignments in memory while retaining WFA's time complexity of . As a result, this work improves the lowest known memory bound to compute gap-affine alignments. In practice, our implementation never requires more than a few hundred MBs aligning noisy Oxford Nanopore Technologies reads up to 1 Mbp long while maintaining competitive execution times. All code is publicly available at . Supplementary data are available at Bioinformatics online.
Grants:	Agencia Estatal de Investigación PID2020-113614RB-C21 Agencia Estatal de Investigación PID2019-107255GB-C21 Agencia Estatal de Investigación TED2021-132634A-I00 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, Industria y Competitividad RYC-2016-21104 Ministerio de Ciencia e Innovación IJC2020-045916-I
Note:	Altres ajuts: DRAC project [001-P-001723]
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, fins i tot amb finalitats comercials, sempre i quan es reconegui l'autoria de l'obra original.
Language:	Anglès
Document:	Article ; recerca ; Versió publicada
Published in:	Bioinformatics, Vol. 39, Issue 2 (February 2023) , art. btad074, ISSN 1367-4811

DOI: 10.1093/bioinformatics/btad074
PMID: 36749013

7 p, 1.3 MB

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