Pairwise sequence alignment — Needleman-Wunsch & Smith-Waterman

Step through the classic alignment DP. The matrix fills row-by-row; the traceback reads back-pointers from the chosen end-cell to recover the optimal alignment. Switch between Needleman-Wunsch (global, end-to-end) and Smith-Waterman (local, best subsegment) — same recurrence, different boundary + traceback rules.

idle

DP matrix

high score negative score current cell traceback path

Top-right corner shows the back-pointer arrow (↖ diagonal = match/mismatch, ↑ up = gap in B, ← left = gap in A).

Alignment — recovered by traceback

Algorithm

Scoring

Recurrence (NW)

M[0][0] = 0
M[i][0] = i · gap
M[0][j] = j · gap
M[i][j] = max(
  M[i-1][j-1] + s(A[i],B[j]),  // ↖
  M[i-1][j] + gap,              // ↑
  M[i][j-1] + gap,              // ←
)
traceback from M[m][n]

Recurrence (SW)

M[i][0] = M[0][j] = 0
M[i][j] = max(
  0,                            // local restart
  M[i-1][j-1] + s(A[i],B[j]),
  M[i-1][j] + gap,
  M[i][j-1] + gap,
)
traceback from argmax M[i][j],
stop when M = 0

Why the difference?

NW forces an end-to-end alignment — even highly diverged ends pay gap costs. SW lets the score "restart" at zero, so it finds the single best matching subsegment. Same DP shape, different rules at the boundary and the traceback.

Used in the wild