BLAST
BLASTアルゴリズムを実行する際には、2つの情報が必要である。 クエリシーケンス(ターゲットシーケンスともいう)とシーケンスデータベースである。 BLASTアルゴリズムは、シーケンスデータベース中のシーケンス断片と類似するクエリシーケンス中のシーケンス断片を見つけ出す。 多くの場合、クエリシーケンスは、シーケンスデータベースと比べてデータ量が非常に小さい。 例えば、クエリシーケンスが千個程度のヌクレオチド(核酸塩基)であるのに対し、シーケンスデータベースは数億のヌクレオチドのデータをもっている場合がある。
BLASTアルゴリズムは、クエリシーケンスとシーケンスデータベースとの間で、高い閾値でシーケンスアライメントを行う。 その際には Smith-Waterman アルゴリズムに近似したヒューリスティクなアルゴリズムが使われる。 完全な Smith-Waterman アルゴリズムは、NCBI GenBank のような大規模なシーケンスデータベースに対して検索を行う場合には、処理速度が非常に遅いことが問題となる。 BLASTアルゴリズムは、Smith-Waterman アルゴリズムより少し正確さで劣るが、50倍以上の処理速度を実現する。 このようにBLASTアルゴリズムは、高速でありかつ比較的正確であるという特徴がある。 こうした特徴が、BLASTアルゴリズムの重要な技術的革新性であり、またおそらくバイオインフォマティクスにおいてBLASTプログラムが最もよく使われている理由となっている。
BLASTアルゴリズムの実行は、概念的には次に述べるように3段階に分かれている。
第1段階: クエリシーケンスを短い固定長データに分割した断片で、シーケンスデータベースを厳密に検索する。