はじめに

2つの文字列の類似性が測定できると役に立つ場合がある. 例えば,GATCGGCATCAATGTGAATCの2つの塩基配列に対して,次のような対応付けを行うことで,これらの塩基配列の類似度合いを調べることができる.

G ATCG GCAT
CAAT GTGAATC
RI==D=I=R==I

なお,=は文字が一致している箇所,Rは文字が異なっている場所,Dは上側に文字を挿入した箇所,Iは下側に文字を挿入した箇所である. また,修正前と修正後のソースコードの類似部分を見つけることで,ソースコードに加えられた変更点(diff)を調べることができる(以下の例では===に修正).

before: if (flag = 1) { printf("found\n"); }
after:  if (flag == 1) { printf("found\n"); }

本課題では,2つの文字列$X = \langle x_1, x_2, …, x_m \rangle$と$Y = \langle y_1, y_2, …, y_n \rangle$の類似性を測定する方法として,編集距離(edit distance)に取り組む.

編集距離の定義

編集距離について理解するため,文字列$X$の先頭から任意回の編集操作を逐次適用していき,文字列$Y$に等しい文字列$Z = \langle z_1, z_2, …, z_n \rangle$を得る手続きを考える.編集操作とは,「$X$ の 2 文字目を $Z$ の 3 番目の変数にコピーする」などの「$X$ の $i$ 番目の文字 $x_i$ の情報を使って,$Z$ の $j$ 番目の変数 $z_j$ を変更する操作」をいう.

以上を形式的に表現してみよう.まず,$Z$の初期状態を空文字列とする($j = 1, 2, …, n$ に対して $z_j = \phi$).$X,Z$ の編集操作の対象となる添字を変数 $i,j$ で表現し,初期状態を $i=j=1$ とする.すると,前述の手続きは,「$Y$ と等しい $Z$ を得るまで (1) 編集操作の適用,(2) 操作対象の添字 $i,j$ の更新,を繰り返す」という手続きで表現できる.ここで,可能な編集操作は,次のものとする.

例えば,$X = \langle a,l,g,o,r,i,t,h,m \rangle$に編集操作を適用し,$Z=\langle a,l,t,r,u,i,s,t,i,c \rangle$を得る過程の例を示す. ここで,$X$の太字と$Z$のアスタリスク(*)は,操作対象の添字 $i,j$ を表す.$Z$ の アンダーバー (_) は,空文字を表す.

現在の $X$ 適用する操作 操作適用後の $Z$ 操作適用後の $i$ 操作適用後の $j$
a l g o r i t h m 初期化 * _ _ _ _ _ _ _ _ _ 1 1
a l g o r i t h m copy a * _ _ _ _ _ _ _ _ 2 2
a l g o r i t h m copy a l * _ _ _ _ _ _ _ 3 3
a l g o r i t h m replace with ‘t’ a l t * _ _ _ _ _ _ 4 4
a l g o r i t h m delete a l t * _ _ _ _ _ _ 5 4
a l g o r i t h m copy a l t r * _ _ _ _ _ 6 5
a l g o r i t h m insert ‘u’ a l t r u * _ _ _ _ 6 6
a l g o r i t h m insert ‘i’ a l t r u i * _ _ _ 6 7
a l g o r i t h m insert ‘s’ a l t r u i s * _ _ 6 8
a l g o r i t h m insert ‘t’ a l t r u i s t * _ 6 9
a l g o r i t h m copy a l t r u i s t i * 7 10
a l g o r i t h m replace with ‘c’ a l t r u i s t i c * 8 11
a l g o r i t h m delete a l t r u i s t i c * 9 11
a l g o r i t h m delete a l t r u i s t i c * 10 11

一般的に,ある文字列を別の文字列に変換する編集過程は複数存在することに注意せよ.

さて,各編集操作$a$にコスト${\rm cost}(a)$が定義されているとすれば,上記の編集過程で要するコストは,次のように計算できる.

本課題では,${\rm cost}(\mbox{copy}) = 0$,${\rm cost}(\mbox{replace}) = {\rm cost}(\mbox{delete}) = {\rm cost}(\mbox{insert}) = 1$とする.したがって,編集過程のコストの総和は$9$である.

一般的に,2つの文字列$X = \langle x_1, x_2, …, x_m \rangle$と$Y = \langle y_1, y_2, …, y_n \rangle$,および編集操作コストが与えられたとき,$X$から$Y$への編集距離とは,$X$を$Y$に変換する編集操作列のコストの最小値である.

編集距離の求め方

編集距離を効率良く求める問題を考える.まず,接頭辞 (prefix) という概念を導入する.

$X$の接頭辞$X_i$($i \in {0, 1, …, m}$),$Y$の接頭辞$Y_j$($j \in {0, 1, …, n}$)の編集距離を$c_{i,j}$と書くと,以下の再帰的な式が成り立つ.

ただし,$d_{x_i \neq y_j}$は,$x_i = y_j$ならば$0$,$x_i \neq y_j$ならば$1$である(注意: クロネッカーのデルタとは異なる). $c_{i,j}$の再帰式のうち,最小値を求める部分は次の編集操作に対応する.

以上のことから,編集距離$d_{m,n}$を求める問題は,部分問題,すなわち編集距離$d_{m-1,n-1}$, $d_{m-1,n}$, $d_{m,n-1}$を求める問題に分解できる.

例えば,$X = \langle Q, U, E, R, Y \rangle$と$Y = \langle I, N, Q, U, I, R, E\rangle$に対して,$c_{i,j}$は次のように求まる.したがって,$X$と$Y$の編集距離は$4$である.

$i \setminus j$ 0 1 2 3 4 5 6 7 $x_i$
0 0 1 2 3 4 5 6 7  
1 1 1 2 2 3 4 5 6 Q
2 2 2 2 3 2 3 4 5 U
3 3 3 3 3 3 3 4 5 E
4 4 4 4 4 4 4 3 4 R
5 5 5 5 5 5 5 4 4 Y
$y_j$   I N Q U I R E  

以上のアルゴリズムを再帰および動的計画法で実装する. 文字列$X = \langle A, T, C, G \rangle$を,C言語では文字列として表現する.

char *x = "ATCG";

これは,文字の配列として文字列を表現することとほぼ等価である.

char x[] = {'A', 'T', 'C', 'G', '\0'};

なお,文字列$X$の要素$x_i$は,C言語ではx[i-1]として表現されることに注意せよ(配列のインデックスが$0$から始まるため).

参考文献