ほとんどのバイオインフォマティクス分析における最も基本的な計算ステップの1つは、2つのゲノム配列間の相違点/類似点の検出である。Edit distanceとペアワイズアラインメントは、このステップを実現するための2つのアプローチで、近似文字列マッチングとして定式化されている（Navarro、2001）。Edit distance approachは、2つのシーケンスがどれほど異なるかを示す尺度である。シーケンスを他のシーケンスに変換するのに必要な編集の最小数を計算する。編集距離が長いほど、シーケンスは互いに異なる。一般的に許可されている編集操作には、一方または両方のシーケンス内の文字の欠失、挿入、および置換が含まれる。ペアワイズアラインメントは、シーケンスがどれだけ似ているかを示す尺度である。可能な編集操作を表す文字の順序付きリストと、2つの与えられたシーケンスの一方を他方に変更するのに必要な一致であるアライメントを計算する。どの2つのシーケンスでも、編集操作と一致の順序が異なる（したがって異なる整列）場合があるため、整列アルゴリズムには通常バックトラック手順が含まれる。このステップは、最高のアライメントスコアを有するアライメント（最適アライメントと呼ばれる）を見つける。アラインメントスコアは、すべての編集のスコアとユーザー定義のスコアリング関数によって含意されるアラインメントに沿った一致の合計である。編集距離およびペアワイズアラインメントアプローチは、非加法的尺度である（Calude et al、2002）。これは、シーケンスペアを2つの連続したサブシーケンスペアに分割した場合、シーケンスペア全体の編集距離が必ずしも短いペアの編集距離の合計に等しいとは限らないことを意味する。代わりに、2つの入力シーケンスのすべての可能な接頭辞を調べ、最適な解を提供する接頭辞のペアを追跡する必要がある。すべての可能な接頭辞を列挙することは、配列決定エラー（Foxら、2014）および遺伝的変異（McKernanら、2009）の両方から生じる編集を許容するために必要である。したがって、編集距離とペアワイズアライメントのアプローチは通常、同じ接頭辞を何度も再検討することを避けるために動的計画法アルゴリズムとして実装されている。 Levenshtein距離（Levenshtein、1966）、Smith-Waterman（Smith and Waterman、1981）、およびNeedleman-Wunsch（Needleman and Wunsch、1970）などのこれらの実装は、2次の時間と空間の複雑さを持つため非効率である（すなわち、 O(m2) であり、シーケンス長はｍ）である。既存の配列アライナーの性能を高めるために多くの試みがなされた。 30年以上の試みにもかかわらず、最速で知られている編集距離アルゴリズム（Masek and Paterson、1980）は、長さmのシーケンスに対して実行時間O(m2/log2m)を持ち、それはまだほぼ2次である（Backurs and Indyk、2017） 。したがって、より最近の研究は、配列アラインメントおよび編集距離の実行の性能を向上させるために、2つの重要な新しい方向のうちの1つに従う傾向がある。 （2）編集距離しきい値を考慮して、動的計画法アルゴリズムの必要性を減らすフィルタリングヒューリスティックを開発する。
ハードウェアアクセラレータは、計算コストのかかるアライメントおよび編集距離アルゴリズムを高速化するためにますます普及してきている（Al Kawamら、2017; Aluru and Jammula、2014; Ngら、2017; Sandesら、2016）。ハードウェアアクセラレータには、マルチコアおよびSIMD（single instruction multiple data）対応の中央処理装置（CPU）、グラフィック処理装置（GPU）、およびフィールドプログラマブルゲートアレイ（FPGA）がある。
（一部省略）
この研究における著者らの目標は、短い配列の最適なアライメントを計算するのに費やされる時間を大幅に減らし、高いフィルタリング精度を維持することである。この目的のために、Shoujiを導入した。それは新しく、速く、そして非常に正確なプリアライメントフィルターである。 Shoujiは、2つの重要なアイデアに基づいている。（1）最適なアライメント計算から異なるシーケンスを迅速に除外することによって、計算コストの高いバンド付き最適アライメントの必要性を著しく減らす新しいフィルタリングアルゴリズム。 （2）この新しいフィルタリング・アルゴリズムを大幅に高速化するための、最新のFPGAの並列処理に適したアーキテクチャーの賢明な使用。
ShoujiとMAGNETがGateKeeperとSHDと比較して、プリアライメントフィルタリングの精度をそれぞれ最大で2桁から4桁向上させることを実証した。 Shoujiを5つの最先端アライナと統合すると、シーケンスアライナの実行時間が最大18.8倍短縮されることを示した。
レポジトリより
Shoujiは、バンド配列アライメント計算のための高速かつ高精度なプリアライメントフィルタです。この名前は、日本の伝統的なドアにちなんで付けられたもので、スライドして開くように設計されています。
インストール
git clone https://github.com/CMU-SAFARI/Shouji.git
cd Shouji/CPU_Implementation/
make -j4
> ./main
missing argument..
./main [DebugMode] [GridSize] [ReadLength] [ReadFile] [# of reads]
テストラン
サイレントモード(0)で実行
./main 0 4 100 ../Datasets/ERR240727_1_E3_30million.txt 30000
レポジトリより
- Hardware_Acceleratorディレクトリには、FPGAボード上でShoujiを動かすために必要なデザインファイルとホストアプリケーションが入っている。また、デザインの合成方法とFPGAチップのプログラム方法についての詳細が記載されている。
引用
Shouji: A Fast and Efficient Pre-Alignment Filter for Sequence Alignment
Mohammed Alser, Hasan Hassan, Akash Kumar, Onur Mutlu, Can Alkan
Bioinformatics, Published: 28 March 2019
