Smith–Watermanアルゴリズム

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
クラス配列アラインメント
最悪の場合の パフォーマンス
最悪の場合の スペースの複雑さ
ステップを段階的に示すアニメーションの例。詳細な手順については、こちらをご覧ください。

Smith–Watermanアルゴリズムは、ローカルシーケンスアラインメントを実行します。つまり、核酸配列またはタンパク質配列の2つのストリング間の類似領域を決定するためです。Smith-Watermanアルゴリズムは、シーケンス全体を調べる代わりに、可能なすべての長さのセグメントを比較し類似度を最適化します。

このアルゴリズムは、1981年にTempleF.SmithMichaelS.Watermanによって最初に提案されました。 [1]バリエーションであるNeedleman-Wunschアルゴリズムと同様に、Smith-Watermanは動的計画法アルゴリズムです。そのため、使用されているスコアリングシステム(置換行列ギャップスコアリングスキームを含む)に関して最適なローカルアライメントを見つけることが保証されるという望ましい特性があります。Needleman-Wunschアルゴリズムとの主な違い負のスコアの行列セルがゼロに設定されているため、(したがって正のスコアの)ローカルアライメントが表示されます。トレースバック手順は、スコアが最も高いマトリックスセルから始まり、スコアがゼロのセルに遭遇するまで続き、スコアが最も高いローカルアライメントが生成されます。時間と空間の2次の複雑さのために、大規模な問題に実際に適用できないことが多く、(Gotoh、1982)、[2]Altschul and Erickson、 1986)、[3]および(Myers and Miller、1988)。[4]

歴史

1970年、ソールB.ニードルマンとクリスチャンD.ヴンシュは、ニードルマン-ブンシュアルゴリズムとも呼ばれる、配列アラインメントのためのヒューリスティックな相同性アルゴリズムを提案しました。[5]これはグローバルアラインメントアルゴリズムであり、計算ステップ(整列されている2つのシーケンスの長さです)。グローバルアラインメントを示す目的で、マトリックスの反復計算を使用します。次の10年間で、Sankoff、[6] Reichert、[7] Beyer [8]などは、遺伝子配列を分析するための代替ヒューリスティックアルゴリズムを策定しました。売り手は、シーケンス距離を測定するためのシステムを導入しました。[9] 1976年に、ウォーターマン等。元の測定システムにギャップの概念を追加しました。[10] 1981年、スミスとウォーターマンは、ローカルアラインメントを計算するためのスミス-ウォーターマンアルゴリズムを公開しました。

Smith–Watermanアルゴリズムは、かなり時間がかかります。2つの長さのシーケンスを整列させる時間がかかります。Gotoh [2]とAltschul [3]は、アルゴリズムを次のように最適化しました。ステップ。スペースの複雑さは、Myers andMiller [4]によって最適化されました(線形)、ここでは短いシーケンスの長さであり、多くの可能な最適なアラインメントのうちの1つだけが必要な場合です。

モチベーション

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

ローカルアラインメントの動機の1つは、離れた場所にある生物学的配列間の類似性が低い領域で正しいアラインメントを取得することが難しいことです。ローカルアラインメントは、そのような領域を完全に回避し、正のスコアを持つ領域、つまり、進化的に保存された類似性のシグナルを持つ領域に焦点を合わせます。ローカルアラインメントの前提条件は、負の期待スコアです。期待スコアは、スコアリングシステム(置換行列ギャップペナルティ)がランダムシーケンスに対して生成する平均スコアとして定義されます。

ローカルアラインメントを使用するもう1つの動機は、最適なローカルアラインメントのための信頼できる統計モデル(KarlinとAltschulによって開発された)があることです。無関係なシーケンスのアラインメントは、極値分布に従う最適なローカルアラインメントスコアを生成する傾向があります。このプロパティにより、プログラムは2つのシーケンスの最適なローカルアラインメントの期待値を生成できます。これは、2つの無関係なシーケンスが、観測されたスコア以上のスコアを持つ最適なローカルアラインメントを生成する頻度の尺度です。非常に低い期待値は、問題の2つのシーケンスが相同である可能性があることを示します。つまり、共通の祖先を共有している可能性があります。

