高速なタンパク質配列相同性検索ツール「DIAMOND」

この記事は今年読んだ一番好きな論文 Advent Calendar 2015の17日の記事です。

今回紹介する論文はタンパク質用の配列相同性検索に関する以下の論文です。

Buchfink, B., Xie, C., & Huson, D. H. (2015). Fast and sensitive protein alignment using DIAMOND. Nature Methods, 12(1), 59–60. doi:10.1038/nmeth.3176

まったく同じ問題に大学時代から取り組んでいて、いろいろな意味で刺激を受けた論文で、良い機会なので紹介しようと思います。

配列相同性検索とは

配列相同性検索とは、DNAやタンパク質の配列をクエリとしてデータベース内の類似する配列を検索する解析です。この検索を行ううえで、クエリの配列とデータベース内の配列の類似度をどのように計算するか？が重要になります。理想的には、すべてのクエリとデータベース内の配列のペアに対して、Smith-Watermanアルゴリズム[1]を利用して類似度を計算し、クエリごとにスコアの高い順に類似するデータベースの配列名を出力することが望ましいです。しかし、この方法ではデータ量が多い場合、非常に多くの計算時間が必要となります。

このため、Seed-And-Extend strategyと呼ばれる近似手法が利用されます。この手法は以下の２つのステップで配列相同性検索を実行します。

クエリとデータベースの配列で短く、かつ、類似度が非常に高い領域（seed）を検索
Seedの周りのみSmith-Watermanベースのスコア計算を実行

ステップ１で、あらかじめ当たりをつけることで大部分のスコア計算を実行せずに済みます。これにより、Smith-Watermanアルゴリズムをそのまま使う場合よりも、大幅な高速化が可能となります。

このSeed-And-Extend　strategyを利用した有名なツールとしてBLAST[2]があります。タンパク質配列相同性検索の場合、BLASTではステップ１でクエリとデータベースの配列間で3文字の類似する部分文字列を2つ検索し、seedとしています。BLASTは現在でも多くの解析で用いられる一般的なツールであり、配列相同性検索を実行する場合、これが利用されます。

DIAMONDとは

近年、DNAシーケンサーの性能向上に伴う、解析データの大規模化に対応するために開発された、Seed-And-Extend strategyベースのタンパク質用の配列相同性検索ツールです。DIAMONDではBLASTとは違い、spaced seedとreduced alphabetを利用することで高い検索精度を維持しつつ、BLASTの2万倍の高速化を実現しています。

Spaced seed

高い検索精度が必要な場合、ある程度ミスマッチを許容したseedの検索が必要になってきます。しかし、ミスマッチを許容すると、途端に計算量が大きくなります。この問題を解決する方法の一つにspaced seedがあります。
Spaced seedは連続した文字列のマッチングではなく、飛ばし飛ばしの文字列の完全一致の検索を行います。以下にspaced seedを利用した文字列のマッチングの例を示します。

Spaced seedでは、1となっている部分のみ一致しているかどうか確認し、0のところは無視します。

詳細は省きますが、spaced seedによって連続した文字列の完全一致よりも精度の高い検索を行うことができます。この結果、seedの検索の際、連続した文字列検索の場合よりも長い文字列検索を用いても精度を維持できるようになります。1文字でも長い文字列の検索ができると、seedの検索で見つかるseedの数が平均 $1/|\Sigma|^2$ ( $\Sigma$ ：アルファベットの集合)となります。このため、その次のステップの計算時間が大幅に削減できます。

実際、DNA配列の場合は非常にうまくいくことが知られています。ただし、タンパク質配列の場合、これまでspaced seedを利用してもあまり精度が上がらないため、使われることはほとんどありませんでした。しかし、DIAMONDでは複数のspaced seedのパターンを利用するmultiple spaced seedと次に詳しく説明するreduced alphabetを組み合わせることで高い検索精度を維持しつつ、高速化を実現しています。

Reduced alphabet

タンパク質は一般的には20種類のアミノ酸で構成されています。配列相同性検索の場合、この20種類ごとに別々の文字を割り当てて、タンパク質を文字列で表現します。しかし、近い性質をもつアミノ酸がいくつかあります。このため、近い性質のアミノ酸は同じ文字で表現し、解析するということが近年良く行われます。DIAMONDにおいても、seedの検索の段階では、20種類のアミノ酸を11種類に減らした配列を変換し、変換後の配列でseedの検索を実行します。これにより、検索を行いやすい完全一致の文字列検索でも、ミスマッチを許した検索を実行した場合と同じように高い検索精度を保つことができます。

Seedの検索

DIAMONDのseedの検索では先ほど紹介した通り、multiple spaced seedとreduced alphabetを利用します。このうち、multiple spaced seedを利用する場合、以下の2つの問題点があります。

Spaced seedのパターン数分、検索回数が増加
Spaced seedのパターン数分、検索インデックスのメモリ量が増加

まず、DIAMONDでは検索回数の増加に対して、検索の際になるべくメモリのキャッシュヒット率を上げることで、seedの検索を高速化して、問題を解決しています。このキャッシュヒット率の向上に関係データベースなどで用いられるsort merge joinと同じような方法を利用します。具体的には以下のように行います。

spaced seedに基づいてデータベース内の配列の部分文字列を生成
できた部分文字列を辞書式順序に並び替え
上記と同様に複数のクエリ配列の部分文字列を生成し、並び替え
データベース配列とクエリ配列の部分文字列の配列を上から順にマッチング

大量なクエリを一度に処理する場合は、この方法により高速に複数の部分文字列の検索を行うことができます。

そして二つ目の問題点のメモリ量の増加に関してですが、これに対しては「メモリが足りなければデータベース、クエリを分割して処理する」だけです。DIAMONDの場合、データベースのサイズ×8バイト分のメモリがインデックスに必要になります。このため、なんらかの対処が必要になると思っていたのですが、DIAMONDでは分割するだけでインデックスなどはそのままメモリにのっけるという男らしい方法を取ります。
（このメモリを気にして、今までmultiple spaced seedを使わなかっただけに正直驚きました。）

実験結果

DIAMONDの評価ではBLASTと比較して評価 (Figure 1, Supplementary Table 1)を行っています。KEGGのデータベースとIlluminaのreadを利用した場合、DIAMOND-sensitive (16パターンのspaced seedを利用)の場合、BLASTと92％のアラインメントが一致し、2000倍の高速化を達成しています。また、DIAMOND-fast(4パターンのspaced seedを利用)の場合、BLASTと69％のアラインメントが一致し、約20,000倍の高速化を達成しています。

感想

正直、論文を読んだだけでは良くわからない部分が多々あります。また、DIAMONDのソースコードを読むと、論文にかかれてないフィルタがいくつか入っているため、本当にspaced seedでよくなっているのか若干疑わしいです。
また、精度に関しても、この評価でいいのか？と疑問もあります。（いろいろなクエリで試すとDIAMOND-sensitiveでも精度が非常に落ちる場合があります。）
ただ、タンパク質配列でまじめにspaced seedを使って精度と速度を出しているすごいツールなので、今後どう発展していくのか楽しみです。私のツール（GHOSTX, GHOSTZ）も負けないように改良を続けていこうと思います。

Reference

1. Smith, T. F., & Waterman, M. S. (1981). Identification of common molecular subsequences. Journal of Molecular Biology, 147(1), 195–197. doi:10.1016/0022-2836(81)90087-5
2. Altschul, S. (1997). Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Research, 25(17), 3389–3402. doi:10.1093/nar/25.17.3389