ヒルシュバーグのアルゴリズム

コンピュータサイエンスにおいて、発明者のダン・ヒルシュバーグにちなんで名付けられたヒルシュバーグのアルゴリズムは、 2つの文字列間の最適な配列アラインメントを見つける動的計画法アルゴリズムです。最適性はレーベンシュタイン距離で測定され、これは1つの文字列を他の文字列に変更するために必要な挿入、置換、削除、およびヌルアクションのコスト合計として定義されます。ヒルシュバーグのアルゴリズムは、分割統治法を使用するニードルマン・ヴンシュのアルゴリズムのより空間効率の高いバージョンとして簡単に説明できます。 [ 1 ]^ヒルシュバーグのアルゴリズムは、計算生物学でDNAおよびタンパク質配列の最大グローバルアラインメントを見つけるために一般的に使用されています。

Hirschberg のアルゴリズムは、最適配列アラインメントに一般的に適用できるアルゴリズムです。BLASTとFASTA は、最適ではないヒューリスティックです。およびが文字列である場合 (および) 、Needleman–Wunsch アルゴリズムは、空間を使用して、時間内で最適なアラインメントを見つけます。Hirschberg のアルゴリズムは Needleman–Wunsch アルゴリズムを巧みに修正したもので、依然として時間はかかりますが、必要なのは空間のみであり、実際にははるかに高速です。^{[2]このアルゴリズムの 1 つの用途は、DNA またはタンパク質配列の配列アラインメントを見つけることです。また、Common} diffツール などを使用して、2 つのデータ セット間の最長共通部分配列 を計算するための空間効率の高い方法でもあります。${\displaystyle X}$${\displaystyle Y}$${\displaystyle \operatorname {長さ} (X)=n}$${\displaystyle \operatorname {長さ} (Y)=m}$${\displaystyle O(nm)}$${\displaystyle O(nm)}$${\displaystyle O(nm)}$${\displaystyle O(\min\{n,m\})}$

ヒルシュバーグアルゴリズムは、ニードルマン・ヴンシュアルゴリズムから次のことを観察することで導き出すことができる。^[3]

1. Needleman–Wunschスコア行列の現在の行と前の行のみを保存するだけで、最適なアライメントスコアを計算できます。
2. が の最適配置であり、 がの任意の分割である場合、となるの分割が存在します。${\displaystyle (Z,W)=\operatorname {NW} (X,Y)}$${\displaystyle (X,Y)}$${\displaystyle X=X^{l}+X^{r}}$${\displaystyle X}$${\displaystyle Y^{l}+Y^{r}}$${\displaystyle Y}$${\displaystyle \operatorname {NW} (X,Y)=\operatorname {NW} (X^{l},Y^{l})+\operatorname {NW} (X^{r},Y^{r})}$

${\displaystyle X_{i}}$は のi番目の文字を表します。ここで、 はのi番目からj番目の文字までの範囲のサイズの部分文字列を表します。は の逆バージョンです。 ${\displaystyle X}$${\displaystyle 1\leqslant i\leqslant \operatorname {length} (X)}$${\displaystyle X_{i:j}}$${\displaystyle j-i+1}$${\displaystyle X}$${\displaystyle \operatorname {rev} (X)}$${\displaystyle X}$

