FASTAとBLASTについて
FASTAとBLASTについて
NCBIでは、BLASTというFASTAのほぼ50倍速い、ホモロジー検索サービスが提供されます。これは、電子メールによるサーバーで、e-mailで検索配列を送るとe-mailで結果がもらえるというものです。また、これらのクローンサービスマシンが日本にも置かれるようです。
さて、BLASTは、Basic Local Alignment Search Toolの略で、NCBIにはBLASTのコーディングをしたWarren Gishがいます。以下のFASTAとBLASTの違いの話は彼に聞いた話です。
（註）現在、遺伝研（DDBJ）では、FASTA のサービスは Web、E-mail では提供しておりません（検索・解析サービスの一部終了のお知らせ）。FASTA をご利用の場合には、遺伝研スーパーコンピュータシステムをご利用ください。
遺伝研では現在FASTAというホモロジーサーチのプログラムが動いていますが、これとBLASTを比較ししたいと思います。
ホモロジーサーチは検索者が指定したDNAや蛋白の配列に近いものをデータベースの中から捜し出すという作業です。配列がぴったし一致するなら、UNIXのgrepや宮沢さんの作ったseqgrepなんかで検索できるのです（たとえば誰かが自分の研究中の配列と同じ配列をすでに決めているかどうかを調べたいときは、「ぴったし」で捜してもいいわけです）が、たいていの場合は、生物学的に近い配列を捜したいので、似たような配列を捜したいということになります。検索結果は似たものの順に出てきて欲しいですから、どのくらい似ているかのスコアを計算してその順にならべるわけです。実はこのスコアの計算方法がFASTAとBLASTでは違っているのです。
FASTAは２段階にわけてスコアの計算をします。配列の比較方法は、２つの列車がすれちがうときのように総当り方式でおこなわれます。すなわち、すべての列車の窓から、すれちがっている相手の列車のすべての窓が眺められるように、もれなく調べられます。
検索したい配列-----------とデータベースの中の１本の配列--------------
（=がすれちがっているところです。）
----------- --------------
----------=-------------
-------=====---------
----========------
-===========---
---===========
------========---
---------=====------
------------==---------
-------------- -----------
今、すれちがいの組み合わせのうち、上から第５番目の -===========— の =========== を調べているとします。まず左端の=から何個ずつかの単位で同じ配列が見つかると、そこに印が付けられあらかじめ決められたプラスの点数が付けられます(1)。これを便宜的に部分得点と(P)と呼びます。その次の単位も検索配列とデータベースの配列が同じならさらに点数がPに加算されます(2)。
逆に、違っていればギャップ(G)と呼ばれ(3)、ギャップが指定された程度の短かさであればギャップも含め一連の似た配列として認識されつづけられますが(3’)、ギャップが大きい場合は(4)、似た配列はここで終りとされます(4’)。
ギャップが含まれる部分ではギャップペナルティという値がPから減点されます。
1 -==+========--- 2 -==++=======---
3 -==++GG+====--- 3' -==+++++====---
4 -==++GGGG===--- 4' -==++=======---
部分得点Pは似た配列のかたまりごとに計算されます。このような計算を、すべてのすれちがいの組み合わせについて、似た配列の部分が現れるたびごとに、部分得点Pを計算していきます。そして、似た配列の部分++++をひとかたまりとして、その位置と得点Pを上位（たとえば）１０箇所分、記憶しておきます。ここまでが第１段階です。もし、検索配列が、データベースの中の完全な部分配列なら、以下のように、あるところで、ひとかたまりの+++++++++++が現れるはずです。その他の部分でも偶然+が現れるかもしれません。
----------- --------------
----------=-------------
-------=====---------
----=+======------
-===========---
---+++++++++++
------========---
---------=====------
------------+=---------
-------------- -----------
さて、似ているが、ぴったり同じでない場合は以下のようになります。後での説明用に左に番号をふっています。
1 ----------- --------------
2 ----------=-------------
3 -------=+=++---------
4 ----=====+==------
5 -+=====++===---
6 ---======+==++
7 ------====++==---
8 ---------+++==------
9 ------------+=---------
10 -------------- -----------
これらのなかで一番 +が多くなるように、指定された（通常２０本の）幅で範囲が選ばれスコアが計算されます。
今、仮に選択の幅を２本とし、上図の5を中心にして、3から7を選択すると、6を中心に4から8を選択するより、+や+++の数が多くなります。
3 -------=+=++---------
4 ----=====+==------
5 -+=====++===---
6 ---======+==++
7 ------====++==---
したがってこの場合は5が中心とされ、それぞれの3の+と++、4の+、5の+と++、などなどの部分得点Pが加算されます。この場合、8に+++があってそこの部分得点Pが非常に高くても、選択範囲外なのでスコアの計算からは、はずされます。このことが、後述のBLASTと違う点です。選択範囲内の部分得点Pの総和がこの検索配列の、このデータベース配列に対するスコアとされます。（このあと選択範囲内の似た配列の部分から、PAMマトリクスを使った類似度の計算をしてそれをスコアとするオプションもあるそうです。PAMマトリクスについてはBLASTのなかで説明します。）以上が第２段階です。後は、スコアの高い順に結果が並ぶということになります。以上がFASTAです。
BLASTでも、似た配列の部分の計算は列車の窓の総当り方式でおこなわれます。ただし、最初に似た配列の部分を検出するときに、FASTAは検索配列をそのまま使っていましたが、BLASTでは、あらかじめ検索配列のなかからNeighborhood Word Listという捜すべき単語を用意し、この単語がデータベース配列にあるかどうかを検出します。別の言葉でいえば、似た配列を捜すとき、FASTAはぴったし同じ配列が見つかるまで窓をずらし続けますが、BLASTは、少し違っている配列でもそれがListの中にあれば、見つかったとします。Neighborhood Word ListはPAMマトリクスと呼ばれる表から、計算によってもとめられます。RRRRに対していま、マトリクスの左上の４つをとってくると
A R
A 3 -3
R -3 6
になります。これらは検索前に平均的な配列（どこにでもある、ありふれた配列）と比較すると有意な差のある「似たもの配列」に置き換えられます。
以下はPam120です。
# This matrix was produced by "pam" Version 1.0.3 [6-Jan-92]
# PAM 120 substitution matrix, scale = ln(2)/2 = 0.346574
# Lowest score = -8, Highest score = 12
A R N D C Q E G H I L K M F P S T W Y V B Z X *
3 -3 -1 0 -3 -1 0 1 -3 -1 -3 -2 -2 -4 1 1 1 -7 -4 0 1 0 -1 -8
-3 6 -1 -3 -4 1 -3 -4 1 -2 -4 2 -1 -5 -1 -1 -2 1 -5 -3 -1 0 -2 -8
-1 -1 4 2 -5 0 1 0 2 -2 -4 1 -3 -4 -2 1 0 -4 -2 -3 4 1 -1 -8
0 -3 2 5 -7 1 3 0 0 -3 -5 -1 -4 -7 -3 0 -1 -8 -5 -3 5 3 -2 -8
-3 -4 -5 -7 9 -7 -7 -4 -4 -3 -7 -7 -6 -6 -4 0 -3 -8 -1 -3 -4 -6 -4 -8
-1 1 0 1 -7 6 2 -3 3 -3 -2 0 -1 -6 0 -2 -2 -6 -5 -3 1 5 -1 -8
0 -3 1 3 -7 2 5 -1 -1 -3 -4 -1 -3 -7 -2 -1 -2 -8 -5 -3 3 5 -1 -8
1 -4 0 0 -4 -3 -1 5 -4 -4 -5 -3 -4 -5 -2 1 -1 -8 -6 -2 1 -1 -2 -8
-3 1 2 0 -4 3 -1 -4 7 -4 -3 -2 -4 -3 -1 -2 -3 -3 -1 -3 2 2 -2 -8
-1 -2 -2 -3 -3 -3 -3 -4 -4 6 1 -3 1 0 -3 -2 0 -6 -2 3 -2 -2 -1 -8
-3 -4 -4 -5 -7 -2 -4 -5 -3 1 5 -4 3 0 -3 -4 -3 -3 -2 1 -3 -2 -2 -8
-2 2 1 -1 -7 0 -1 -3 -2 -3 -4 5 0 -7 -2 -1 -1 -5 -5 -4 1 0 -2 -8
-2 -1 -3 -4 -6 -1 -3 -4 -4 1 3 0 8 -1 -3 -2 -1 -6 -4 1 -3 -1 -2 -8
-4 -5 -4 -7 -6 -6 -7 -5 -3 0 0 -7 -1 8 -5 -3 -4 -1 4 -3 -4 -5 -3 -8
1 -1 -2 -3 -4 0 -2 -2 -1 -3 -3 -2 -3 -5 6 1 -1 -7 -6 -2 -1 0 -2 -8
1 -1 1 0 0 -2 -1 1 -2 -2 -4 -1 -2 -3 1 3 2 -2 -3 -2 1 0 -1 -8
1 -2 0 -1 -3 -2 -2 -1 -3 0 -3 -1 -1 -4 -1 2 4 -6 -3 0 1 -1 -1 -8
-7 1 -4 -8 -8 -6 -8 -8 -3 -6 -3 -5 -6 -1 -7 -2 -6 12 -2 -8 -5 -6 -5 -8
-4 -5 -2 -5 -1 -5 -5 -6 -1 -2 -2 -5 -4 4 -6 -3 -3 -2 8 -3 -2 -4 -3 -8
0 -3 -3 -3 -3 -3 -3 -2 -3 3 1 -4 1 -3 -2 -2 0 -8 -3 5 -2 -2 -1 -8
1 -1 4 5 -4 1 3 1 2 -2 -3 1 -3 -4 -1 1 1 -5 -2 -2 6 4 -1 -8
0 0 1 3 -6 5 5 -1 2 -2 -2 0 -1 -5 0 0 -1 -6 -4 -2 4 6 0 -8
-1 -2 -1 -2 -4 -1 -1 -2 -2 -1 -2 -2 -2 -3 -2 -1 -1 -5 -3 -1 -1 0 -2 -8
-8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 1
具体的に見てみましょう。
いま、検索配列をAAAABABCDDEEE…..とし、配列を見る窓を、４つごとに見ていく場合を考えます。
AAAABABCDDEEE.....
-------------
1 AAAA =AAAA,AAAB,AAAC,AAAD,,,
2 AAAB =AAAB,AAAA,AAAC,AAAD,,,
3 AABA =AABA,AAAA,AACA,AADA,,,
4 ABAB =ABAB
5 BABC =BABC,BABA
最初の窓に現れるのはAAAAです。次は2のAAAB、次は3のAABAとなります。1にもどって、このAAAAという並び方に、ランダムな配列と比べて一定以上近いものがNeighborhoodWordで=の右に書いてあります（例なのでほんとにこうなのかどうかはわかりません）。これらの値は今までにわかっている配列から統計的に計算されています。AAAAの場合はAAAA,AAAB,AAAC,AAAD,,,と多かったですが、たとえばABABではABABしかない場合もあります。この場合は、ABABはありふれた配列だよということです。したがって極端な場合、この４つの並びがランダムな配列と差がないとされた場合は、Listに残らず、検索対象にならない並びも出てくるということです。さて、Neighborhood Word Listは出来ました。
後は、Listにある配列を、FASTAと同じように列車の窓の総当り方式で捜します。FASTAと違うのは、ギャップを間に入れないでListとマッチする部分があるかどうかだけ捜します。
文学的な表現になりますが、FASTAは類似性を持つ部分が長く保たれている配列の順に、BLASTは部分的にではあるがそこに高い類似性を持つものの順に結果が並んでいると考えたらよさそうでした。
したがって検索結果は、与えた配列やそれぞれの細かなパラメータの設定方法により、かなり違いが出て来るようです。ただ、配列の類似性が高い場合には、どちらを使ってもほとんどもれなく、捜したい配列が出て来るので、後はユーザーの好みの問題ということになります。
ただ、問題は検索時間です。BLASTはFASTAの何十倍という早速さで検索が終ります。これにはいくつか秘密があって、まず似た単語がすでに決められており、検索が１段階で終ることがあるでしょう。そのほか、ファイルもバイト毎の圧縮がおこなわれているので、ハードディスクでなく、メモリー上に全てのデータがのっている状態で検索がおこなわれるので、高速です。具体的に、全データを圧縮すると現状で５０メガバイトになるそうです。