QuickEd: High-performance exact sequence alignment based on bound-and-align

Abstract

MotivationPairwise sequence alignment is a core component of multiple sequencing-data analysis tools. Recent advancements in sequencing technologies have enabled the generation of longer sequences at a much lower price. Thus, long-read sequencing technologies have become increasingly popular in sequencing-based studies. However, classical sequence analysis algorithms face significant scalability challenges when aligning long sequences. As a result, several heuristic methods have been developed to improve performance at the expense of accuracy, as they often fail to produce the optimal alignment. ResultsThis paper introduces QuickEd, a sequence alignment algorithm based on a bound-and-align strategy. First, QuickEd effectively bounds the maximum alignment-score using efficient heuristic strategies. Then, QuickEd utilizes this bound to reduce the computations required to produce the optimal alignment. Using QuickEds bound-and-align strategy, we reduce O(n2) complexity of traditional dynamic programming algorithms to O(n[s]), where n is the sequence length and[s] is an estimated upper bound of the alignment-score between the sequences. As a result, QuickEd is consistently faster than other state-of-the-art implementations, such as Edlib and BiWFA, achieving performance speedups of 1.6-7.3x and 2.1 - 2.5x, respectively, aligning long and noisy datasets. In addition, QuickEd maintains a stable memory footprint below 50 MB while aligning sequences up to 1 Mbp. AvailabilityQuickEd code and documentation are publicly available at https://github.com/maxdoblas/QuickEd. Contactmax.doblas@bsc.es