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

手順を段階的に示すアニメーションの例。詳細な手順については、こちらをご覧ください。
クラス	配列アライメント
最悪の場合の パフォーマンス	${\displaystyle O(mn)}$
最悪の場合の 空間複雑度	${\displaystyle O(mn)}$

スミス・ウォーターマンアルゴリズムは、ローカル配列アライメント、つまり、2 つの核酸配列またはタンパク質配列の文字列間の類似領域を決定するために実行されます。スミス・ウォーターマンアルゴリズムは、配列全体を見るのではなく、すべての可能な長さのセグメントを比較し、類似性の尺度を最適化します。

このアルゴリズムは、 1981 年にTemple F. SmithとMichael S. Watermanによって初めて提案されました。^[1]ニードルマン–ヴンシュ アルゴリズムのバリエーションと同様に、スミス–ウォーターマン アルゴリズムは動的計画法アルゴリズムです。そのため、使用されているスコアリング システム (置換マトリックスとギャップ スコアリングスキームを含む) に関して最適なローカル アラインメントを確実に見つけられるという望ましい特性があります。ニードルマン–ヴンシュ アルゴリズムとの主な違いは、負のスコアリング マトリックス セルが 0 に設定されていることです。トレースバック手順は、最高スコア マトリックス セルから開始され、スコアが 0 のセルに遭遇するまで続行され、最高スコア ローカル アラインメントが生成されます。このアルゴリズムは 3 乗の時間計算量であるため、大規模な問題には実際には適用できないことが多く、(Gotoh、1982)、^[2] ( Altschulおよび Erickson、1986)、^[3] (Myers および Miller、1988) などの計算効率の高い代替法に置き換えられます。^[4]

1970 年、Saul B. Needleman と Christian D. Wunsch は、配列アラインメントのためのヒューリスティックな相同性アルゴリズムを提案しました。これは Needleman–Wunsch アルゴリズムとも呼ばれます。^[5]これは、計算ステップ (および は、アラインメントされる 2 つの配列の長さ) を必要とするグローバル アラインメント アルゴリズムです。これは、グローバル アラインメントを示すために、行列の反復計算を使用します。その後の 10 年間で、Sankoff、 ^[6] Reichert、^[7] Beyer ^[8]らは、遺伝子配列を解析するための代替ヒューリスティック アルゴリズムを策定しました。Sellers は、配列距離を測定するシステムを導入しました。^[9] 1976 年、Waterman らは、ギャップの概念を元の測定システムに追加しました。^[10] 1981 年、Smith と Waterman は、ローカル アラインメントを計算する Smith–Waterman アルゴリズムを発表しました。 ${\displaystyle O(mn)}$${\displaystyle m}$${\displaystyle n}$

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

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

ローカル アラインメントの目的の 1 つは、遠縁の生物学的配列間の類似性が低い領域で正しいアラインメントを得るのが難しいことです。これは、進化の過程で突然変異によって「ノイズ」が大きくなりすぎて、それらの領域を意味のある形で比較することができなくなるためです。ローカル アラインメントでは、そのような領域を完全に回避し、スコアが正の領域、つまり進化的に保存された類似性のシグナルを持つ領域に焦点を当てます。ローカル アラインメントの前提条件は、負の期待スコアです。期待スコアは、スコアリング システム (置換マトリックスとギャップ ペナルティ) がランダムな配列に対して生成する平均スコアとして定義されます。

ローカル アラインメントを使用するもう 1 つの理由は、最適なローカル アラインメントのための信頼性の高い統計モデル (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. スコアリング行列を構築し、その最初の行と最初の列を初期化します。スコアリング行列のサイズは です。行列は 0 ベースのインデックスを使用します。 ${\displaystyle H}$${\displaystyle (n+1)*(m+1)}$

   ${\displaystyle H_{k0}=H_{0l}=0\quad \quad 0\leq k\leq n\quad かつ\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_{ik,j}-W_{k}\},\\\max _{l\geq 1}\{H_{i,jl}-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_{ik,j}-W_{k}}$長さのギャップの終わりにある場合のスコアは、${\displaystyle a_{i}}$${\displaystyle k}$

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

   ${\displaystyle 0}$は、およびまで類似性が存在しないことを意味します。${\displaystyle a_{i}}$${\displaystyle b_{j}}$

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

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

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

Smith-Waterman アルゴリズムは、2 つのシーケンスの類似点のあるセグメントを見つけますが、Needleman-Wunsch アルゴリズムは、2 つの完全なシーケンスをアラインメントします。したがって、これらは異なる目的を果たします。両方のアルゴリズムは、置換マトリックス、ギャップ ペナルティ関数、スコアリング マトリックス、およびトレースバック プロセスの概念を使用します。主な違いは次の 3 つです。

最も重要な違いの 1 つは、ローカル アラインメントを可能にする Smith-Waterman アルゴリズムのスコアリング システムでは負のスコアが割り当てられないことです。いずれかの要素のスコアが 0 より低い場合、その位置までのシーケンスに類似点がないことを意味します。この要素は、以前のアラインメントの影響を排除するために 0 に設定されます。このようにして、計算はその後も任意の位置でアラインメントを見つけ続けることができます。

Smith-Waterman アルゴリズムの初期スコアリング マトリックスにより、1 つのシーケンスの任意のセグメントを他のシーケンスの任意の位置にアラインメントできます。ただし、Needleman-Wunsch アルゴリズムでは、完全なシーケンスをアラインメントするために、エンド ギャップ ペナルティも考慮する必要があります。

各塩基置換またはアミノ酸置換にはスコアが割り当てられます。一般的に、一致には正のスコアが割り当てられ、不一致には比較的低いスコアが割り当てられます。DNA 配列を例にとると、一致に +1、不一致に -1 が割り当てられると、置換マトリックスは次のようになります。

この置換マトリックスは次のように記述できます。 ${\displaystyle s(a_{i},b_{j})={\begin{cases}+1,\quad a_{i}=b_{j}\\-1,\quad a_{i}\neq b_{j}\end{cases}}}$

異なる塩基置換またはアミノ酸置換には異なるスコアが付けられる場合があります。アミノ酸の置換マトリックスは通常、塩基の置換マトリックスよりも複雑です。PAM 、BLOSUMを参照してください。

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

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

線形ギャップ ペナルティでは、ギャップを開く場合と拡張する場合のスコアは同じです。

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

単一のギャップのコストは どこになりますか。${\displaystyle W_{1}}$

ギャップ ペナルティはギャップの長さに正比例します。線形ギャップ ペナルティを使用する場合、Smith–Waterman アルゴリズムは次のように簡略化できます。

${\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)}$、

