スミス・ウォーターマンアルゴリズム

スミス・ウォーターマンアルゴリズムは、局所的な配列アライメントを実行します。つまり、2つの核酸配列またはタンパク質配列間の類似領域を特定します。スミス・ウォーターマンアルゴリズムは、配列全体を調べるのではなく、あらゆる長さのセグメントを比較し、類似度を最適化します。

このアルゴリズムは、1981 年にTemple F. SmithとMichael S. Watermanによって初めて提案されました。 ^{[ 1 ]}変形であるNeedleman–Wunsch アルゴリズムと同様に、Smith–Waterman は動的計画法アルゴリズムです。そのため、使用されているスコアリング システム (置換行列とギャップ スコアリングスキームを含む) に関して最適な局所アライメントを見つけることが保証されるという望ましい特性があります。Needleman –Wunsch アルゴリズムとの主な違いは、負のスコアリング マトリックス セルがゼロに設定されることです。トレースバック手順は、最も高いスコアのマトリックス セルから開始され、スコアがゼロのセルに遭遇するまで進み、最も高いスコアの局所アライメントが得られます。その二次時間計算量のため、大規模な問題に実用的に適用できないことが多く、(Gotoh、1982)、^{[ 2 ]} ( Altschulと Erickson、1986)、^{[ 3 ]および (Myers と Miller、1988) [ 4 ]}などの計算効率の高い代替手段に置き換えられています。

1970年、ソール・B・ニードルマンとクリスチャン・D・ウンシュは、配列アライメントのためのヒューリスティック相同性アルゴリズム（ニードルマン・ウンシュアルゴリズムとも呼ばれる）を提案した。^{[ 5 ]}これは、グローバルアライメントアルゴリズムであり、${\displaystyle O(mn)}$計算手順（${\displaystyle m}$そして${\displaystyle n}$は、整列される 2 つの配列の長さです。これは、グローバル整列を表示するために行列の反復計算を使用します。次の 10 年間、Sankoff ^{[ 6 ]}、Reichert ^{[ 7 ]} 、 Beyer ^{[ 8 ]}らは、遺伝子配列を分析するための代替ヒューリスティック アルゴリズムを考案しました。Sellers は、配列距離を測定するシステムを導入しました。^{[ 9 ]} 1976 年、Waterman らは、元の測定システムにギャップの概念を追加しました。^{[ 10 ]} 1981 年、Smith と Waterman は、ローカル整列を計算する Smith–Waterman アルゴリズムを発表しました。

スミス・ウォーターマンアルゴリズムは、かなり時間がかかります。長さの異なる 2 つのシーケンスを整列させるには、${\displaystyle m}$そして${\displaystyle n}$、${\displaystyle O(m^{2}n+n^{2}m)}$時間が必要です。Gotoh ^{[ 2 ]}と Altschul ^{[ 3 ]}はアルゴリズムを最適化し、${\displaystyle O(mn)}$ステップ。空間計算量はMyersとMiller ^{[ 4 ]}によって最適化された。${\displaystyle O(mn)}$に${\displaystyle O(n)}$（線形）${\displaystyle n}$は、多数の可能な最適アライメントのうちの 1 つだけが必要な場合の、より短いシーケンスの長さです。Chowdhury、Le、および Ramachandran ^{[ 11 ]}は後に、入力シーケンスの全長に対して空間使用量を線形に保ちながら、アルゴリズムのキャッシュパフォーマンスを最適化しました。

近年、様々な生物を対象としたゲノムプロジェクトにより、遺伝子やタンパク質の膨大な配列データが生成され、計算による解析が必要となっている。配列アライメントは、遺伝子間またはタンパク質間の関係性を示し、それらの相同性や機能性の理解を深めるのに役立つ。また、配列アライメントによって保存ドメインやモチーフを明らかにすることもできる。

局所アライメントの動機の一つは、遠縁の生物学的配列間の類似性が低い領域では、正しいアライメントを得ることが困難であるという点です。これは、進化の過程で突然変異によって「ノイズ」が過剰に蓄積され、これらの領域を意味のある形で比較することが不可能になっているためです。局所アライメントでは、このような領域を完全に回避し、正のスコアを持つ領域、つまり進化的に保存された類似性のシグナルを持つ領域に焦点を当てます。局所アライメントの前提条件は、負の期待値スコアです。期待値スコアは、スコアリングシステム（置換行列とギャップペナルティ）がランダムな配列に対して生成する平均スコアとして定義されます。

