Pruning the Search, Not the Signal: Adaptive-Banding Needleman-Wunsch Sequence Alignment via Protein Language Model Confidence
- 1University of Engineering and Technology Lahore
Abstract
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 x M cells without search grid constraints. To bridge this gap, we introduce Adaptive-Banding Needleman-Wunsch (AB-NW), pruning the search space without sacrificing sequence alignment signal by 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 O(NW_bar) and space to O(NW_max), where W_bar << M. 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 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.
Related
- EMAP-SSN: An Embedding- and Multiple-Alignment-Integrated Sequence Similarity Network Platform for Interactive Exploration of Protein Sequence Space
- CRAIC: interactive interrogation of multiple sequence alignment uncertainty
- DUMMEST: A simpler and faster model for frameshift-aware alignment of a DNA sequence to a protein family
- What Shapes Brain Alignment of Large Language Models during Dialogue? Insights from Language Production and Comprehension
- Optimized Multiple Circular Sequence Alignment for Cyclic Peptide Motif Discovery
BibTeX
@misc{shoaib2026pruning,
title = {{Pruning the Search, Not the Signal: Adaptive-Banding Needleman-Wunsch Sequence Alignment via Protein Language Model Confidence}},
author = {M. Shoaib and W. Ali},
howpublished = {bioRxiv},
year = {2026},
month = aug,
doi = {10.64898/2026.08.26.747234},
url = {https://www.biorxiv.org/content/10.64898/2026.08.26.747234v2},
note = {CC BY},
}
RIS
TY - UNPB
TI - Pruning the Search, Not the Signal: Adaptive-Banding Needleman-Wunsch Sequence Alignment via Protein Language Model Confidence
AU - M. Shoaib
AU - W. Ali
PY - 2026
DA - 2026/08/26
PB - bioRxiv
DO - 10.64898/2026.08.26.747234
UR - https://www.biorxiv.org/content/10.64898/2026.08.26.747234v2
AB - 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 x M cells without search grid constraints. To bridge this gap, we introduce Adaptive-Banding Needleman-Wunsch (AB-NW), pruning the search space without sacrificing sequence alignment signal by 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 O(NW_bar) and space to O(NW_max), where W_bar << M. 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 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.
ER -