Minimum Edit distance

MED遞迴表示法和演算法
  1. Let \( X=x_1x_2\dots x_m \) and \( Y=y_1y_2\dots y_n \)
  2. Let \( E_{ij} \) denote the edit distance between \( A \)(new) and \( B \)(old) , \( 1\leq i\leq m \) , \( 1\leq i\leq n \)。
  3. Oberve \( x_i \) and \( y_j \) after alignment:

    Insertion
    \( E_{ij}=E_{i-1,j}+1 \)
    \( x_i \)
    -
    Deletion
    \( E_{ij}=E_{i,j-1}+1 \)
    -
    \( y_j \)
    Difference
    \( E_{ij}=E_{i-1,j-1}+diff(i,j) \)
    \( x_i \)
    \( y_j \)

\[ \{ E_{00}=0 \} \;\cup \] \[ \{ E_{0j}=j\;|\;\text{for }1\leq j\leq n\} \;\cup \] \[ \{E_{i0}=i \;|\; \text{for }1\leq i\leq m \} \;\cup \] \[ \{\; E_{ij}= min\{ \underline{E_{i-1,j}+1},\; \underline{E_{i,j-1}+1},\; \underline{E_{i-1,j-1}+diff(i,j)}, \} \; |\;\text{for }1\leq i\leq n, 1\leq j\leq m \; \} \] \[ diff(i,j) = \begin{cases} 0 \text{, if }x_i=y_j\\ 1 \text{, if }x_i\neq y_j\\ \end{cases} \] +1或diff的加權可由應用不同，加以修改。
例如比對的東西不能輕易刪除，但可以換成其他東西，那刪除的成本可能+20之類的。

Example

Old string(A): EXPONENTIAL
New string(B): POLYNOMIAL
\( \varepsilon=\emptyset\)
這裡給\( diff() \)加權為
\( x_i=y_j \rightarrow diff(i,j)=0 \)
\( x_i\neq y_j \rightarrow diff(i,j)=1 \)

A\B \( \varepsilon \) P O L Y N O M I A L
\( \varepsilon \) 0 1 2 3 4 5 6 7 8 9 10
E 1
X 2
P 3
O 4
N 5
E 6
N 7
T 8
I 9
A 10
L 11
開始填表
A\B \( \varepsilon \) P O L Y N O M I A L
\( \varepsilon \) 0 \( \leftarrow \)1 \( \leftarrow \)2 \( \leftarrow \)3 \( \leftarrow \)4 \( \leftarrow \)5 \( \leftarrow \)6 \( \leftarrow \)7 \( \leftarrow \)8 \( \leftarrow \)9 \( \leftarrow \)10
E \( \uparrow \)1 \( \nwarrow 1 \) \( \leftarrow 2 \) \( \leftarrow 3 \) \( \leftarrow 4 \) \( \leftarrow 5 \) \( \leftarrow 6 \) \( \leftarrow 7 \) \( \leftarrow 8 \) \( \leftarrow 9 \) \( \leftarrow 10 \)
X \( \uparrow \)2 \( \nwarrow 2 \) \( \nwarrow 2 \) \( \leftarrow 3 \) \( \leftarrow 4 \) \( \leftarrow 5 \) \( \leftarrow 6 \) \( \leftarrow 7 \) \( \leftarrow 8 \) \( \leftarrow 9 \) \( \leftarrow 10 \)
P \( \uparrow \)3 \( \nwarrow 2 \) \( \leftarrow 3 \) \( \nwarrow 3 \) \( \leftarrow 4 \) \( \leftarrow 5 \) \( \leftarrow 6 \) \( \leftarrow 7 \) \( \leftarrow 8 \) \( \leftarrow 9 \) \( \leftarrow 10 \)
O \( \uparrow \)4 \( \uparrow 3 \) \( \nwarrow 2 \) \( \leftarrow 3 \) \( \leftarrow 4 \) \( \leftarrow 5 \) \( \nwarrow 5 \) \( \leftarrow 6 \) \( \leftarrow 7 \) \( \leftarrow 8 \) \( \leftarrow 9 \)
N \( \uparrow \)5 \( \uparrow 4 \) \( \uparrow 3 \) \( \nwarrow 3 \) \( \leftarrow 4 \) \( \nwarrow 4 \) \( \leftarrow 5 \) \( \leftarrow 6 \) \( \leftarrow 7 \) \( \leftarrow 8 \) \( \leftarrow 9 \)
E \( \uparrow \)6 \( \uparrow 5 \) \( \uparrow 4 \) \( \uparrow 4 \) \( \nwarrow 4 \) \( \leftarrow 5 \) \( \nwarrow 5 \) \( \leftarrow 6 \) \( \leftarrow 7 \) \( \leftarrow 8 \) \( \leftarrow 9 \)
N \( \uparrow \)7 \( \uparrow 6 \) \( \uparrow 5 \) \( \uparrow 5 \) \( \uparrow 5 \) \( \nwarrow 4 \) \( \leftarrow 5 \) \( \leftarrow 6 \) \( \leftarrow 7 \) \( \leftarrow 8 \) \( \leftarrow 9 \)
T \( \uparrow \)8 \( \uparrow 7 \) \( \uparrow 6 \) \( \uparrow 6 \) \( \uparrow 6 \) \( \uparrow 5 \) \( \nwarrow 5 \) \( \leftarrow 6 \) \( \leftarrow 7 \) \( \leftarrow 8 \) \( \leftarrow 9 \)
I \( \uparrow \)9 \( \uparrow 8 \) \( \uparrow 7 \) \( \uparrow 7 \) \( \uparrow 7 \) \( \uparrow 6 \) \( \uparrow 6 \) \( \nwarrow 6 \) \( \nwarrow 6 \) \( \leftarrow 7 \) \( \leftarrow 8 \)
A \( \uparrow \)10 \( \uparrow 9 \) \( \uparrow 8 \) \( \uparrow 8 \) \( \uparrow 8 \) \( \uparrow 7 \) \( \uparrow 7 \) \( \uparrow 7 \) \( \uparrow 7 \) \( \nwarrow 6 \) \( \leftarrow 7 \)
L \( \uparrow \)11 \( \uparrow 10 \) \( \uparrow 9 \) \( \uparrow 9 \) \( \uparrow 9 \) \( \uparrow 8 \) \( \uparrow 8 \) \( \uparrow 8 \) \( \uparrow 8 \) \( \uparrow 7 \) \( \nwarrow 6 \)

(有顏色的地方是最佳解的回推的路徑，灰色是沒有修改的地方，藍色為刪除舊資料，黃色是覆蓋成新資料，綠色是在舊資料後插入。)
(箭頭向上為新insert舊，箭頭向左為delete舊，箭頭向左上則要判斷比對資料相不相同，不相同才要修改。)
由表格可得知the shortest edit distance為6。
回推內容為
I為Insertion
D為Deletion
S為Substitution

D D S S S I
E X P O N E N T - I A L
- - P O L Y N O M I A L
說明:
EXPONENTIAL是舊的資料。
POLYNOMIAL為新的資料。
最短的改法為:
在舊的資料上
刪除E
刪除X
修改N為L
修改E為Y
修改T為O
插入M。
這樣只要修改6次即可。

更改權重的題目

例子: 比對DNA序列