局所アライメントを使用するもう一つの動機は、最適な局所アライメントに関する信頼性の高い統計モデル（KarlinとAltschulによって開発された）が存在することです。無関係な配列のアライメントは、極値分布に従う最適な局所アライメントスコアを生成する傾向があります。この特性により、プログラムは2つの配列の最適な局所アライメントの期待値を生成できます。これは、無関係な2つの配列が、観測されたスコア以上のスコアを持つ最適な局所アライメントを生成する頻度を示す指標です。期待値が非常に低い場合は、問題の2つの配列が相同である可能性があり、共通の祖先を持つ可能性があることを示しています。

させて${\displaystyle A=a_{1}a_{2}...a_{n}}$そして${\displaystyle B=b_{1}b_{2}...b_{m}}$は整列される配列であり、${\displaystyle n}$そして${\displaystyle m}$長さは${\displaystyle A}$そして${\displaystyle B}$それぞれ。

1. 置換行列とギャップペナルティ方式を決定する。
   • ${\displaystyle s(a,b)}$- 2つの配列を構成する要素の類似度スコア
   • ${\displaystyle W_{k}}$- 長さのあるギャップのペナルティ${\displaystyle k}$
2. スコアリングマトリックスを作成する${\displaystyle H}$そして、その最初の行と最初の列を初期化します。スコアリング行列のサイズは${\displaystyle (n+1)*(m+1)}$行列は0から始まるインデックスを使用します。

   ${\displaystyle H_{k0}=H_{0l}=0\quad for\quad 0\leq k\leq n\quad and\quad 0\leq l\leq m}$

3. 以下の式を用いて採点マトリックスを記入してください。

   ${\displaystyle H_{ij}=\max {\begin{cases}H_{i-1,j-1}+s(a_{i},b_{j}),\\\max _{k\geq 1}\{H_{i-k,j}-W_{k}\},\\\max _{l\geq 1}\{H_{i,j-l}-W_{l}\},\\0\end{cases}}\qquad (1\leq i\leq n,1\leq j\leq m)}$

   どこ

   ${\displaystyle H_{i-1,j-1}+s(a_{i},b_{j})}$整列のスコアは${\displaystyle a_{i}}$そして${\displaystyle b_{j}}$、

   ${\displaystyle H_{i-k,j}-W_{k}}$スコアは${\displaystyle a_{i}}$長さのギャップの端にある${\displaystyle k}$、

   ${\displaystyle H_{i,j-l}-W_{l}}$スコアは${\displaystyle b_{j}}$長さのギャップの端にある${\displaystyle l}$、

   ${\displaystyle 0}$類似点がないことを意味します${\displaystyle a_{i}}$そして${\displaystyle b_{j}}$。

4. トレースバック。スコアリングマトリックスの最高スコアから開始します。${\displaystyle H}$そして、スコアが0のマトリックスセルに到達したら、各スコアのソースに基づいて再帰的にトレースバックを行い、最適なローカルアライメントを生成します。

スミス・ウォーターマンアルゴリズムは、一致/不一致（置換とも呼ばれる）、挿入、および削除によって2つの配列を整列させます。挿入と削除はどちらもギャップを導入する操作であり、ギャップはダッシュで表されます。スミス・ウォーターマンアルゴリズムにはいくつかのステップがあります。

1. 置換行列とギャップペナルティ方式を決定します。置換行列は、塩基またはアミノ酸の各ペアに、一致または不一致のスコアを割り当てます。通常、一致には正のスコアが与えられ、不一致には比較的低いスコアが与えられます。ギャップペナルティ関数は、ギャップの開設または拡張に対するスコアコストを決定します。ユーザーは、目的に応じて適切なスコアリングシステムを選択することをお勧めします。さらに、置換行列とギャップペナルティのさまざまな組み合わせを試してみるのも良いでしょう。
2. スコアリング行列を初期化します。スコアリング行列の次元は、各シーケンスの長さにそれぞれ1を加えた値です。最初の行と最初の列のすべての要素は0に設定されます。追加の最初の行と最初の列により、任意の位置でシーケンスを別のシーケンスにアラインメントすることが可能になり、それらを0に設定することで、末端のギャップがペナルティの対象外となります。
3. 採点：マトリックス内の各要素を左から右、上から下の順に採点します。その際、置換（対角線上の得点）やギャップの追加（水平方向および垂直方向の得点）の結果を考慮します。いずれの得点も正の値でない場合は、その要素の得点は0となります。それ以外の場合は、最も高い得点が使用され、その得点の根拠が記録されます。
4. トレースバック。最も高いスコアを持つ要素から開始し、各スコアの発生源に基づいて再帰的にトレースバックを行い、0に到達するまで続けます。このプロセスでは、指定されたスコアリングシステムに基づいて最も高い類似度スコアを持つセグメントが生成されます。2番目に優れたローカルアライメントを取得するには、最良のアライメントのトレースの外側にある2番目に高いスコアから開始してトレースバックプロセスを適用します。

