動的計画法に基づき、最適な局所的アライメントを厳密に求める手法である。 ２つの配列長がm, nである場合の実行時間はO(mn)となる。 このアルゴリズムの実装としてはEMBOSSのwaterプログラムがある。
配列\( x = x_{1} x_{2} \ldots x_{m} \)と\( y = y_{1} y_{2} \ldots y_{n} \)の最適局所的アライメントを求めたいとする。 部分配列\( x = x_{1} x_{2} \ldots x_{i} \)と\( y = y_{1} y_{2} \ldots y_{j} \)の最適アライメントのスコアを格納するためのスコア行列\( F \)を導入する。 以下、ギャップ計算はリニアペナルティと仮定する。 初期条件として\( F(0, 0) = 0 \)とし、\( F(i, 0) = F(0, j) = 0 \ (1 \le i \le m, 1 \le j \le n) \)とする。 その他\( F(i, j) \)は以下の漸化式で段階的に求める。 \[ F(i, j) = max \ \begin{cases} 0 \\ F(i-1, j-1) + s(x_{i}, y_{j}) \\ F(i-1, j) - d \\ F(i, j-1) -d \end{cases} \tag{3} \] 配列類似度の最大値である座標を開始点として、スコアが0となる座標に至るまで経路復元することで、最適な局所的アライメントが得られる。