概要

検索原理

BLASTによる検索法の概要を以下に示す。

1. 質問配列をk-mer(塩基配列の場合では11mer、タンパク配列の場合では3merが既定値)に分け、各k-merと配列類似度スコアがT以上で一致するk-merを求め、そのリストを作成する。 配列類似度スコアは各文字の類似度の和で計算されるが、塩基配列の場合では一致・不一致のスコア、タンパク配列の場合ではアミノ酸置換行列の値が一般に使用される。
2. データベース配列の中でリスト中のk-merとギャップを許容せずに並置されるものを有限オートマトン(Aho Corasickアルゴリズム)を用いて検出する。
3. データベース配列上で一定距離内にある並置されたk-merどうしを連結後、High Scoring Pair (HSP)と称する一定閾値以上のスコアを示す領域に対する統計的評価を行い、有意なHSPを含む配列をDBから抽出する。
4. 動的計画法を用いて、質問配列と抽出配列とのギャップを許容したアライメントを求める。

使用例

BLASTを利用するにはsbjの索引を作成する。

$ makeblastdb -in sbj.fa -dbtype nucl -hash_index -parse_seqids # 塩基配列の場合
$ makeblastdb -in sbj.fa -dbtype prot -hash_index -parse_seqids # アミノ酸配列の場合

qry及びsbjが塩基配列であるかアミノ酸配列であるかの相違により、使用するプログラムが異なる（下記参照）。 blastnプログラムでは塩基配列間の配列アライメントをするが、他のプログラムではアミノ酸配列に翻訳後に配列アライメントする。

$ command -query qry.fa -db sbj.fa

• -evalue 1e-10
• -num_threads 8
• -outfmt 7
• -out output
• -max_target_seqs 1

参考・関連情報

• BLAST論文
• 改良版BLAST論文
• Aho Corasickアルゴリズム
• FASTA