Smith–Waterman

Temple F. Smith & Michael S. Waterman, 1981

Smith–Waterman (1981) adapts Needleman–Wunsch for local alignment by clamping negative scores to zero. Each cell H[i,j] = max(0, H[i-1,j-1]+score, H[i-1,j]-gap, H[i,j-1]-gap). The maximum entry marks the alignment endpoint; traceback follows until a zero is reached, revealing the highest-scoring local subsequence pair.