BLAST

BLAST (Basic Local Alignment Search Tool) は、バイオインフォマティクスでDNAの塩基配列あるいはタンパク質のアミノ酸配列のシーケンスアライメントを行うためのアルゴリズムをいい、またそのアルゴリズムを実装したプログラムをいう。
BLAST を使って、手元にあるシーケンスで、シーケンスデータベースもしくはライブラリに対して検索することにより、ある閾値以上のスコアで類似するシーケンス群を発見することができる。
BLAST は、バイオインフォマティクスで最も広く使われているプログラムの一つである。
概要.
BLAST は、バイオインフォマティクスにおいて、DNAの塩基配列あるいはタンパク質のアミノ酸配列のシーケンスで、ペアワイズのシーケンスアライメントを行う。
BLAST は、主にシーケンスの局所的アライメント（ローカルアライメント）を行うために使われる。
BLAST と同様にペアワイズアライメントを行うためのプログラムとしては、他に FASTA などがある。
また、マルチプルアライメントを行うためのプログラムとしては、Clustal (ClustalW、ClustalX) などがある。
BLAST は、バイオインフォマティクスで最も広く使われているプログラムの一つである。
BLAST が広く使われている理由は、BLAST が処理速度を非常に重視していることにあるとみられる。
BLAST のアルゴリズムは正確さより速度を重視している。
BLAST におけるこの速度重視によって、今日では膨大なデータが蓄積されているゲノムのシーケンスデータベースに対して検索を行うような場合において、BLAST アルゴリズムを実用的なものとしている。
BLAST が開発された後、BLAST より速いアルゴリズムがいくつか開発されている。
BLAST は、大まかなシーケンスマッチングを必要とする他のアルゴリズムの一部としてもよく使われている。
BLAST を使うことで、例えば、ハツカネズミの未知の遺伝子を発見したときに、ヒトがそのシーケンスと類似した遺伝子をもつかどうかを調べることができる。
ハツカネズミの未知のシーケンスで BLAST を使って、ヒトゲノムのシーケンスデータベースに対して検索を行うと、BLAST は類似性の高いシーケンス群を見つけ出す。
また、BLAST は次のような問いを考えるときに使うことができる。
BLASTアルゴリズムおよびそのアルゴリズムを実装したプログラムは、次の人々によって開発された。
BLASTアルゴリズムを実装したプログラムは複数存在する。
それぞれダウンロードして利用することができる。
オリジナルの実装は NCBI BLAST である。
BLASTは NCBI (GenBank) やDDBJのウェブ上でも利用することができる。
BLASTのオリジナルの論文 "Altschul, SF, W Gish, W Miller, EW Myers, and DJ Lipman. Basic local alignment search tool. J Mol Biol 215(3):403-10, 1990." は、1990年代に非常に多くの論文で引用された。
BLASTアルゴリズム.
BLASTアルゴリズムを実行する際には、2つの情報が必要である。
クエリシーケンス（ターゲットシーケンスともいう）とシーケンスデータベースである。
BLASTアルゴリズムは、シーケンスデータベース中のシーケンス断片と類似するクエリシーケンス中のシーケンス断片を見つけ出す。
多くの場合、クエリシーケンスは、シーケンスデータベースと比べてデータ量が非常に小さい。
例えば、クエリシーケンスが千個程度のヌクレオチド（核酸塩基）であるのに対し、シーケンスデータベースは数億のヌクレオチドのデータをもっている場合がある。
BLASTアルゴリズムは、クエリシーケンスとシーケンスデータベースとの間で、高い閾値でシーケンスアライメントを行う。
その際には Smith-Waterman アルゴリズムに近似したヒューリスティクなアルゴリズムが使われる。
完全な Smith-Waterman アルゴリズムは、NCBI GenBank のような大規模なシーケンスデータベースに対して検索を行う場合には、処理速度が非常に遅いことが問題となる。
BLASTアルゴリズムは、Smith-Waterman アルゴリズムより少し正確さで劣るが、50倍以上の処理速度を実現する。
このようにBLASTアルゴリズムは、高速でありかつ比較的正確であるという特徴がある。
こうした特徴が、BLASTアルゴリズムの重要な技術的革新性であり、またおそらくバイオインフォマティクスにおいてBLASTプログラムが最もよく使われている理由となっている。
BLASTアルゴリズムの実行は、概念的には次に述べるように3段階に分かれている。
第2段階で、ギャップを考慮せずに、スコアの高いアライメントが行えた場合、データベースのシーケンスデータは第3段階の処理対象となる。
BLASTから派生したアルゴリズムがいくつか考案されている。
並列処理・分散処理への対応.
並列処理や分散処理の環境に対応したBLASTアルゴリズムがいくつか考案されている。
こうしたアルゴリズムは一般に Parallel BLAST と呼ばれることがある。
Parallel BLAST は、PthreadsやMPIのAPIを使って実装される。
多くのコンピュータプラットフォームに移植され、Linux、Windows、Solaris、AIXなどで利用可能である。
BLASTアルゴリズムを並列処理や分散処理に対応させる手法には次のようなものがある。
BLASTプログラム.
BLASTプログラムを利用するには、プログラムをダウンロードして blastall コマンドラインユーティリティとして実行する方法と、ウェブからアクセスする方法とがある。
NCBI (GenBank) やDDBJのウェブサイトでは、これらの機関が共同で構築している塩基配列（およびアミノ酸配列）の公共シーケンスデータベースに対して、ウェブブラウザでBLASTによる類似性検索を行うことができる。 
この公共シーケンスデータベースは定期的に更新され、新たに配列決定が行われた生物のシーケンスのほとんどは、このデータベースに登録される。
BLASTには実際には複数のプログラムが含まれている。
blastall 実行ファイルには、blastp、blastn、blastx、tblastn、tblastx のプログラムが含まれている。
blastall をコマンドライン環境で実行する際は、-p オプションで実行するプログラムを指定する（例: blastall -p blastn）。
BLASTプログラムを実行する際、クエリシーケンスはFASTAフォーマットでプログラムに渡す。
次にBLASTに含まれているプログラムのうち主なものを示す。