Pairwise DP Sandbox

Needleman-Wunsch & Smith-Waterman Alignment

Interactive exploration of global (Needleman-Wunsch), local (Smith-Waterman), and affine gap penalty dynamic programming pairwise sequence alignment.

Complete

Speed:

Optimal Pairwise Alignment:

Score:0

Identity:0%

Length:0 bp

Gaps:0

2D Dynamic Programming Score MatrixHover cell to inspect recurrence

Alignment Recurrence Formulation

At each cell (i, j), the optimal score is selected from three transitions:

↖ Diagonal: Align base S1[i] to S2[j] (Match / Mismatch).
↑ Up: Insert gap in S2 (Deletion in target).
← Left: Insert gap in S1 (Insertion in target).

In Smith-Waterman (Local), negative scores are reset to 0, allowing isolated high-scoring local alignment islands to emerge.

Global vs Local Alignment

Needleman-Wunsch (1970) aligns sequences end-to-end (ideal for homologous genes of equal length).Smith-Waterman (1981) identifies the highest-scoring local subsegment (essential for finding conserved domains embedded in noisy non-coding regions).

Gotoh 3-Matrix Affine Gaps

Biological insertions/deletions often span multiple contiguous nucleotides. Gotoh (1982) separated gap opening (g_open) and gap extension (g_ext) into three interleaved matrices (M, I_x, I_y), achieving O(MN) time instead of naive O(MN²).

SIMD Vectorization in Modern Aligners

Modern aligners (Minimap2, BWA-MEM2, Parasail) vectorize DP matrix filling using SSE4.1, AVX2, and AVX-512 vector instructions (Suzuki-Kasahara 2-piece affine formulation), computing 16–32 cells per CPU cycle.