概要
FASTAは相同性検索に用いるプログラムである。
検索原理
FASTAはアライメント候補領域を制限後に動的計画法を適用する手法である。
FASTAによる検索法の概要を以下に示す。
- 質問配列に対し高い類似性を示す領域をデータベース配列から検出する。
- 質問配列をk-merに分ける。
- 質問配列とデータベース配列に対してハッシュ表を作成する。
- オフセット値を算出する。
- 検出領域を結合する。
- オフセット値をソートする。
- 同じオフセット値をもつ領域を連結する。
- 上位にランクされた配列と質問配列の最適アライメントを計算する。
- 置換スコア行列を用いて連結配列のアライメントスコアを算出し、高スコアのものを選択する。
- オフセット値が異なる領域でも近接しているものに対しては、ギャップペナルティを課してもスコアが高い場合は連結する。
- このように連結されたアライメント周りに適当な幅をとり、その幅内部で動的計画法を適用してアライメントを求める。
参考・関連情報