２つの文字列の類似度を考えてみます。

＝＝前置き＝＝
類似度は次のように計算します。 ２つの文字列を端から対応する１対に文字ごとに比較していきます。一対の文字が同じなら０、違う文字なら２として、これを左から右に繰り返して総和を求めます。

即ち、似ているほど類似度は小さい値になります。

例えば、 abcd と abcd は類似度０
abcc と abcd の類似度は２
abcb と adac の類似度は６ です。

これだけなら簡単ですが、もう１つ新しい要素を加えます。 文字列に*マークをいくつでも加えられるとします。そして比較する文字対の一方が*の場合は類似度１とします。

例えば、
abcd と ab*d の類似度は１
a*cd と ab*d の類似度は２ です。

ここで　* は、類似度の数値を最低にするように挿入しなくてはいけないものとします。
例えば、
abcdとacdの類似度はacdに*を挿入し、a*cdとすることにより類似度は１になります。

＝＝ここから本番＝＝
それでは、２つの文字列に*を挿入し、類似度数を最少にする方法を示します。
ここでは　abc　とac　の類似度計算を例にとって説明します。

類似度の計算には、２つの表を使います（(1)類似度数表、(2)選択表）。

先ず、２つの初期表を用意します。

類似度数表

 選択表

次に、類似度表の空いたマスに数値を書き込んでいきます。 空いたマスの数値を計算するには、隣接する左、左下、下 の３つのマスが数値で埋まっていなくてはなりません。次の図は、隣接３マスから右上のマスの類似度を計算する方法です。

右上のマスの数値は次のどちらかになります。
min(X+1,Z+1,Y) または、min(X+1,Z+1,Y+2)です。
この２つの違いは、比較する文字が同じか否かで決まります。

例えば、次の図で？マスの数値を計算する時は、比較する文字がＡとＡなので、
min(X+1,Z+1,Y) を用います。比較する文字が違う場合min(X+1,Z+1,Y+2)を用います。

？セルの場合をまとめると、比較する文字がA同士で同じため、min(X+1,Y,Z+1)はmin(2,0,2)となり、0になります。 この場合、minで選ばれたのは左下なので、選択表の？のマスに左下と書き込みます。 これを繰り返して完成したものが次です。

類似度表完成

 選択表完成

類似度表の右上隅がＡＢＣとＡＣの類似度で、ＡＣはＡ＊Ｃになって、１となります。
選択表を右上からたどるとどこに＊が入るのかが分かります。
左から来た場合は縦の文字列に＊が入り、Ａ＊Ｃとなります。
下から来た場合（上の図にはありませんが）、横の文字列に＊が入ります。

＝＝
（すみません）話がゴチャゴチャして、よくわかりませんよね。
これは来週の生物分子の授業内容です。授業では生物のアミノ酸の配列（文字列）を比較して種の間の類似度を計算します。例えば、人とウサギは、人と人参の関係より近い、なんてのを計算します。