タンパク質データベースの検索は、バイオインフォマティクスなどのライフサイエンス分野で非常に重要な課題となっている。データベースサイズの指数関数的増加と共に分析される新しいデータの量がますます大きくなってきているため、既存のツールを使用したタンパク質類似性解析は、非常に遅く非効率的な作業になっている。タンパク質データベースの検索に最も広く使用されているソフトウェアは、BLAST(Altschul et al、1990)であり、NCBIサーバーで1日に何万もの検索が行われている(Discoveryのデータベース、ACM Queue 3巻、 2005年4月)。
要するに、BLASTはいわゆるシード・アンド・エクステンディング・アプローチを4つの段階で使用する。まず、BLASTはヒットを見つけようとする。ヒットは、クエリー配列と標的配列との間の短い正確なマッチ(通常はサイズ3)であり、使用されるスコアリングマトリックスに従っていくらかの小さな閾値を上回るスコアである。第2段階では、これらのヒットはungapped extensionを使用して拡張される。特定のカットオフ・スコアを上回っているすべてのextensionは、第3および第4段階に渡される。これらは、high-scoring segment pairs (HSPs)と呼ばれる。第3および第4段階では、クエリとターゲットとの間のアライメントがHSPをシードとして使い計算される。所定の閾値を上回るスコアを有する全てのアライメントが報告される。これらのアラインメントは、第2段階からのヒューリスティックな測定に基づいているため、必ずしも最適ではない。このプロセスは、サイズが約30 GBのNCBI-NRのような大規模データベースではかなり時間がかかる。そのため、DIAMOND(Buchfink et al、2014)、BLAT(Kent、2002)、Rapsearch2(Zhao et al。、2012)、PAUDA(Huson and Xie、2014)などの多くの新しいアプローチやツールが開発された。これらのアプローチの多くは、新しいコンピューティングアーキテクチャと並列コンピューティングアーキテクチャを活用して膨大な計算需要に対応し、完全に新しいアイデアや問題の視点を提示している。
それらの1つはDIAMONDである(紹介)。これは、論文によれば、非常に多数のショートリードをタンパク質データベースに合わせる必要があるハイスループットな設定ではBLASTよりも最大20,000倍高速である。このような環境でのBLASTXの代替とされている。 DIAMONDはそのアプローチにいくつかの斬新なアイデアを使用している。ダブルindexingは、より多くのキャッシュを意識してメモリ負荷を軽減するのに役立つ。これにより実行時間が大幅に改善されるが、感度を落とさずにシードを大幅に少なく処理する必要がある 。次いで、ヒットは、整列のために SIMD-accelerated banded Smith-Waterman algorithm に渡される。しかし、膨大な数のリードをタンパク質データベースに整列させる際に非常に高速になるように特別に設計されているため、通常の長いクエリデータセットではDIAMOND感度が多少低くなる。
BLAT、Rapsearch2、PAUDAなどの他のツールでは、BLASTやまったく正確なアルゴリズムに比べて時には非常に大きなスピードアップを伴い、アプリケーションに応じて良い結果を得ることができる別のアプローチを提案している。それにもかかわらず、効率的かつ敏感なタンパク質データベースの検索は、依然として解決すべき課題である。
この論文では、SWORD(Smith-Waterman on Reduced Database)を紹介する。このアプローチは、いくつかの有名なアイデアと、ハードウェアアーキテクチャによって開かれた新しい洞察と可能性を組み合わせた、この問題への斬新なアプローチある。同等の感度をクライアントに提供しながら、同じ設定でSWORDは従来のBLASTより最大16倍高速である。一方、高い得点アライメントだけが必要な場合、SWORDは最大68倍のスピードアップを提供する。探索空間を縮小するためのヒューリスティックな前処理フェーズと、それに続く第2の最適化フェーズを利用する。第2段階は、縮小された空間上で完全なSmith-Watermanアルゴリズム(Smith and Waterman、1981)を実行するSIMD(Single Instruction Multiple Data)命令によって高速化され、ユーザに最適なアラインメントを提供する。
インストール
mac os 10.13でテストした。
依存
- gcc 4.8+
本体 Github
git clone --recursive https://github.com/rvaser/sword.git sword
cd sword/
make
> ./sword -h
$ ./sword -h
usage: sword -i <query db file> -j <target db file> [arguments ...]
arguments:
-i, --query <file>
(required)
input fasta database query file
-j, --target <file>
(required)
input fasta database target file
-g, --gap-open <int>
default: 10
gap opening penalty, must be given as a positive integer
-e, --gap-extend <int>
default: 1
gap extension penalty, must be given as a positive integer and
must be less or equal to gap opening penalty
-m, --matrix <string>
default: BLOSUM_62
similarity matrix, can be one of the following:
BLOSUM_45
BLOSUM_50
BLOSUM_62
BLOSUM_80
BLOSUM_90
PAM_30
PAM_70
PAM_250
-o, --out <string>
default: stdout
output file for the alignment
-f, --outfmt <string>
default: bm9
out format for the output file, must be one of the following:
bm0 - blast m0 output format
bm8 - blast m8 tabular output format
bm9 - blast m9 commented tabular output format
-v, --evalue <float>
default: 10.0
evalue threshold, alignments with higher evalue are filtered,
must be given as a positive float
-a, --max-aligns <int>
default: 10
maximum number of alignments to be outputted
-A, --algorithm <string>
default: SW
algorithm used for alignment, must be one of the following:
SW - Smith-Waterman local alignment
NW - Needleman-Wunsch global alignment
HW - semiglobal alignment
OV - overlap alignment
-k, --kmer-length <int>
default: 3
length of kmers used for database search
possible values: 3, 4, 5
-c, --max-candidates <int>
default: 30000
number of target sequences (per query sequence) passed
to the alignment part
-T, --threshold <int>
default: 13
minimum score for two kmers to trigger a hit
if 0 given, only exact matching kmers are checked
-t, --threads <int>
default: hardware concurrency / 2
number of threads used in thread pool
-h, -help
prints out the help
ラン
indexの作成は必要ない。アミノ酸配列データベースを指定して検索を実行する。
./sword -i input.fa -j database.fa
引用
SWORD-a highly efficient protein database search.
Vaser R, Pavlović D, Šikić M
Bioinformatics. 2016 Sep 1;32(17):i680-i684.