ここで、 はギャップ開始ペナルティ、 はギャップ拡張ペナルティです。たとえば、長さ 2 のギャップのペナルティは です。 ${\displaystyle v}$${\displaystyle u}$${\displaystyle 2u+v}$

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

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

タッグGCCCGCTA-C

TA---G-CC-CTATC

アフィンギャップペナルティを使用すると、結果は次のようになります (ギャップの開口部と拡張はそれぞれ 5.0 と 1.0 です)。

タッググックCCGCTA

TA---GCC--CTA

この例では、アフィン ギャップ ペナルティによって、散在する小さなギャップを回避できることを示しています。

スコアリング マトリックスの機能は、2 つのシーケンスのすべてのコンポーネントを 1 対 1 で比較し、最適なアラインメントの結果を記録することです。スコアリング プロセスは、動的プログラミングの概念を反映しています。最終的な最適なアラインメントは、成長する最適なアラインメントを繰り返し拡張することによって見つけられます。言い換えると、現在の最適なアラインメントは、以前の最適なアラインメントからどのパス (一致/不一致またはギャップの挿入) が最も高いスコアを与えるかを決定することによって生成されます。マトリックスのサイズは、1 つのシーケンスの長さ + 1 と、もう 1 つのシーケンスの長さ + 1 です。追加の最初の行と最初の列は、1 つのシーケンスをもう 1 つのシーケンスの任意の位置にアラインメントするために使用されます。最初の行と最初の列は両方とも 0 に設定されているため、最後のギャップはペナルティを受けません。初期のスコアリング マトリックスは次のとおりです。

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 つの要素のスコアリング プロセスを示しています。黄色は、考慮されているベースを示します。赤色は、スコアリングされているセルの最高スコアを示します。

完成したスコアリング マトリックスは、下の左側に示されています。青色は最高スコアを示しています。要素は複数の要素からスコアを受け取ることができ、この要素をトレースバックすると、それぞれが異なるパスを形成します。最高スコアが複数ある場合は、各最高スコアからトレースバックを実行する必要があります。トレースバック プロセスは、下の右側に示されています。最適なローカル アライメントは、逆方向に生成されます。

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

GTT - AC 
GTTGAC 

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

Cray は、FPGAチップに基づく再構成可能なコンピューティングプラットフォームを使用して Smith–Waterman アルゴリズムの高速化を実証し、標準的なマイクロプロセッサ ベースのソリューションと比較して最大 28 倍の高速化を示しました。Smith–Waterman アルゴリズムの別の FPGA ベース バージョンでは、FPGA (Virtex-4) が 2.2 GHz Opteron プロセッサと比較して最大 100 倍の高速化を示しました^[16]。^[17] TimeLogic DeCypher および CodeQuest システムも、PCIe FPGA カードを使用して Smith–Waterman および Framesearch を高速化します。

2011年の修士論文^[18]には、FPGAベースのスミス-ウォーターマン加速の分析が含まれています。

2016 年の出版物「Xilinx SDAccel でコンパイルされた OpenCL コードがゲノム シーケンシングを高速化し、CPU/GPU のパフォーマンス/W を 12 ～ 21 倍上回る」では、非常に効率的な実装が紹介されました。Xilinx Virtex-7 2000T FPGA を搭載した 1 枚の PCIe FPGA カードを使用すると、ワット レベルのパフォーマンスは CPU/GPU よりも 12 ～ 21 倍優れていました。

