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

Dynamic programming yields exact quadratic-time (O(NM)) pairwise sequence alignments. Static banding heuristics (O(NW)) fail catastrophically on low-identity (below 30 percent), asymmetric insertions/deletions (indels), or extreme length ratios, dropping core-block Sum-of-Pairs (SP) score recovery to 20 to 50 percent. Conversely, recent protein language model (PLM) aligners evaluate all N by 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 dynamic programming corridor prior to fine-resolution dynamic programming 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 O(NW_mean) and space to O(NW_max), where the average bandwidth is much smaller than sequence length M. Benchmarked across three PLM backbones (ESM2-8M, ESM2-35M, ProtBERT) across nine structural challenge categories, AB-NW recovers over 98.9 percent 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 to 78.8 percent of active dynamic programming cells. On large protein matrices (N, M greater than or equal to 3,700), AB-NW eliminates 87.6 to 91.7 percent of cells, achieving speedups of 9.79x to 13.30x (pure DP) and 1.73x to 2.94x (end-to-end), reaching up to 18.12x on unbiased controls (p less than 0.05 to p less than 10^-15), making AB-NW practical for large-scale, high-throughput sequence alignment pipelines.