動的計画法に基づき、最適な大域的アライメントを厳密に求める手法である。 ２つの配列長がm, nである場合の実行時間はO(mn)となる。 このアルゴリズムの実装としてはEMBOSSのneedleプログラムがある。
配列\( 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 \)とし、ギャップペナルティ\( -d \)を用いると、\( F(i, 0) = -id (1 \le i \le m) \),\( F(0, j) = -jd(1 \le j \le n) \)となる。 その他\( F(i, j) \)は以下の漸化式で段階的に求める。 \[ F(i, j) = max \ \begin{cases} F(i-1, j-1) + s(x_{i}, y_{j}) \\ F(i-1, j) - d \\ F(i, j-1) -d \end{cases} \] 最終的に得られた\( F(m, n) \)が２つの配列類似度の最大値である。 アライメントは\( F(m, n) \)を開始点として、maxで選択した過程を逆に辿ることで求める。