これは、アフィンギャップコストを使用したペアワイズアラインメントを使用して行うことができます。これには、それぞれ長さnおよびmの2つのストリングに対してO(nm)時間がかかります。
まず最初に、使用されるビットまたはバイトに関して、おそらく最小限のパッチを見つける方法はありません。これは、そのような方法があれば、それshortest_patch(x, y)
を計算する関数を使用して、を使用して任意の文字列の最小の圧縮を見つけることができるためですs
。shortest_patch('', s)
コルモゴロフの複雑さは、特定の文字列の可能な限り最短の圧縮は形式的に計算できないことを示しています。 。しかし、ここにあるように編集が空間にクラスター化される傾向がある場合は、通常のレーベンシュタイン距離アルゴリズムを使用して生成されたパッチよりも小さいパッチを見つけることが確かに可能です。
スクリプトを編集する
パッチは通常、CSでは「スクリプトの編集」と呼ばれます。x
ある文字列を別の文字列に変換するための最小限の(挿入数と削除数の観点から)編集スクリプトを見つけることは、等しい文字のすべてのペアが値0を持ち、等しくない文字のすべてのペアが値をy
持つ最適なペアワイズアラインメントを見つけることと同じです。 -infであり、1つの文字列の文字が-
ギャップ文字と整列するすべての位置の値は-1です。配置は簡単に視覚化できます。
st--ing st-i-ng
stro-ng str-ong
これらは、ストリングsting
との2つの最適な配置でありstrong
、モデルではそれぞれコストが-3です。等しくない文字のペアに-infではなく値-1が指定されている場合、コストはレーベンシュタイン距離(挿入数、削除数、置換数)に等しいアラインメントが得られます。
st-ing sti-ng
strong strong
これらは、新しいモデルでの2つの最適な配置であり、それぞれのコストは-2です。
これらが編集スクリプトとどのように対応するかを確認するために、上の文字列を「元の」文字列と見なし、下の文字列を「ターゲット」文字列と見なすことができます。等しくない文字のペアを含む列は置換に対応-
し、上の行にaを含む列は文字の挿入に対応し-
、下の行にaを含む列は文字の削除に対応します。「命令」(C)opy、(D)elete、(I)nsert、および(S)ubstituteを使用して、アライメントから編集スクリプトを作成できます。各命令の後には、アラインメントから消費する列の数を示す数字が続きます。IおよびSの場合は、挿入または置換する対応する文字数が続きます。たとえば、前の2つの配置の編集スクリプトは次のとおりです。
C2, I1"r", S1"o", C2 and C2, S1"r", I1"o", C2
バンチングの増加
mississippi
ここで、とのような文字列がある場合tip
、2つの配置が見つかります
mississippi
------tip--
mississippi
t---i----p-
どちらも-9の同じスコアを持っています:両方とも同じ合計数の挿入、削除、および置換を必要とします。ただし、編集スクリプトをより簡潔に記述できるため、一番上のものを使用することをお勧めしますD6, S1"t", C2, D2
。2番目の編集スクリプトはですS1"t", D3, C1, D4, C1, D1
。
アラインメントアルゴリズムが最初のアラインメントも「優先」するようにするために、ギャップコストを調整して、ギャップのブロックを開始すると、既存のギャップのブロックを継続するよりもコストがかかるようにすることができます。前の列にギャップが含まれていないときにギャップを含む列のコストが-1ではなく-2になるようにすると、効果的に実行しているのは、連続するギャップのブロックの数にペナルティを課すことです(隣接するギャップの各ブロックは明らかに最初の位置を持っています)。このモデルでは、2つの連続したギャップのブロックが含まれているため、上記の最初の配置のコストは-11になります。2番目の配置には、3つの連続したギャップのブロックが含まれているため、コストは-12になります。IOW、アルゴリズムは最初の配置を優先するようになりました。
このモデルは、ギャップコストgを含むすべての整列位置と、ギャップ列の隣接ブロックの最初の位置コストg + sであり、アフィンギャップコストモデルと呼ばれ、O(nm)アルゴリズムが後藤によって与えられました。 1982年:http://www.genome.ist.i.kyoto-u.ac.jp/~aln_user/archive/JMB82.pdf。ギャップオープンコストを増やすと、整列されたセグメントが一緒に束ねられます。経験的に正しく見え、十分に小さいアライメント(パッチに対応)が得られるまで、さまざまなコストパラメータで遊ぶことができます。