アルゴリズム

Smith–Watermanアルゴリズムのスコアリング方法

させて整列されるシーケンスであり、ここでの長さですそれぞれ。

  1. 置換行列とギャップペナルティスキームを決定します。
    • -2つのシーケンスを構成する要素の類似度スコア
    • -長さのあるギャップのペナルティ
  2. スコアリングマトリックスを作成する最初の行と最初の列を初期化します。スコアリングマトリックスのサイズは次のとおりです。マトリックスは0ベースのインデックスを使用します。
  3. 次の式を使用してスコアリングマトリックスを入力します。
    どこ
    アラインメントのスコアです
    スコアは長さのギャップの終わりにあります
    スコアは長さのギャップの終わりにあります
    まで類似性がないことを意味します
  4. トレースバック。スコアリングマトリックスの最高スコアから開始スコアが0のマトリックスセルで終了し、各スコアのソースに基づいて再帰的にトレースバックし、最適なローカルアライメントを生成します。

説明

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

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

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

グローバルおよびローカルシーケンスアラインメント

Smith-Watermanアルゴリズムは、類似性のある2つのシーケンス内のセグメントを検出しますが、Needleman-Wunschアルゴリズムは、2つの完全なシーケンスを整列させます。したがって、それらは異なる目的を果たします。どちらのアルゴリズムも、置換行列、ギャップペナルティ関数、スコアリング行列、およびトレースバックプロセスの概念を使用します。3つの主な違いは次のとおりです。

Smith–Watermanアルゴリズム ニードルマン-ブンシュアルゴリズム
初期化 最初の行と最初の列は0に設定されます 最初の行と最初の列はギャップペナルティの対象となります
スコアリング 負のスコアは0に設定されます スコアはマイナスになる可能性があります
トレースバック 最高のスコアから始めて、0に遭遇したときに終了します マトリックスの右下のセルから開始し、左上のセルで終了します

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

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

置換行列

各塩基置換またはアミノ酸置換にはスコアが割り当てられます。一般に、一致には正のスコアが割り当てられ、不一致には比較的低いスコアが割り当てられます。例としてDNA配列を取り上げます。一致が+1、不一致が-1の場合、置換行列は次のようになります。

A G C T
A 1 -1 -1 -1
G -1 1 -1 -1
C -1 -1 1 -1
T -1 -1 -1 1

この置換行列は、次のように説明できます。

異なる塩基置換またはアミノ酸置換は、異なるスコアを持つことができます。アミノ酸の置換行列は通常、塩基の置換行列よりも複雑です。PAMBLOSUMを参照してください

ギャップペナルティ

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

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

リニア

線形ギャップペナルティ関数が使用される場合の簡略化されたSmith–Watermanアルゴリズム

線形ギャップペナルティは、ギャップを開いたり拡張したりする場合と同じスコアになります。

どこ単一のギャップのコストです。

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

簡略化されたアルゴリズムはステップ。要素がスコアリングされるとき、この要素に直接隣接する要素からのギャップペナルティのみを考慮する必要があります。

アフィン

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

どこギャップオープニングペナルティであり、ギャップ拡張ペナルティです。たとえば、長さ2のギャップに対するペナルティは次のとおりです。

元のSmith–Watermanアルゴリズムの論文では、任意のギャップペナルティが使用されていました。それは使用していますしたがって、ステップは非常に時間がかかります。Gotohは、アフィンギャップペナルティの手順を次のように最適化しました。[2]ただし、最適化されたアルゴリズムは1つの最適な配置を見つけようとするだけであり、最適な配置が見つかるとは限りません。[3] Altschulは、計算の複雑さを維持しながら、すべての最適な配置を見つけるようにGotohのアルゴリズムを変更しました。[3]その後、マイヤーズとミラーは、後藤とアルトシュルのアルゴリズムは、1975年にヒルシュベルクによって公開された方法[11]に基づいてさらに修正できることを指摘し、この方法を適用しました。[4] MyersとMillerのアルゴリズムは、次を使用して2つのシーケンスを整列させることができます。スペース、短いシーケンスの長さです。

