Exact O(s · d) Sequence Alignment
Wavefront Alignment Algorithm (WFA)
Interactive exploration of exact gap-affine sequence alignment running in O(s · d) time via diagonal wavefront frontier expansion and free Longest Common Prefix (LCP) extensions.
Instead of filling a table of scores over coordinates (i, j), WFA tracks the furthest-reaching offset Ms[k] along diagonal k = j - i for score s:
Free LCP: Matching characters extend along diagonal k with 0 cost, causing similar sequences to reach the end in O(s · d) time.
Why WFA Replaces Classical DP
In typical genomics alignments, error rates are low (< 5%). Needleman-Wunsch wastes computation filling millions of unpromising cells in an O(NM) table. WFA computes only the narrow diagonal cone O(s · d), achieving 20–100× speedups.
Longest Common Prefix (LCP) Acceleration
Because matches incur 0 penalty, any cell on diagonal k can slide diagonally forward until the first mismatch. In modern implementations (WFA2-lib), LCP is accelerated using 64-bit word comparisons and SIMD vector bitmasks.
Pangenomics & Bi-directional WFA (BiWFA)
WFA is the core alignment engine behind pangenome graph builders (such as PGGB, Minigraph-Cactus, and Spoa). Bi-directional WFA (BiWFA) performs wavefront expansion from both ends simultaneously, reducing memory from O(s2) to O(s).