Presentation is loading. Please wait.

Presentation is loading. Please wait.

分子生物情報学 動的計画法に基づく配列比較法 (ペアワイズアライメント法)

Similar presentations


Presentation on theme: "分子生物情報学 動的計画法に基づく配列比較法 (ペアワイズアライメント法)"— Presentation transcript:

1 分子生物情報学 動的計画法に基づく配列比較法 (ペアワイズアライメント法)
阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター

2 配列アライメント バイオインフォマティクスの最重要技術の一つ 2個もしくは3個以上の配列の類似性の判定に利用
文字間の最適な対応関係を求める(最適化問題) 配列長を同じにするように、ギャップ記号(挿入、欠失に対応)を挿入

3 スコア行列(置換行列) 残基間(アミノ酸文字間)の類似性を表す行列 PAM250, BLOSUM45 など

4 スコア行列の導出 基本的には頻度の比の対数をスコアとする BLOSUM行列
既存のスコア行列を用いて多くの配列のアライメントを求め、ギャップ無しの領域(ブロック)を集める 残基がL%以上一致しているものを同一クラスタに集める 同じクラスタ内で残基aが残基bにアラインされる頻度Aabを計算 qa=∑b Aab / ∑cd Acd, pab=Aab / ∑cd Acd を求め、   s(a,b)=log(pab/qaqb) としたのち、スケーリングし近傍の整数値に丸める

5 ペアワイズ・アライメント 配列が2個の場合でも可能なアラインメントの個数は指数オーダー
しかし、スコア最大となるアライメント(最適アライメント)は動的計画法により、O(mn)時間で計算可能(m,n:入力配列の長さ)

6 ギャップペナルティ 線形コスト -gd g: ギャップ長 d: ギャップペナルティ この図の例では、コスト= -3d
アフィンギャップコスト –d – e(g-1) d: ギャップ開始ペナルティ e: ギャップ伸張ペナルティ この図の例では、コスト= -d - 2e よく利用されるペナルティ (d,e)=(12,2),(11,1)

7 動的計画法による大域アライメント(1) (Needleman-Wunschアルゴリズム)
入力文字列から格子状グラフを構成 アライメントと左上から右下へのパスが一対一対応 最長経路=最適アライメント

8 動的計画法による大域アライメント(2) DP (動的計画法)による 最長経路(スコア)の計算 ⇒ O(mn)時間 行列からの経路の復元は、
F(m,n)からmaxで=となっている F(i,j)を逆にたどることに行う (トレースバック)

9 動的計画法による大域アライメント(3)

10 局所アライメント(1) (Smith-Watermanアルゴリズム)
配列の一部のみ共通部分があることが多い   ⇒共通部分のみのアライメント x1x2 … xm, y1y2 … yn を入力とする時、スコアが最大となる部分列ペア xixi+1 … xk,  yjyj+1 … yh を計算 例えば、HEAWGEH と GAWED の場合、         A W G E         A W -E   というアライメントを計算 大域アライメントを繰り返すとO(m3n3)時間 ⇒Smith-WatermanアルゴリズムならO(mn)時間

11 局所アライメント(2) 動的計画法 の式 (最大のF(i,j)から トレースバック)

12 局所アライメント(3) 局所アライメントの正当性の証明(下図)
局所アライメントの定義:x1x2 … xm, y1y2 … yn を入力とする時、スコアが最大となる部分列ペア xixi+1 … xk, yjyj+1 … yh を計算

13 アフィンギャップコストによる アライメント
三種類の行列を用いる動的計画法によりO(mn)時間 Smith-Watermanアルゴリズムとの組み合わせが広く利用されている

14 任意ギャップコストによる アライメント 動的計画法(右式)により、O(n 3 )時間   (ただし、m=O(n)とする)

15 ギャップコストと計算時間の関係 ギャップコストが凸の時: O(n 2α(n))時間 ただし、α(n)は
  アッカーマン関数の逆関数(実用的には定数と同じ)

16 ペアワイズ・アライメントの計算量に 関するその他の結果
線形領域アライメント スコア計算だけなら簡単 トレースバックが難しい しかし、分割統治法によりO(n)領域が可能(右図) O(n2)時間の改善は可能か?   ⇒O(n2/logn)が可能 s(xi,yj)が疎(O(n)程度)な場合(Sparse DP) ⇒O(n logn)程度で可能

17 配列検索の実用プログラム(1) O(mn):mは数百だが、nは数GBにもなる ⇒実用的アルゴリズムの開発
 ⇒実用的アルゴリズムの開発 FASTA:短い配列(アミノ酸の場合、1,2文字、DNAの場合、4-6文字)の完全一致をもとに対角線を検索し、さらにそれを両側に伸長し、最後にDPを利用。 BLAST:固定長(アミノ酸では3, DNAでは11)の全ての類似単語のリストを生成し、ある閾値以上の単語ペアを探し、それをもとに両側に伸長させる。ギャップは入らない。伸長の際に統計的有意性を利用。

18 配列検索の実用プログラム(2)

19 配列検索の実用プログラム(3) SSEARCH: 局所アラインメント(Smith-Watermanアルゴリズム)をそのまま実行
PSI-BLAST: ギャップを扱えるように拡張したBLASTを繰り返し実行。「BLASTで見つかった配列からプロファイルを作り、それをもとに検索」という作業を繰り返す。

20 講義のまとめ(配列アライメントI) 動的計画法によるペアワイズアライメント 参考文献 大域アライメント
局所アライメント(Smith-Watermanアルゴリズム) アフィンギャップコストを用いたアライメント 線形領域アライメント 参考文献 阿久津、浅井、矢田訳:バイオインフォマティクス –確率モデルによる遺伝子配列解析、医学出版、2001


Download ppt "分子生物情報学 動的計画法に基づく配列比較法 (ペアワイズアライメント法)"

Similar presentations


Ads by Google