アルゴリズムと計算量の問題

$X=x_1{x}_2{x}_3{x}_4=\mathrm{ACGA}$、$Y=y_1{y}_2{y}_3=\mathrm{CAG}$ とし、$D[i][j]$ を「$X$ の先頭 $i$ 文字を $Y$ の先頭 $j$ 文字に変換する最小コスト」と定める。求める値は $D[4][3]$ である。

漸化式　$c_{\mathrm{del}}=1,c_{\mathrm{ins}}=2,c_{\mathrm{sub}}=1$ なので
$$D[i][j]=\min (D[i-1][j]+1,D[i][j-1]+2,D[i-1][j-1]+[x_i\ne y_j])$$
ここで $[x_i\ne y_j]$ は $x_i\ne y_j$ のとき $1$、$x_i=y_j$ のとき $0$（置換不要）である。

初期値　空文字列への変換は削除だけなので $D[i][0]=i$（$0,1,2,3,4$）。空文字列からの変換は挿入だけなので $D[0][j]=2j$（$0,2,4,6$）。

表を埋める（上の行から、左から順に）

$i=1$（$x_1=\mathrm{A}$）:
- $D[1][1]=\min (2+1,1+2,0+1)=1$（$\mathrm{A}\ne \mathrm{C}$）
- $D[1][2]=\min (4+1,1+2,2+0)=2$（$\mathrm{A}=\mathrm{A}$）
- $D[1][3]=\min (6+1,2+2,4+1)=4$

$i=2$（$x_2=\mathrm{C}$）:
- $D[2][1]=\min (1+1,2+2,1+0)=1$（$\mathrm{C}=\mathrm{C}$）
- $D[2][2]=\min (2+1,1+2,1+1)=2$
- $D[2][3]=\min (4+1,2+2,2+1)=3$

$i=3$（$x_3=\mathrm{G}$）:
- $D[3][1]=\min (1+1,3+2,2+1)=2$
- $D[3][2]=\min (2+1,2+2,1+1)=2$
- $D[3][3]=\min (3+1,2+2,2+0)=2$（$\mathrm{G}=\mathrm{G}$）

$i=4$（$x_4=\mathrm{A}$）:
- $D[4][1]=\min (2+1,4+2,3+1)=3$
- $D[4][2]=\min (2+1,3+2,2+0)=2$（$\mathrm{A}=\mathrm{A}$）
- $D[4][3]=\min (2+1,2+2,2+1)=3$

表にまとめると（行が $i$、列が $j$）
$$\begin{array}{ccccc}& 0& \mathrm{C}& \mathrm{A}& \mathrm{G}\\ 0& 0& 2& 4& 6\\ \mathrm{A}& 1& 1& 2& 4\\ \mathrm{C}& 2& 1& 2& 3\\ \mathrm{G}& 3& 2& 2& 2\\ \mathrm{A}& 4& 3& 2& 3\end{array}$$

よって編集距離は $D[4][3]=3$ である。

（確認）たとえば $\mathrm{ACGA}$ の末尾の $\mathrm{A}$ を削除して $\mathrm{ACG}$（コスト $1$）、先頭 $2$ 文字を $\mathrm{A}\to \mathrm{C}$、$\mathrm{C}\to \mathrm{A}$ と置換して $\mathrm{CAG}$（コスト $2$）とすれば、合計 $3$ で変換できる。

$D[i][j]$ を $X$ の先頭 $i$ 文字から $Y$ の先頭 $j$ 文字への最小コストとする。漸化式は $D[i][j]=\min (D[i-1][j-1]+(\text{一致なら }0,\text{不一致なら }1),D[i-1][j]+1,D[i][j-1]+2)$。境界は $D[i][0]=i$、$D[0][j]=2j$。

行ごとの値（$j=0,1,2,3$、$Y=\mathrm{C},\mathrm{A},\mathrm{G}$）は次のとおり。
- $i=0$: 0, 2, 4, 6
- $i=1$（A）: 1, 1, 2, 4
- $i=2$（C）: 2, 1, 2, 3
- $i=3$（G）: 3, 2, 2, 2
- $i=4$（A）: 4, 3, 2, 3

よって $D[4][3]=3$。

検算: 最初の A を削除して CGA にし（コスト 1）、G→A、A→G と 2 回置換すると合計 3 で $Y$ になる。コスト 2 以下は、長さを 3 にする削除が必須なので「削除 1 回＋置換 1 回」に限られる。削除後の候補 CGA, AGA, ACA, ACG と CAG との不一致文字数はそれぞれ 2, 3, 3, 2 で、どれも置換 1 回では足りない。したがって 3 が最小。