BLAST
この固定長データの長さを W(ワード)とする。例えば、W = 3 で、クエリシーケンス AGTTAC に対してデータベース中に ACTTAG というシーケンスが存在した場合、BLASTアルゴリズムは、TTA という部分データが両シーケンスで共有されていると認識する。W のサイズは、特に指定しない場合、ヌクレオチドでは11、アミノ酸では3である。
第2段階: BLASTアルゴリズムは、クエリシーケンスと、部分データを共有すると認識したデータベース中のシーケンス群に対して、ギャップを考慮しない単純なアライメントを行う。このギャップを考慮しないアライメントは、第1段階の W の長さの固定長での検索処理を、アライメントのスコアが高くなるように両方向に W(ワード)のサイズを拡張した処理である。この段階ではヌクレオチド(核酸塩基)やアミノ酸の挿入や欠損は考慮しない。先述の例では、AGTTAC と ACTTAG はそれぞれ TTA を共に含んでおり、ギャップを考慮しないアライメントは次のようになる。 ..AGTTAC.. | ||| ..ACTTAG..
第2段階で、ギャップを考慮せずに、スコアの高いアライメントが行えた場合、データベースのシーケンスデータは第3段階の処理対象となる。
第3段階: BLASTアルゴリズムは、Smith-Waterman アルゴリズムの変形版アルゴリズムで、クエリシーケンスとデータベースのシーケンスの間で、ギャップを考慮したアライメントを行う。アライメントを行った後、統計的に有意なアライメント群がユーザに示される。
BLASTから派生したアルゴリズムがいくつか考案されている。
BLAST を使うことで、例えば、ハツカネズミの未知の遺伝子を発見したときに、ヒトがそのシーケンスと類似した遺伝子をもつかどうかを調べることができる。 ハツカネズミの未知のシーケンスで BLAST を使って、ヒトゲノムのシーケンスデータベースに対して検索を行うと、BLAST は類似性の高いシーケンス群を見つけ出す。
また、BLAST は次のような問いを考えるときに使うことができる。
手元のタンパク質のアミノ酸配列は、どのバクテリアと系統的に関係があるか?
今シーケンシングして得られたDNAは、どの種に由来するか?
自分が決定した構造(もしくは構造モチーフ)をもつタンパク質を記録した、他の遺伝子はあるか?
BLASTアルゴリズムおよびそのアルゴリズムを実装したプログラムは、次の人々によって開発された。
Stephen Altschul(NCBI; 米国生物工学情報センター)
Warren Gish (NCBI)
David Lipman (NCBI)
Webb Miller(ペンシルベニア州立大学)
Gene Myers(アリゾナ大学)
BLASTアルゴリズムを実装したプログラムは複数存在する。 それぞれダウンロードして利用することができる。 オリジナルの実装は NCBI BLAST である。
BLAST (Basic Local Alignment Search Tool) は、バイオインフォマティクスでDNAの塩基配列あるいはタンパク質のアミノ酸配列のシーケンスアライメントを行うためのアルゴリズムをいい、またそのアルゴリズムを実装したプログラムをいう。 BLAST を使って、手元にあるシーケンスで、シーケンスデータベースもしくはライブラリに対して検索することにより、ある閾値以上のスコアで類似するシーケンス群を発見することができる。 BLAST は、バイオインフォマティクスで最も広く使われているプログラムの一つである。