Pruning the Search, Not the Signal: Adaptive-Banding Needleman–Wunsch via Protein Language Model Confidence
Dynamic programming (DP) yields exact quadratic-time (O(NM)) pairwise sequence alignments. Static banding heuristics (O(NW)) fail catastrophically on low-identity (< 30%), asymmetric insertions/deletions (indels), or extreme length ratios, dropping core-block Sum-of-Pairs (SP) score recovery to 20%– 50%. Conversely, recent protein language model (PLM) aligners evaluate all N × M cells without search grid constraints. To bridge this gap, we introduce Adaptive-Banding Needleman–Wunsch (AB-NW), leveraging PLM contextual representations to construct a confidence-adaptive DP corridor prior to fine-resolution DP while keeping downstream scoring unmodified. AB-NW downsamples residue embeddings, computes a coarse alignment, and sets per-row corridor bounds via normalized confidence metrics. Evaluated via JIT-compiled buffers, this reduces time complexity to and space to O(NWmax) . Benchmarked across three PLM backbones (ESM2-8M, ESM2-35M, ProtBERT) across nine structural challenge categories, AB-NW recovers > 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 matrices (N, M ≥ 3, 700), AB-NW eliminates 87.6%– 91.7% of cells, achieving speedups of 9.79×–13.30× (pure DP) and 1.73×– 2.94× (end-to-end), reaching up to 18.12× on unbiased controls (p < 0.05 to p < 10−15), making AB-NW practical for large-scale, high-throughput sequence alignment pipelines.