ギャップペナルティの例

例として、シーケンスTACGGGCCCGCTACおよびTAGCCCTATCGGTCAのアラインメントを取り上げます。線形ギャップペナルティ関数を使用すると、結果は次のようになります(EMBOSS Waterによって実行されるアライメント。置換マトリックスはDNAfullです。ギャップの開口部と拡張性は両方とも1.0です)。

TACGGGCCCGCTA-C

TA --- G-CC-CTATC

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

TACGGGCCCGCTA

TA --- GCC--CTA

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

スコアリングマトリックス

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

b 1 ..。 b j ..。 b m
0 0 ..。 0 ..。 0
a 1 0
..。 ..。
a i 0
..。 ..。
a n 0

例として、 DNA配列TGTTACGGGGTTGACTAのアラインメントを取り上げます。次のスキームを使用します。

  • 置換マトリックス:
  • ギャップペナルティ:(線形ギャップペナルティ)。

以下に示すように、スコアリングマトリックスを初期化して入力します。この図は、最初の3つの要素のスコアリングプロセスを示しています。黄色は、検討中の塩基を示します。赤い色は、スコアリングされるセルの最高スコアを示します。

スコアリングマトリックスの初期化(左1)と最初の3つの要素のスコアリングプロセス(左2–4)

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

スミス-ウォーターマン-アルゴリズム-例-Step2.png
スミス-ウォーターマン-アルゴリズム-例-Step3.png
完成したスコアマトリックス(最高スコアは青) トレースバックプロセスとアライメント結果

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

GTT-AC 
GTTGAC 

実装

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

加速バージョン

FPGA

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

2011年の修士論文[17]には、FPGAベースのSmith-Watermanアクセラレーションの分析が含まれています。

ザイリンクスSDAccelでコンパイルされた2016年の出版物OpenCLコードでは、ゲノムシーケンスを高速化し、CPU /GPUパフォーマンス/Wを12〜21倍上回り、非常に効率的な実装が提示されました。ザイリンクスVirtex-72000TFPGAを搭載した1枚のPCIeFPGAカードを使用すると、ワットレベルあたりのパフォーマンスはCPU / GPUよりも12〜21倍優れていました。

GPU

ローレンスリバモア国立研究所と米国エネルギー省の合同ゲノム研究所は、グラフィックスプロセッシングユニット(GPU)を使用してスミス-ウォーターマンローカルシーケンスアラインメント検索の高速バージョンを実装し、予備的な結果はソフトウェア実装の2倍のスピードアップを示しました。[18]同様の方法が1997年以来、同じスピードアップ係数でBiofacetソフトウェアにすでに実装されています。[19]

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

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

CUDAでの11の異なるSW実装が報告されており、そのうち3つは30倍のスピードアップを報告しています。[21]

SIMD

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

アルゴリズムのSSE2ベクトル化(Farrar、2007)が利用可能になり、SSE2拡張機能を備えたIntel / AMDプロセッサで8〜16倍の高速化を実現します。[13] Coreマイクロアーキテクチャを使用してIntelプロセッサで実行する場合、SSE2実装は20倍の増加を達成します。FarrarのSSE2実装は、 FASTAシーケンス比較パッケージのSSEARCHプログラムとして利用できます。SSEARCHは、EuropeanBioinformaticsInstituteの一連の類似性検索プログラムに含まれています。

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

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

現在、Smith–Watermanを加速するSSEソリューションとFPGAソリューションの両方を提供するバイオインフォマティクスの唯一の企業であるCLC bioは、 CLCBioinformaticsCubeを使用した標準的なソフトウェア実装よりも110以上の高速化を達成しました。[要出典]

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

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

Cell BroadbandEngine

2008年、Farrar [24]は、Striped Smith–Waterman [13]CellBroadbandEngineへの移植について説明し、 IBMQS20ブレードSonyPlayStation3でそれぞれ32と12GCUPSの速度を報告しました。

制限事項

