|
|
|
|
|
ダイナミックプログラミング法による配列比較は、組合せをすべて勘定して厳密に探索問題を解くアルゴリズムである。一方、人間が目で配列比較を行うとするともっと直観的なやり方をする。例えば、まず両配列で共通に現れるパターンを探し、それを両側に延ばしてみるのではないだろうか。ＢＬＡＳＴアルゴリズムはこのようなヒューリスティックス（heuristics）、すなわち人間のもつ知識・知見をコンピュータのアルゴリズムに反映させた方法である。ただし、そこには次のような数学的基礎がある。 いま、２つのランダムな配列の間に存在するギャップのない最長の類似セグメントを MSP (Maximal-scoring Segment Pair) と呼ぶことにすると、スコア S をもつ MSP が長さ N と M の配列比較で得られる確率 p は
で与えられる。ここで、K は 0.1 程度の定数である。MSP が統計的に有意であると判定する p の値を例えば 0.05 とすると、この式でスコアの閾値が決まることになる。
ＢＬＡＳＴではまず問合せ配列に現れる長さ W の単語（文字列）、およびそれに類似な単語のリストを作成する。デフォルト値はアミノ酸で W = 3、ヌクレオチドで W = 11 になっている。類似語とはギャップのないペアワイズ比較でスコアが T 以上になる同じ長さの単語である。この際、自分自身との比較でスコアが T に達しない単語は除去する。この単語の一覧表をもとにデータベースを検索するのであるが、そこに有限オートマトン（finite automaton）が使われている。オートマトンは計算機の数学的なモデルとして古くから研究されている分野であるが、配列解析でも複数の文字列パターンが配列中に存在するかを高速に検索するのに有効である。図の簡単な例でこれを見てみよう。このオートマトンは３つの３文字（トリプレット）パターン ABA、BAA、BAB を探すためのもので、初期状態 Q0 から出発し配列を１文字ずつ読み込んでいくと、文字が何であったか（ここでは A、B、C の３種類の文字からなる配列を考えている）により状態遷移が起こり、とくに太線の矢印で示した状態遷移をした時にはパターンが見つかったことを示している。このように検索すべき複数の文字列パターンをオートマトンの形に表現しておくと、配列を一度読むだけですべてのパターンが存在するかを判定できるわけである。
さてＢＬＡＳＴアルゴリズムに戻ると、類似語が存在した場合これを出発点として問合せ配列とデータベース配列の局所アライメント（ギャップのない）を両側に延ばしていき、最長のセグメントとなった場合の類似度が閾値 S を越えたものを HSP (High-scoring Segment Pairs) として取り出す。上記の式により HSP の統計的有意性が評価できることに注意したい（ランダム配列において HSP の中で最もスコアが高いものが MSP である）。さらに、複数の HSP が存在する場合はそれを組み合わせた統計評価がなされる。以上の手続きに基づき、統計的に有意な局所アライメントがすべて出力される。ＢＬＡＳＴはＦＡＳＴＡよりも１０倍程度高速のアルゴリズムである。配列の類似性はしばしばギャップなしのコンセンサス配列あるいはモチーフを含んでおり、この知見に基づくＢＬＡＳＴアルゴリズムでホモロジー検索は充分な場合も多い。一方、ＦＡＳＴＡアルゴリズムではギャップを含んだ弱い類似性の検出、並列ダイナミックプログラミングではすべてのダイアゴナルを考慮した類似性の検出に有効であり、検索の速度と精度の必要性から選択して利用すべきであろう。