QuickEd

QuickEd accelerates exact pairwise sequence alignment through a bound-and-align strategy that reduces computational complexity while maintaining accuracy for long and noisy datasets.

Key Features:

• Bound-and-align strategy: QuickEd first bounds the maximum alignment-score using efficient heuristic strategies, then utilizes this bound to reduce computations required to produce the optimal alignment.
• Reduced complexity: QuickEd achieves O(ns^) complexity, where n is the sequence length and s^ is an estimated upper bound of the alignment-score, compared to O(n2) complexity of traditional dynamic programming algorithms.
• Performance speedups: QuickEd achieves speedups of 4.2-5.9× over Edlib and 3.8-4.4× over BiWFA when aligning long and noisy datasets.
• Stable memory footprint: QuickEd maintains memory usage below 35 MB while aligning sequences up to 1 Mbp.

Scientific Applications:

• Long-read sequencing analysis: QuickEd addresses scalability challenges of classical algorithms when aligning sequences generated by long-read sequencing technologies.
• Noisy dataset alignment: QuickEd maintains accuracy for datasets with high error rates characteristic of certain sequencing technologies.

Methodology:

QuickEd implements a two-step bound-and-align strategy: first, efficient heuristic strategies bound the maximum alignment-score; second, this bound reduces the computations needed to produce the optimal alignment through dynamic programming.