Needleman–Wunschアルゴリズムとの比較

スミス・ウォーターマンアルゴリズムは、類似性のある2つの配列のセグメントを検出するのに対し、ニードルマン・ウンシュアルゴリズムは、2つの完全な配列を整列させます。したがって、両者は異なる目的で使用されます。どちらのアルゴリズムも、置換行列、ギャップペナルティ関数、スコアリング行列、およびトレースバックプロセスの概念を使用します。主な違いは次の3点です。

最も重要な違いの一つは、スミス・ウォーターマンアルゴリズムのスコアリングシステムでは負のスコアが割り当てられないことであり、これにより局所的なアライメントが可能になります。いずれかの要素のスコアがゼロより低い場合、その位置までの配列には類似性がないことを意味します。この場合、その要素のスコアはゼロに設定され、以前のアライメントの影響が排除されます。このようにして、計算はその後任意の位置でアライメントを見つけるために継続されます。

Smith–Watermanアルゴリズムの初期スコアリングマトリックスでは、一方の配列の任意のセグメントを他方の配列の任意の位置にアライメントすることが可能です。しかし、Needleman–Wunschアルゴリズムでは、配列全体をアライメントするために、末端ギャップペナルティも考慮する必要があります。

ギャップペナルティ

ギャップペナルティは、挿入または削除に対するスコアを指定します。単純なギャップペナルティ戦略は、各ギャップに固定スコアを使用することです。しかし、生物学では、実際的な理由からスコアを異なる方法でカウントする必要があります。一方では、2 つの配列間の部分的な類似性は一般的な現象です。他方では、単一の遺伝子変異イベントによって、単一の長いギャップが挿入される可能性があります。したがって、長いギャップを形成する連結したギャップは、散在する複数の短いギャップよりも通常は好ましいです。この違いを考慮に入れるために、ギャップ開始とギャップ拡張の概念がスコアリングシステムに追加されました。ギャップ開始スコアは通常、ギャップ拡張スコアよりも高くなります。たとえば、EMBOSS Waterのデフォルトパラメータは、ギャップ開始 = 10、ギャップ拡張 = 0.5 です。

ここでは、ギャップペナルティの2つの一般的な戦略について説明します。その他の戦略については、 「ギャップペナルティ」を参照してください。${\displaystyle W_{k}}$長さのギャップに対するギャップペナルティ関数をとする。${\displaystyle k}$:

リニア

線形ギャップペナルティでは、ギャップを開く場合とギャップを広げる場合で同じスコアが適用されます。

${\displaystyle W_{k}=kW_{1}}$、

どこ${\displaystyle W_{1}}$これは、単一のギャップのコストです。

ギャップペナルティはギャップ長に正比例します。線形ギャップペナルティを使用する場合、スミス・ウォーターマンアルゴリズムは次のように簡略化できます。

${\displaystyle H_{ij}=\max {\begin{cases}H_{i-1,j-1}+s(a_{i},b_{j}),\\H_{i-1,j}-W_{1},\\H_{i,j-1}-W_{1},\\0\end{cases}}}$

簡略化されたアルゴリズムは${\displaystyle O(mn)}$手順。要素のスコアリングを行う際には、その要素に直接隣接する要素からのギャップペナルティのみを考慮する必要があります。

アフィン

アフィンギャップペナルティは、ギャップの開始と拡張を別々に考慮します。

${\displaystyle W_{k}=uk+v\quad (u>0,v>0)}$、

どこ${\displaystyle v}$ギャップオープニングペナルティであり、${\displaystyle u}$はギャップ延長ペナルティです。例えば、長さ2のギャップに対するペナルティは${\displaystyle 2u+v}$。

オリジナルのSmith–Watermanアルゴリズム論文では、任意のギャップペナルティが使用されていました。${\displaystyle O(m^{2}n)}$そのため、ステップ数が多く、かなりの時間を要します。Gotoh はアフィンギャップペナルティのステップ数を最適化し、${\displaystyle O(mn)}$^{[ 2 ]}しかし、最適化されたアルゴリズムは最適なアライメントを1つだけ見つけようと試みるだけであり、最適なアライメントが見つかることは保証されていない。^{[ 3 ]} Altschulは、計算複雑性を維持しながらすべての最適なアライメントを見つけるようにGotohのアルゴリズムを修正した。^{[ 3 ]}その後、MyersとMillerは、GotohとAltschulのアルゴリズムは、1975年にHirschbergによって発表された方法に基づいてさらに修正できることを指摘し、^{[ 12 ]}この方法を適用した。^{[ 4 ]} MyersとMillerのアルゴリズムは、2つの配列をアライメントすることができる。${\displaystyle O(n)}$スペース、${\displaystyle n}$短い方のシーケンスの長さである。Chowdhury、Le、およびRamachandran ^{[ 11 ]}は後に、Hirschberg が使用したものとは異なる再帰的な分割統治戦略を使用して、線形空間で Gotoh のアルゴリズムをキャッシュ効率よく実行する方法を示した。結果として得られたアルゴリズムは、キャッシュ性能が優れているため、実際には Myers と Miller のアルゴリズムよりも高速に実行される。^{[ 11 ]}