遺伝子データの急速な拡大は、現在のDNA配列アラインメントアルゴリズムの速度に挑戦します。DNA変異体を発見するための効率的で正確な方法に対する本質的なニーズには、リアルタイムでの並列処理のための革新的なアプローチが必要です。光コンピューティングのアプローチは、現在の電気的実装の有望な代替手段として提案されています。OptCAMはそのようなアプローチの例であり、Smith–Watermanアルゴリズムよりも高速であることが示されています。[25]

も参照してください

参照

  1. ^ スミス、テンプルF.&ウォーターマン、マイケルS.(1981)。「一般的な分子サブシーケンスの識別」 (PDF)分子生物学ジャーナル147(1):195–197。CiteSeerX10.1.1.63.2897 _ 土井10.1016 / 0022-2836(81)90087-5PMID7265238 _
  2. ^ a b c 後藤修(1982)。「生物学的配列を照合するための改良されたアルゴリズム」。分子生物学ジャーナル162(3):705–708。CiteSeerX10.1.1.204.203_ 土井10.1016 / 0022-2836(82)90398-9PMID7166760_  
  3. ^ a b c d Stephen F. Altschul&Bruce W. Erickson(1986)。「アフィンギャップコストを使用した最適な配列アラインメント」。数学的生物学の会報48(5–6):603–616。土井10.1007/BF02462326PMID3580642_ S2CID189889143_  
  4. ^ a b c Miller、Webb; マイヤーズ、ユージーン(1988)。「線形空間での最適な配置」。バイオインフォマティクス4(1):11–17。CiteSeerX10.1.1.107.6989_ 土井10.1093 / bioinformatics/4.1.11PMID3382986_  
  5. ^ ソール・B・ニードルマン; クリスチャンD.ウンシュ(1970)。「2つのタンパク質のアミノ酸配列の類似性の検索に適用できる一般的な方法」。分子生物学ジャーナル48(3):443–453。土井10.1016 / 0022-2836(70)90057-4PMID5420325_ 
  6. ^ Sankoff D.(1972)。「削除/挿入の制約下でのシーケンスのマッチング」アメリカ合衆国科学アカデミー紀要69(1):4–6。Bibcode1972PNAS ... 69....4S土井10.1073/pnas.69.1.4PMC427531_ PMID4500555_  
  7. ^ トーマスA.ライヘルト; ドナルドN.コーエン; アンドリューKCウォン(1973)。「遺伝子変異とポリペプチド配列のマッチングへの情報理論の応用」。理論生物学ジャーナル42(2):245–261。Bibcode1973JThBi..42..245R土井10.1016 / 0022-5193(73)90088-XPMID4762954_ 
  8. ^ William A. Beyer、Myron L. Stein、Temple F. Smith、およびStanislaw M. Ulam(1974)。「分子配列メトリックと進化系統樹」。数学的生物科学19(1–2):9–25。土井10.1016 / 0025-5564(74)90028-5{{cite journal}}:CS1 maint:複数の名前:著者リスト(リンク
  9. ^ ピーターH.セラーズ(1974)。「進化的距離の理論と計算について」。Journal ofAppliedMathematics26(4):787–793。土井10.1137/0126070
  10. ^ MSウォーターマン; TFスミス; WA Beyer(1976)。「いくつかの生物学的配列測定基準」数学の進歩20(3):367–387。土井10.1016 / 0001-8708(76)90202-4
  11. ^ DS Hirschberg(1975)。「最大の共通部分列を計算するための線形空間アルゴリズム」。ACMの通信18(6):341–343。CiteSeerX10.1.1.348.4774_ 土井10.1145/360825.360861S2CID207694727_  
  12. ^ Wozniak、Andrzej(1997)。「ビデオ指向の命令を使用してシーケンス比較を高速化する」バイオサイエンスにおけるコンピューターアプリケーション13(2):145–50。土井10.1093 / bioinformatics/13.2.145PMID9146961_ 
  13. ^ a b c Farrar、Michael S.(2007)。「StripedSmith–Watermanは、他のSIMD実装よりもデータベース検索を6倍高速化します」。バイオインフォマティクス23(2):156–161。土井10.1093 / bioinformatics/btl582PMID17110365_ 
  14. ^ 趙、Mengyao; イ・ワンピン; ギャリソン、エリックP; マース、ガボールT(2013年12月4日)。「SSWライブラリ:ゲノムアプリケーションで使用するためのSIMD Smith-Waterman C /C++ライブラリ」PLOSONE8(12):e82138。arXiv1208.6350Bibcode2013PLoSO...882138Z土井10.1371/journal.pone.0082138PMC3852983_ PMID24324759_  
  15. ^ FPGA 100xペーパー:「アーカイブされたコピー」(PDF)2008年7月5日にオリジナル(PDF)からアーカイブされました2007年10月17日取得 {{cite web}}:CS1 maint:タイトルとしてアーカイブされたコピー(リンク「アーカイブされたコピー」(PDF)2008年7月5日にオリジナル(PDF)からアーカイブされました2007年10月17日取得 {{cite web}}:CS1 maint:タイトルとしてアーカイブされたコピー(リンク、および「アーカイブされたコピー」(PDF)2011年7月20日にオリジナル(PDF)からアーカイブされました2007年10月17日取得 {{cite web}}:CS1 maint:タイトルとしてアーカイブされたコピー(リンク
  16. ^ ProgeniqPte。Ltd.、「ホワイトペーパー-計算ワークフローのボトルネックを解消するための10倍から50倍の高速化による集中的なアプリケーションの高速化」。
  17. ^ Vermij、Erik(2011)。スーパーコンピューティングプラットフォームでの遺伝子配列アラインメント(PDF)(M.Sc. thesis)デルフト工科大学。2011年9月30日にオリジナル(PDF)からアーカイブされました2011年8月17日取得
  18. ^ 劉、ヤン; 黄、ウェイン; ジョンソン、ジョン; Vaidya、Sheila(2006)。GPU Accelerated Smith–Watermanコンピュータサイエンスの講義ノート3994。SpringerLink。pp。188–195。  _ 土井10.1007/11758549_29ISBN 978-3-540-34385-1
  19. ^ 「バイオインフォマティクスの高スループットシーケンスの検索と分析(ホワイトペーパー)」GenomeQuest。2008年5月13日にオリジナルからアーカイブされました2008年5月9日取得
  20. ^ Manavski、Svetlin A.&Valle、Giorgio(2008)。「Smith-Watermanシーケンスアラインメント用の効率的なハードウェアアクセラレータとしてのCUDA互換GPUカード」BMCバイオインフォマティクス9(補足2:S10):S10。土井10.1186/1471-2105-9-S2-S10PMC2323659_ PMID18387198_  
  21. ^ 「CUDAゾーン」Nvidia 2010年2月25日取得
  22. ^ Rognes、Torbjørn; Seeberg、Erling(2000)。「一般的なマイクロプロセッサでの並列処理を使用したSmith–Watermanシーケンスデータベース検索の6倍の高速化」バイオインフォマティクス16(8):699–706。土井10.1093 / bioinformatics/16.8.699PMID11099256_ 
  23. ^ Rognes、Torbjørn(2011)。「シーケンス間SIMD並列化を使用したFasterSmith–Watermanデータベース検索」BMCバイオインフォマティクス12221。doi10.1186/1471-2105-12-221PMC3120707_ PMID21631914_  
  24. ^ Farrar、Michael S.(2008)。「Smith–WatermanをCellBroadbandEngineに最適化する」2012-02-12にオリジナルからアーカイブされました。 {{cite journal}}引用ジャーナルには|journal=ヘルプ)が必要です
  25. ^ マレキ、エサン; Koohi、Somayyeh; Kavehvash、Zahra; マシャギ、アリレザ(2020)。「OptCAM:DNA変異体発見のための超高速全光学アーキテクチャ」バイオフォトニクスジャーナル13(1):e201900227。土井10.1002/jbio.201900227PMID31397961_ 

外部リンク

  • 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ライセンスの下でSmith-WatermanアルゴリズムのSIMD実装にAPIを提供するオープンソースのC++ライブラリ
  • メロディックシーケンスアラインメント—メロディックシーケンスアラインメントのJavaScript実装
  • DRAGMAPイルミナDRAGENFPGA実装のC++ポート