ローレンス・リバモア国立研究所と米国エネルギー省の合同ゲノム研究所は、グラフィックス処理装置（GPU）を使用してスミス・ウォーターマン局所配列アライメント検索の高速化バージョンを実装し、予備的な結果ではソフトウェア実装に比べて2倍の高速化が示されました。^[19]同様の方法は、1997年からバイオファセットソフトウェアに実装されており、同じ高速化係数を実現しています。^[20]

NVIDIAのCUDA Cプラットフォームでは、このアルゴリズムのGPU実装もいくつか利用可能です。^[21] Farrarによる最もよく知られているCPU実装（x86アーキテクチャでSIMD命令を使用）と比較すると、単一のNVidia GeForce 8800 GTXカードを使用したこのソリューションのパフォーマンステストでは、小さいシーケンスではパフォーマンスがわずかに向上しますが、大きいシーケンスではパフォーマンスがわずかに低下します。ただし、デュアルNVidia GeForce 8800 GTXカードで同じテストを実行すると、テストされたすべてのシーケンスサイズでFarrar実装のほぼ2倍の速度になります。

SW の新しい GPU CUDA 実装が利用可能になりました。これは以前のバージョンよりも高速で、クエリの長​​さの制限もなくなりました。CUDASW++ を参照してください。

CUDA上で11種類の異なるソフトウェア実装が報告されており、そのうち3つは30倍の高速化を報告している。^[22]

最後に、スミス・ウォーターマン法の他のGPUアクセラレーション実装は、NVIDIAのゲノム解析用ソフトウェアスイートであるNVIDIA Parabricksで見つけることができます。^[23]

2000年に、 Intel Pentium MMXプロセッサや同様の技術で利用可能な単一命令複数データ（SIMD）技術を使用したSmith-Watermanアルゴリズムの高速実装が、 RognesとSeebergの出版物で説明されました。 ^[24] Wozniak（1997）のアプローチとは対照的に、新しい実装は対角ベクトルではなく、クエリシーケンスと平行なベクトルに基づいています。 Sencel Bioinformatics社は、このアプローチをカバーする特許を申請しています。 Sencel社はソフトウェアをさらに開発しており、学術目的での実行ファイルを無料で提供しています。

このアルゴリズムのSSE2ベクトル化 (Farrar、2007) が現在利用可能で、SSE2 拡張機能を備えた Intel/AMD プロセッサで 8 ～ 16 倍の高速化を実現します。^[14] Core マイクロアーキテクチャを使用した Intel プロセッサで実行すると、 SSE2 実装により 20 倍の高速化が実現します。Farrar の SSE2 実装は、 FASTA配列比較パッケージの SSEARCH プログラムとして利用できます。SSEARCH は、欧州バイオインフォマティクス研究所の類似性検索プログラム スイートに含まれています。

公開されているホワイトペーパーによると、デンマークのバイオインフォマティクス企業CLC bio は、 Intel 2.17 GHz Core 2 Duo CPU 上で SSE2 を使用して、標準的なソフトウェア実装に比べて 200 倍近くの高速化を達成しました。

IntelおよびAdvanced Micro Devices (AMD) ベースのLinuxサーバー上の Smith-Waterman アルゴリズムの高速バージョンは、Biocceleration が提供する GenCore 6 パッケージでサポートされています。このソフトウェア パッケージのパフォーマンス ベンチマークでは、同じプロセッサ上の標準ソフトウェア実装と比較して、最大 10 倍の速度向上が示されています。

CLC bio は現在、バイオインフォマティクス分野で唯一、スミス・ウォーターマン法を加速する SSE と FPGA ソリューションの両方を提供している企業であり、CLC Bioinformatics Cube により、標準的なソフトウェア実装に比べて 110 倍以上の高速化を達成しています。^[要出典]

SSSE3を搭載した CPU 上でのアルゴリズムの最高速実装は、SWIPE ソフトウェア (Rognes, 2011) ^[25]で、 GNU Affero General Public Licenseに基づいて利用できます。並行して、このソフトウェアは 16 の異なるデータベース シーケンスの残基を 1 つのクエリ残基と比較します。375 残基のクエリ シーケンスを使用して、デュアル Intel Xeon X5650 6 コア プロセッサ システムで 1 秒あたり 1060 億セル更新 (GCUPS) の速度が達成されました。これは、Farrar の「ストライプ」アプローチに基づくソフトウェアよりも 6 倍以上高速です。BLOSUM50 マトリックスを使用する場合、 BLASTよりも高速です。

CおよびC++でのSmith–Waterman の実装であるdiagonalswは、 SIMD 命令セット ( x86 プラットフォームの場合はSSE4.1 、PowerPC プラットフォームの場合は AltiVec) を使用します。これは、オープンソースのMIT ライセンスの下でリリースされています。

2008年にFarrar ^{[26]はStriped Smith-Waterman [14]の}Cell Broadband Engineへの移植について説明し、 IBM QS20ブレードとSony PlayStation 3でそれぞれ32と12GCUPSの速度を報告した。

遺伝子データの急速な拡大により、現在の DNA 配列アライメント アルゴリズムの速度が課題となっています。DNA 変異体を発見するための効率的かつ正確な方法には、リアルタイムでの並列処理を実現する革新的なアプローチが不可欠です。

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

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