${\displaystyle X}$および は整列されるシーケンスです。が の文字、が の文字であるとします。、、 は適切に定義された整数値関数であると仮定します。これらの関数は、それぞれ を削除、 を挿入、に置き換えるコストを表します。 ${\displaystyle Y}$${\displaystyle x}$${\displaystyle X}$${\displaystyle y}$${\displaystyle Y}$${\displaystyle \operatorname {Del} (x)}$${\displaystyle \operatorname {Ins} (y)}$${\displaystyle \operatorname {Sub} (x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$

を定義します。これは、Needleman–Wunsch スコア行列の最後の行を返します。 ${\displaystyle \operatorname {NWScore} (X,Y)}$${\displaystyle \mathrm {Score} (i,j)}$

関数NWScore(X, Y)
    Score(0, 0) = 0 // 2 * (length(Y) + 1) 配列
    j = 1からlength(Y)まで
        Score(0, j) = Score(0, j - 1) + Ins(Y j )
     for i = 1 to length(X) // 配列の初期化
        スコア(1, 0) = スコア(0, 0) + Del(X i )
         、 j = 1から長さ(Y)
            スコアサブ = スコア(0, j - 1) + サブ(X i , Y j )
            スコアDel = スコア(0, j) + Del(X i )
            スコアIns = スコア(1, j - 1) + Ins(Y j )
            スコア(1, j) = max(スコアサブ、スコアデリート、スコアイン)
        終わり
        // Score[1]をScore[0]にコピーする
        スコア(0, :) = スコア(1, :)
    
    j = 0からlength(Y)まで終了
        最終行(j) = スコア(1, j)
    LastLine
を返す

いずれの時点でも、スコア マトリックスの最新の 2 行のみが必要であることに注意してください。したがって、は空間で実装されます。 ${\displaystyle \operatorname {NWScore} }$${\displaystyle \operatorname {NWScore} }$${\displaystyle O(\min\{\operatorname {length} (X),\operatorname {length} (Y)\})}$

Hirschberg アルゴリズムは次のとおりです。

関数Hirschberg(X, Y)
    Z = ""
    W = ""
    長さ(X) == 0
        の場合、 i = 1から長さ(Y)
            Z = Z + '-'
            W = W + Y i
        終了、
    そうでなければlength(Y) == 0
        の場合、 i = 1からlength(X)まで
            Z = Z + X i
            W = W + '-'
        終了
    、そうでなければlength(X) == 1またはlength(Y) == 1の場合
        (Z, W) = ニードルマンウンシュ(X, Y)
    それ以外
        xlen = 長さ(X)
        xmid = 長さ(X) / 2
        ylen = 長さ(Y)

        スコアL = NWScore(X 1:xmid , Y)
        スコアR = NWScore(rev(X xmid+1:xlen ), rev(Y))
        ymid = arg maxスコアL + rev(スコアR)

        (Z,W) = ヒルシュベルク(X 1:xmid , y 1:ymid ) + ヒルシュベルグ(X xmid+1:xlen , Y ymid+1:ylen )
     end 
    return (Z, W)

観測(2)の文脈において、 がの分割であると仮定する。 指数はかつとなるように計算される。 ${\displaystyle X^{l}+X^{r}}$${\displaystyle X}$${\displaystyle \mathrm {ymid} }$${\displaystyle Y^{l}=Y_{1:\mathrm {ymid} }}$${\displaystyle Y^{r}=Y_{\mathrm {ymid} +1:\operatorname {length} (Y)}}$

させて

${\displaystyle {\begin{aligned}X&={\text{AGTACGCA}},\\Y&={\text{TATGC}},\\\operatorname {Del} (x)&=-2,\\\operatorname {Ins} (y)&=-2,\\\operatorname {Sub} (x,y)&={\begin{cases}+2,&{\text{if }}x=y\\-1,&{\text{if }}x\neq y.\end{cases}}\end{aligned}}}$

最適な配置は次のように与えられる。

W = AGTACGCA
 Z = --TATGC-

実際、これは対応するニードルマン・ヴンシュ行列をバックトラックすることで検証できます。

         ＴＡＴＧＣ
     ０   -2 -4 -6 -8 -10
  Ａ  -2   -1 0 -2 -4 -6
  Ｇ  -4   -3 -2 -1 0 -2
  Ｔ   -6   -2   -4 0 -2 -1
  Ａ   -8 -4    0   -2 -1 -3
  Ｃ -10 -6 -2   -1   -3 1
  Ｇ -12 -8 -4 -3    1   -1
  Ｃ -14 -10 -6 -5 -1    3 
 Ａ -16 -12 -8 -7 -3    1

まず、トップレベルの の呼び出しから始めます。これは、最初の引数を半分に分割します: 。 の呼び出しにより、次の行列が生成されます: ${\displaystyle \operatorname {Hirschberg} ({\text{AGTACGCA}},{\text{TATGC}})}$${\displaystyle X={\text{AGTA}}+{\text{CGCA}}}$${\displaystyle \operatorname {NWScore} ({\text{AGTA}},Y)}$

        タットGC
    0 -2 -4 -6 -8 -10
 A -2 -1 0 -2 -4 -6
  G -4 -3 -2 -1 0 -2
  T -6 -2 -4 0 -2 -1
  A -8 -4 0 -2 -1 -3

同様に、次の行列を生成します。 ${\displaystyle \operatorname {NWScore} (\operatorname {rev} ({\text{CGCA}}),\operatorname {rev} (Y))}$

       ＣＧＴＡＴ
    0 -2 -4 -6 -8 -10
 A -2 -1 -3 -5 -4 -6
  C -4 0 -2 -4 -6 -5
  G -6 -2 2 0 -2 -4
  C -8 -4 0 1 -1 -3

それらの最後の行（後者を反転した後）とそれらの合計はそれぞれ

スコアL = [ -8 -4 0 -2 -1 -3 ]
 rev(スコアR) = [ -3 -1 1 0 -4 -8 ]
 合計 = [-11 -5   1 -2 -5 -11]

最大値（太字で表示）は に現れymid = 2、分割 が生成されます。 ${\displaystyle Y={\text{TA}}+{\text{TGC}}}$

ヒルシュベルク再帰全体（簡潔にするために省略）は、次のツリーを生成します。

               (AGTACGCA、TATGC)
               / \
        (AGTA、TA) (CGCA、TGC)
         / \ / \
     (AG、) (TA、TA) (CG、TG) (CA、C)
              / \ / \       
           (T、T) (A、A) (C、T) (G、G)

ツリーの葉には最適な配置が含まれています。

• 最長共通部分列