ギャップペナルティの例

配列TACGGGCCCGCTACとTAGCCCTATCGGTCAのアライメントを例にとります。線形ギャップペナルティ関数を使用した場合、結果は次のようになります (アライメントは EMBOSS Water によって実行されました。置換マトリックスは DNAfull (類似度スコア: 一致する文字には +5、それ以外は -4)。ギャップの開始と延長はそれぞれ 0.0 と 1.0 です)。

TACGGGCCCGCTA-CTA---G-CC-CTATC

アフィンギャップペナルティを使用した場合、結果は次のようになります（ギャップの開始と拡張はそれぞれ5.0と1.0です）。

TACGGGCCCGCTATA---GCC--CTA

この例は、アフィンギャップペナルティが散在する小さなギャップを回避するのに役立つことを示している。

DNA配列TGTTACGGとGGTTGACTAのアライメントを例にとります。以下のスキームを使用してください。

• 置換行列：${\displaystyle s(a_{i},b_{j})={\begin{cases}+3,\quad a_{i}=b_{j}\\-3,\quad a_{i}\neq b_{j}\end{cases}}}$
• ギャップペナルティ：${\displaystyle W_{k}=2k}$（線形ギャップペナルティ${\displaystyle W_{1}=2}$）

下記に示すスコアリングマトリックスを初期化し、データを入力します。この図は、最初の3つの要素のスコアリングプロセスを示しています。黄色は、評価対象となる塩基を示しています。赤色は、評価対象の細胞における最高スコアを示しています。

完成したスコアリングマトリックスは、左下に示されています。青色は最高スコアを示しています。1つの要素が複数の要素からスコアを受け取る場合、その要素を遡るとそれぞれ異なるパスが形成されます。最高スコアが複数ある場合は、それぞれの最高スコアから遡って処理する必要があります。遡及処理は右下に示されています。最適なローカルアライメントは逆方向に生成されます。

アライメント結果は以下のとおりです。

GTT - AC GTTGAC

Smith–Waterman アルゴリズムの実装である SSEARCH は、UVA FASTA Downloadsから入手できるFASTA配列解析パッケージに含まれています。この実装には、 Wozniak (1997) のアプローチ^{[ 13 ]}の修正と Farrar ^{[ 14 ]}によって開発された SSE2 ベクトル化を使用して比較を 10～20 倍高速化するPowerPC G4 および G5 プロセッサ用の Altivec アクセラレーション コードが含まれており、最適なタンパク質配列データベース検索が非常に実用的になっています。ライブラリ SSW は、Farrar の実装を拡張して、最適な Smith–Waterman スコアに加えてアライメント情報を返すようにしています。^{[ 15 ]}

遺伝子データの急速な増加は、既存のDNA配列アライメントアルゴリズムの処理速度に課題を突きつけている。効率的かつ正確なDNA変異検出手法には、リアルタイムでの並列処理を実現する革新的なアプローチが不可欠である。

• バイオインフォマティクス
• 配列アライメント
• シーケンスマイニング
• ニードルマン・ウンシュアルゴリズム
• レーベンシュタイン距離
• 爆発
• FASTA

• JAligner —スミス・ウォーターマンアルゴリズムのオープンソースJava実装
• BABA —アルゴリズムを視覚的に説明するアプレット（ソースコード付き）
• FASTA/SSEARCH — EBIのサービスページ
• UGENE Smith–Watermanプラグイン— C++で記述されたグラフィカルインターフェースを備えた、SSEARCH互換のオープンソースアルゴリズム実装
• OPAL —大規模な最適配列アライメントのためのSIMD C/C++ライブラリ
• diagonalsw — MITライセンスの下で提供される、SIMD命令セット（特にSSE4.1）を備えたオープンソースのC/C++実装。
• SSW — MITライセンスの下でSmith–WatermanアルゴリズムのSIMD実装へのAPIを提供するオープンソースC++ライブラリ
• メロディーシーケンスアライメント—メロディーシーケンスアライメントのためのJavaScript実装
• DRAGMAPは、Illumina DRAGEN FPGA実装のC++移植版です。