Pruning the Search, Not the Signal: Adaptive-Banding Needleman-Wunsch Sequence Alignment via Protein Language Model Confidence

Abstract

Dynamic programming (DP) yields exact quadratic-time (O(NM)) pairwise sequence alignments. Static banding heuristics (O(NW)) fail catastrophically on low-identity (98.9% of exact unconstrained alignment scores and core-block SP accuracy across static banding failure modes (Twilight Zone, Asymmetric Indels, Extreme Aspect Ratios) while eliminating 55.3%-78.8% of active DP cells. On large protein sequence matrices (N, M >= 3,700), AB-NW eliminates 87.6%-91.7% of cells, achieving speedups of 9.79x-13.30x (pure DP) and 1.73x-2.94x (end-to-end), reaching up to 18.12x on unbiased controls (p < 0.05 to p < 10^-15), making AB-NW practical for large-scale, high-throughput sequence alignment pipelines.