相同性検索FASTA

FASTA はホモロジー検索法の一つで、入力した配列(クエリー配列)と似ている配列(ターゲット配列)を検索する方法である。検索するデータベースが大きいため、マッチングによる検索は膨大な時間がかかる。そこで、FASTA は検索速度を上げるために、二段階検索を取り入れている。一段階目では、二つの配列のずれを粗スコア化してから、スコアの高いものをいくつか選ぶ。二段階目では、選ばれた配列に対して Needleman-Wunsch アルゴリズムを利用してギャップを考慮したスコアを計算して、検索結果を出力する。

  1. 二つの配列のズレをスコア化する(粗スコア)。
    1. 例えば、クエリー配列が「WWKRTSW」で、データベースにある配列のうちの一つを「CTWCRTSWA」とする、この配列に対して粗スコアを求める。
    2. 位置番号を記録する

      クエリー配列

      WKRTS
      1 , 2 , 73456

      対象配列

      CTWCRTSWA
      123456789
    3. 相対位置を計算する。例えば、対象配列の 1 文字目 C は、入力配列に存在しないので計算できない。次に、対象配列の 2 文字目 T の相対位置は、5 - 2 = 3 となります。対象配列の 3 文字目の W は三つの値が存在し、それぞれ 1 - 3 = -2、2 - 3 = -1、7 - 3 = 4 である。以降、順に求める。

      CTWCRTSWA
      123456789
      NA3-2, -1, 4NA-1-1-1-7, -6, 1NA
    4. 相対位置からスコアを計算する。上の表から、相対位置は -7 から 4 の間の値をとるから、この範囲にあるすべての相対位置のスコアを計算する。

  2. 粗スコアの高い部分配列を選ぶ。
  3. 選ばれた部分配列に対して、スコア行列を利用して再度スコアを計算し、スコアがもっとも大きいものを初期スコアとする。
  4. 初期スコアを利用して、部分配列をフィルタリングする。
  5. 残った配列に対して Needleman-Wunsch アルゴリズムを利用して、ギャップを考慮したスコアを計算する。
  6. スコア順にソートして結果を表示する。