bioinfo pptx

Size: px

Start display at page:

Download "bioinfo pptx"

たつぞういそみ
5 years ago
Views:

1 IT BIO バイオインフォマティクス第 2 回藤博幸

2 アラインメントのアルゴリズムについて - 動的計画法 (dynamic programing) - 動的計画法は組み合わせ最適化の一般的な手法であり配列アラインメントばかりでなくバイオインフォマティクスの様々な分野で利用されている

3 二本の配列から可能なアラインメントの例ギャップペナルティ g(l)=α+β(l-1) :L はギャップの長さ

4 可能なアラインメントの中で一つを選択する目的関数を定めそれを最大化 ( 最小化 ) するものを求めるという形で選択アミノ酸残基ペアに対するスコアとギャップペナルティを用いたアラインメントスコア (alignment score) を目的関数としてそれを最大化するものを最適アラインメント (op5mal alignment) として選択

5 アミノ酸ペアに対するスコア A - T G G C T A A G S - - W 一致するアミノ酸 +10 物理化学的性質の似ていないアミノ酸 -10 物理化学的性質の類似するアミノ酸 +5

6 スコアテーブル PAM250 アミノ酸の置換頻度から構築 G A S T P L I M V D N E Q F Y W K R H C G 5 A 1 2 S T P L I M V D N E Q F Y W K R H C 大きな数字置換しやすい小さい数字置換しにくい (1) G,A,S, T, P: small hydrophilic residues (2) L, I, M, V: hydrophobic residues (3) D, N, E, Q: nagatively charged residues and the relatives (4) F, Y, W: aromatic residues (5) K, R, H: positively charged residues (6) C: Cys

7 アミノ酸側鎖 Asp (D) Glu (E) Cys (C) Tyr (Y) アスパラギン酸グルタミン酸システインチロシン Ser セリン (S) R 主鎖 H N H C H C O O H Lys (K) 解離性アミノ酸 Arg (R) His (H) リジンアルギニンヒスチジン Thr (T) スレオニンアミノ基アミノ酸は大文字で表記するカルボキシル基基本構造 Gly (G) グリシンアラニンバリンロイシンイソロイシン Met (M) Ala (A) Pro (P) Val (V) 疎水性アミノ酸 Phe (F) Leu (L) Ile (I) Trp (W) メチオニンプロリンフェニルアラニントリプトファン親水性アミノ酸 Asn (N) アスパラギン Gln グルタミン (Q)

8 置換頻度に基づくスコアマトリクス上でアミノ酸が物理化学的性質に対応するグループが形成されること進化の過程でアミノ酸の置換の多くは物理化学的性質の類似するものの間で生じやすいすなわちアミノ酸置換は保存的 ( 中立的 ) である

LUSTAL format alignment by MAFFT L-INS-i (v7.

---SLW----------NRPTTVVEIEGQK----------VEALLDTGADDTVIKDLDLKG gi 4389337 pdb LAMTMEHK--------DRPLVRVILTNTGSHPVKQRSVYITALLDTGADDTVISEEDWPT gi 224443 prf

::: gi 443546 pdb 7 KW------KPKMIGGIGGFIKVRQ---YDQIPVEIXGHKAIGTVL----VGPTPVNIIGR HIV2 NY------TPKIVGGIGGFINTKE---YKNVEIKVLNKRVRATIM----TGDTPINIFGR simian

9 LUSTAL format alignment by MAFFT L-INS-i (v7.130b) gi pdb 7 PQITLW QRPLVTIRIGGQL KEALLDTGADDTVLEEMNLPG HIV VTAYIEDQP VEVLLDTGADDSIVAGIELGD simian ---SLW NRPTTVVEIEGQK VEALLDTGADDTVIKDLDLKG gi pdb LAMTMEHK DRPLVRVILTNTGSHPVKQRSVYITALLDTGADDTVISEEDWPT gi prf ---TLDDQGGQGQEPPPEPRITLKVGGQP VTFLVDTGAQHSVLTQNPGPL :. *:****:.::: gi pdb 7 KW------KPKMIGGIGGFIKVRQ---YDQIPVEIXGHKAIGTVL----VGPTPVNIIGR HIV2 NY------TPKIVGGIGGFINTKE---YKNVEIKVLNKRVRATIM----TGDTPINIFGR simian NW------KPQIIGGIGGSINVKQ---FFNCKVTIAGKTTHASVL----VGPTPVNIVGR gi pdb DWPVMEAANPQ-IHGIGGGIPVRKSRDMIELGVINRDGSLERPLLLFPLVAMTPVNILGR gi prf SD------KSAWVQGATGGKRYRW---TTDRKVHLATGKVTHSFLH---VPDCPYPLLGR... : * * : : :..:. * :.** gi pdb 7 NLLTQIGXTLN F HIV2 NILT simian NVLKKLGCTLN gi pdb DCLQGLGLRLT NL gi prf DLLTKLKAQIHFEGSGAQVMGPMGQPLQVL : * Clustal 形式のアラインメント強く保存しているセグメント ( モチーフ ) が 2 ケ所見いだされる

10 Clustal 形式アラインメント下段のシンボルの意味 * では, 完全に保存 : では, 強い物理化学的類似性のあるグループで保存. では, 弱い類似性のあるグルプで保存強い弱いの基準は,PAM250 行列において, アミノ酸間のスコアが 0.5 より大きいか,0.5 以下かで分けている PAM250 行列については次回説明

11 アフィンギャップペナルティ g(l)=α+β(l-1) L はギャップの長さ挿入欠失 (inser5on/dele5on) はギャップとよばれる空記号をいれて対応挿入欠失は略して INDEL と呼ばれる

12 可能なアラインメントの数長さ m と n の配列の可能なアラインメントの数を c(m, n) とする挿入 / 欠失を除くと並置される残基対が同じ組み合わせのアラインメントの数を g(m, n) とするこの時 g(m, n) < c(m, n) k 個の残基がそれぞれ並置されているとすると一方の配列からは m C k 通りの対応させる残基を選べる同様に他方の残基礎からも n C k 通りの対応させる残基を選べるよって g(m, n) = Σ k=1to min{m,n} m C k n C k = m+n C n m = nの場合を考えてみると Stirlingの公式を用いて g(n, n) = 2n C n ~ 2 2n / πn n = 10 の場合 g(10,10) = n =100 の場合 g(100,100) = 全てを数え上げてスコア最大のものを見つけることは困難動的計画法 (dynamic programming) が利用される

13 動的計画法によるペアワイズアラインメントを簡単な例で考えてみるスコアは Dayhoff の PAM250 g(l) = βl β = 8 とする配列は ANALYSIS ANYSIS 8 残基 6 残基の 2 本を考える

14 配列 A ANALYSIS 8 残基配列 B ANYSIS 6 残基この時 (8+1) (6+1) のサイズの行列 D を考える一般にはアラインメントする配列の長さが M 残基と L 残基の時 (M+1) x (L+1) の行列を考える配列 A のアミノ酸を 2 行目以降に対応させ配列 B のアミノ酸を 2 列目以降に対応させる

15 D(0,0) A N Y S I S D(0,6) A N A L Y S こうしておくと要素 D(i, j) は配列 A の i 番目のアミノ酸と配列 B の j 番目に対応する S I D(8,6) D(8,0)

16 要素 D(i, j) を考える A N A L Y S I S A N Y S I S アミノ酸 i, j が並置されるアミノ酸 i がギャップに対応アミノ酸 j がギャップに対応この 3 つの動きのみ可能で後戻りはしないと考える i j i - - j

17 行列上のパスが一つのアラインメントを表す A N A L Y S I S A N Y S I S アミノ酸 i, j が並置されるアミノ酸 i がギャップに対応アミノ酸 j がギャップに対応最もスコアの高くなるパスを見つけてやると良い i j i - - j

18 スタート A N Y S I S A N A L Y 今ここに自分がいるとするスタートのポイントからここまでの最適な経路を見つけたいこの最適な経路は部分配列 ANY と ANA の最適アラインメントを意味する S S I

19 スタート A N Y S I S A N A L Y S I S 今ここに自分がいるとするスタートのポイントからここまでの最適な経路を見つけたいこの最適な経路は部分配列 ANY と ANA の最適アラインメントを意味する自分の周辺の 3 点に着目するそれぞれスタートからこの点までの最適経路とそのスコアがもとまっているとする

20 スタート A N A L Y S I S A N Y S I S スタートからこの点までの最適経路が図のようになっているということは部分配列 ANY と AN が A N Y A N - とアラインされることを意味するスコア = = -4 自分がいるところ

21 スタート A N A L Y S I S A N Y S I S スタートからこの点までの最適経路が図のようになっているということは部分配列 AN と AN が A N A N とアラインされることを意味するスコアは = 4 今ここに自分がいるとする

22 スタート A N A L Y S I S A N Y S I S スタートからこの点までの最適経路が図のようになっているということは部分配列 AN と ANA が A N - A N A とアラインされることを意味するスコアは = -4 今ここに自分がいるとする

23 スタート A N Y S I S 今ここに自分がいるとする A N A L スタートからまでの最適経路とスコアがもとまっているならこの 3 点に接続した経路を考えてその中でも最も点数の高いものを選択すれば良い Y S I S

24 スタート A N Y S I S 今ここに自分がいるとする A N A L Y S I 右上に接続する場合, 縦方向の移動は gap を意味し A とを対応させるので A N Y - A N A というアラインメントが形成されスコアは -4 8 = -12 S

25 スタート A N Y S I S 今ここに自分がいるとする A N 4-4 斜め上に接続する場合,Y と A を対応させることを意味し A L -4 A N Y A N A Y S I というアラインメントが形成され Y と A のスコアは -3 なのでアラインメントのスコアは 4 3 = 1 S

26 スタート A N Y S I S 今ここに自分がいるとする A N A L Y S I 左横に接続する場合, 横方向の移動は gap を意味し Y とを対応させるので A N - Y A N A - というアラインメントが形成されスコアは -4 8 = -12 S

27 スタート A N Y S I S A N A L Y S I S 今ここに自分がいるとする最もアラインメントのスコアが高かったのは Y と A を対応させる経路であったのでこの経路を選び部分配列 ANY と ANA の最適並置のアラインメントスコアは 1 となる

28 スタート A N Y S I S この処理を式で書くと A N A L D(i, j) = max { D(i-1,j) - β, 右上 D(i,j-1) - β, 左横 D(i-1,j-1)+s(i, j) 対角線 } Y S I s(i, j) は配列 A の i 番目のアミノ酸と配列 B の j 番目のアミノ酸の PAM250 行列の値 S

29 A N A A N Y S I S D(0,0) = 0 D(i, 0) = -(i β) D(0, j) = -(j β) とするここでは β=8 とする L Y S I S A N Y 処理の意味境界でのギャップの処理赤線部分 : 配列 B の N 末の ANY をギャップと対応づけ配列 B の配列 A とのマッチングは 4 残基目以降でおこる 3 残基のギャップなので 3 8=24 のペナルティを課している

30 A N Y S I S A N A L Y S I この行列上で次の漸化式を左上から順次といていく D(i, j) = max { D(i-1,j) - β, D(i,j-1) - β, D(i-1,j-1)+s(i, j) } S この順番で漸化式をといていけばに到達した時にはの値は既に計算されていることがわかる

31 A N A L Y S I S A N Y S I S この順番でも良い

32 A N Y S I S A N A L 漸化式を N 末側 ( 左上 ) から順次解いていくと順次部分配列のアラインメントスコアが求められ最終的に D(8, 6) の要素が求まる Y S I S 動的計画法 (dynamic programing) とはこのように部分問題 ( この場合は部分配列の最適並置 ) を順次解いていくことで最終的には全問題について最適な解を得るアルゴリズムである

33 経路行列 A N Y S I S A N Y S I S A A -8 N N -16 A A -24 L L -32 Y Y -40 S S -48 I I -56 S S -64 漸化式でスコアを計算すると同時に 3 つの処理のどれが選ばれたかを経路行列に記憶しておく

34 バックトラック :D(8,6) から経路行列を逆にたどりながらアラインメントを構築 (C 末から構築 ) A N Y S I S A N Y S I S A A -8 N N -16 A A -24 L L -32 Y Y -40 S S -48 I I -56 S S -64 配列 A ANALYSIS 配列 B ANA--SIS

35 アフィンギャップペナルティ g(l)=α+β(l-1) L はギャップの長さアフィンペナルティの場合後藤のアルゴリズムで計算される後藤のアルゴリズムの必要性や説明はこの資料の後半に参考としてつけておく

36 ここまでの説明 2 本の配列の全長での最適アラインメントをもとめるペアワイズグローバルアラインメント (pairwise global alignment) データベース検索には 2 本の配列を比較し局所的な類似性を検出するペアワイズローカルアラインメントが必要 (pairwise local alignment)

37 Global pairwise alignment から Local pairwise alignment への拡張何故ローカルアラインメントが必要なのか?

38 Global Alignment と Local Alignment の違い Smith-Waterman algorithm

39 Local Alignment の漸化式の意味

40 Local alignment のアルゴリズムのスコアマトリクスへの要請スコアマトリクスの要素 s(a, b) の中で少なくとも一つは負のスコアが含まれていなければならないそうしないと漸化式を解いた時の D は増加し続ける全てが正の値をとるようなマトリクスを使用する時は 0 に相当する値を設定して局所アラインメントを実行する

41 グローバルアラインメント出力 : アラインメントが一つローカルアラインメント出力 : 複数の局所的なアラインメント最初のアラインメントを構築した後で次にアラインメントスコアの高い要素を見つけてアラインメントを構築すればよいしかしその前にサブオプティマルアラインメントを除去する必要がある

42 declump 法による suboptimal alignment の除去 2 構造 A 構造 B 最大スコアのアラインメントパス 2 番目に大きなスコアのアラインメントパス

43 declump 法による suboptimal alignment の除去 1 構造 A Suboptimal region 構造 B 最大スコアのアラインメントパス 2 番目に大きなスコアのアラインメントパス declump 法については本資料の最後に参考として説明をつけてある

44 二本の配列についてのアラインメント Pairwise global alignment Pairwise local alignment 多数本の配列についてのアラインメント mul5ple global alignment

45 マルチプルアラインメント配列解析の第ニのステップ (1) 多次元 Needleman-Wunsch 法 (2) プログレッシブアラインメント progressive alignment ClustalW と tree-based alignment (3) その他の方法

46 (1) 多次元 Needleman-Wunsch 法

47 ペアワイズアラインメントの場合 : 2 次元配列 D の上で漸化式を計算してアラインメントが得られた 3 本の配列のアラインメントの場合 : もう一つ次元を増やして 3 次元配列 D とそれに対応する漸化式を計算すれば 3 本の配列の最適アラインメントが得られる配列 B 配列 A 配列 C

48 N 本の配列のアラインメントの場合 : N 次元配列 D 上で漸化式を計算して最適マルチプルアラインメントを求める配列の本数が多くなると N 次元配列 D のサイズが大きくなり莫大な記憶用量が必要となる D の中で最適アラインメントパスを探索するのに莫大な計算時間を要する研究はなされているが実用的観点からはまだ遠い ( 探索空間の制限 )

49 (2) プログレッシブアラインメント ClustalW と tree-based alignment

50 ペアワイズアラインメントを繰り返す事でマルチプルアラインメントを構築例 :5 本の配列のアラインメント (1) 配列 1 と配列 2 をペアワイズアラインメント (2) 配列 1 2 のアラインメントを一本の配列のように考え配列 3 とペアワイズアラインメント i 配列 3 j k 2 次元配列 D 漸化式中のスコアは例えば S(i,j) + S(i,k)

51 (3) 配列 1,2,3 のアラインメントを 1 本の配列とみなし配列 4 とアラインメント (4) 配列 1,2,3,4 のアラインメントを 1 本の配列とみなし配列 5 とアラインメントプログレッシブアラインメントの問題点 : (1) 順番に依存してアラインメントの結果が異なって来る Tree-based alignment (2) 各ペアワイズアラインメントのステップでは最適な並置が形成されているが 5 本の配列全体の並置として最適である保証はない

52 配列が 4 本 (A, B, C, D) の場合 (1) 全てのペアについてアラインメントを実施しそれに基づき Guide Treeを作成 (2) 近縁なものから順番にペアワイズアラインメントで重ねる C A D B まず (C, A) のアラインメントが作成される次に (C, A) のペアワイズアラインメントを一つの配列とみなし D とのアラインメントを構築する ((C, A), D) 最後に ((C, A), D) の 3 本のアラインメントと配列 B を並置するこの方法ではアラインメントと配列あるいは二つのマルチプルアライメントをペアワイズアラインメントの方法で順次重ねていくこのアラインメントの方法は clustalw ではプロファイルアラインメントと呼ばれている

53 プログレッシブアラインメントの順序の問題 tree-based approach は良好な結果を与え直観的にも納得できる方法であるしかし配列全体としての最適並置になっている保証がないという問題は解決されていないこれはプログレッシブアラインメントの Once a gap, forever a gap という性質のためである

54 配列が 6 本 (A, B, C, D, E, F) の場合で示したノードに対応するアラインメントに導入された gap の位置はそれ以降のアラインメントのステップで変更されない C A D B E F 一旦 gap が入ると配列全体としては間違った位置であっても修正されない

55 (3) その他の方法 simulated annealing genetic algorithm iterative improvement hidden Markov model 繰り返し計算が必要なものが多い

56 Itera4ve Improvement アラインメントを二分割ランダムあるいは系統樹の情報から二つのアラインメントをペアワイズにアラインする繰り返し

57 マルチプルアラインメントのツールとしては Clustal W が多く使用されているが非常に大量の配列を精度よくアラインメントするのであれば mah, MUSCLE, T-Coffee などのツールを使用した方が良いこれらのツルでは高速高精度のアラインメントを実現するための様々な工夫 ( アルゴリズム ) がなされている global pairwise Dynamic Programing (Needleman-Wunsch) mul5ple Dynamic Programing A* algorithm Simulated Annealing Gene5c Algorithm Itera5ve Improvement local Dynamic Programing (Smith-Waterman) BLAST EM algorithm Gibbs sampling

58 配列データベース検索による機能予測脳型プロスタグランジン D 2 合成酵素の機能予測

59 ! - Evolution of Prostaglandin D 2 Synthase -! Nagata, A., Suzuki, Y., Igarashi, M., Eguchi, N., Toh, H., Urade, Y.,Hayaishi, O. Proc. Natl. Acad. Sci. USA 88, (1991). Igarashi, M., Nagata, A., Toh, H., Urade, Y., Hayaishi, O. Proc. Natl. Acad. Sci. USA 89, (1992).

60 PGD synthase O COOH HO COOH O O OH OH PGH 2 PGD 2

61 PGD Synthase about 190 a.a. Amino Acid Sequence Database Database Searching Lipocalins

62 NCBI でキーワード検索しアミノ酸配列を入手

63 まずブラウザを立ち上げ NCBI を検索ここをクリック

64 ここに prostaglandin D synthase と入力して Search をクリック

65 Protein をクリック

66 190aa の酵素をクリック

69 FASTA をクリック

70 send to をクリック

71 File をチェック Create File をクリック

72 OK で download folder にテキスト形式でファイルがつくられる

73 NCBI BLAST での類似配列検索

74 まずブラウザを立ち上げ NCBI を検索 NCBI で検索して検索結果画面から Blast をクリック

75 protein blast をクリック

77 Algorithm parameters をクリック

78 Max target sequences をデフォルト (100) から 1000 に変更 ( 出力される検出配列の数 )

79 配列をウィンドウにペーストして BLAST をクリックし検索を実行

80 配列を Window に入力するかわりに選択ボタンを使って入力ファイルを指定することもできる

81 検索が実行している間タイムアウトすることを避けるために Conserved Domain Database による解析結果が出力され定期的に更新される

86 解析に利用する配列をチェックボックスにチェックを入れて選択する

87 E-value: やや正確さにかけるが検出された配列と同じかそれ以上の類似度を示す配列で同じ長さのものが使用したデータベースで偶然見いだされる本数の期待値小さいほど良い BLAST の有意性の指標使用するデータベースにより値が異なる

88 チェック後に download をクリックし出てくるメニューから FASTA (complete sequences) を選択

89 ダウンロードの確認ウィンドウが出てくるので OK をクリックしてダウンロードフォルダに配列を mul5-fasta 形式で保存

91 mouse PGD synthase human neutrophil gelatinase-associated lipocalin

92 Lipocalin Family! Diverse family of secretory proteins involved! 分泌蛋白質から構成されるグループで疎水性の低分子に結合しその輸送に携わっている in binding and transport of small hydrophobic molecules secretor y tissue! lipocalin! targe Small hydrophobic t cell!! molecules!

93 PGD synthases enzyme!!! vertebrates! Lipocalins! transporter! = non-enzyme!! from bacteria to eukaruyotes! Which sites are involved in acquisition! of the catalytic activity?!

94 PGD 2 合成酵素とリポカリンのアラインメントを作成前回練習した mah を使用 hpp://sci-tech.ksc.kwansei.ac.jp/~tohhiro/link.html より lipocalin.txt をダウンロードして mah の入力とする lipocalin.txt には PGD 合成酵素を含むリポカリン 24 配列が mul5-fasta 形式で含まれている ( メモ帳などで確認すること )

95 Ma2 を起動する 1 左下スタートをクリック

96 2. 検索ウィンドウに mah と入力上部に mah のインストール場所が表示されるこの mah のアイコンをクリック

97 3. mah の入力画面がたちあがる

98 4. 入力ファイルを指定するために mul5-fasta format のファイルが置かれた Directory を表示する ( ここからは Windows OS 上での処理 ) 左下のスタートをクリックし出て来たパネル左上のドキュメントを選択

99 5. ドキュメント directory が表示される Directory から mah のウィンドウにファイルをドラッグするとファイル名が入力されるファイル名が入力されたら enter キーをおす

100 6. Output すなわちアラインメントを出力するファイル名を聞かれる入力ファイル名を参考に Z ドライブ上のファイル ( 新規でも既存の者でも良い ) を指定し Enter キーをおす出力オプションを聞いてくるので 2 を指定する Clustal 形式 /Fasta 形式 Sorted Order/Input Order 説明はアラインメントを見ながら

101 7. アラインメントのオプションを聞いてくる 1 の auto オプションを指定して enter auto オプション小規模データ丁寧に大規模データそれなりにアライン

102 t7 8. 指定したファイルやオプションをコマンドライン形式で確認してくる問題なければ Y を入力して enter

103 9. ウィンドウ中に出力が表示 (END) が表示された時点で出力ファイルに書き込まれている

104 10. メモ帳によって Clustal 形式のアラインメントを確認

105 PGD synthase is inac5vated by treatment with. SH X SH-Modifier Cys residues may be involved in the cataly5c reac5on of the enzyme.

106 C C C C C C C C C C C C C C C

107 Site-Directed Mutagenesis Cys Ala, Ser Cys S S Cys Cys SH Mutants showed the ac5vity comparable to that of the wild type enzyme. Mutants lost the enzyme ac5vity.

108 点数 (4) (3) (2) (1) 達成目標 (3) に加え NCBI のサイトで BLAST によるデータベース検索を行うことができる (2) に加えグローバルマルチプルアラインメントのツリーベース法について説明できる (1) に加えペアワイズローカルアラインメントにどのように動的計画法を拡張するか説明できるペアワイズグローバルアラインメントの動的計画法の漸化式とその処理の意味を説明ですツリーベース法の問題とそれを克服する方法について説明できる BLAST の原理は次回

109 参考資料後藤のアルゴリズム

110 計算量について計算に要するステップ数 = 3MN これを O(MN) と表す M=N の時 N 2 これは N が大きい場合 1 回目の講義で説明した可能なアラインメント全ての数え上げに比べきわめて小さい c(n,n) > g(n,n) 22N πn

111 アフィンギャップペナルティ g(l)=α+β(l-1) L はギャップの長さ挿入欠失 (inser5on/dele5on) はギャップとよばれる空記号をいれて対応挿入欠失は略して INDEL と呼ばれる

112 α = opening penalty β = extension penalty 通常は α はスコアマトリクスの最大値と同じ程度の値 β は α の 1/10 程度の値に設定される g(l) = α + β(l - 1) gap penalty α g(l) = βl gap length

113 動的計画法によるペアワイズアラインメントを簡単な例で考えてみるスコアは Dayhoff の MDM78 g(l) = α + β(l - 1) (α=8, β=1 とする ) 配列は ANALYSIS ANYSIS 8 残基 6 残基の 2 本を考える

114 配列 A ANALYSIS 8 残基配列 B ANYSIS 6 残基この時 (8+1) (6+1) のサイズの行列 D を考える一般にはアラインメントする配列の長さが M 残基と L 残基の時 (M+1) x (L+1) の行列を考える配列 A のアミノ酸を 2 行目以降に対応させ配列 B のアミノ酸を 2 列目以降に対応させる C 言語の様式にならって 1 行目と 1 列目の要素を表す添字は 0 とするプログラミング言語でいうと行列ではなく配列である

115 D(0,0) A N Y S I S D(0,6) A N A L Y S こうしておくと要素 D(i, j) は配列 A の i 番目のアミノ酸と配列 B の j 番目に対応する S I D(8,6) D(8,0)

116 D(0,0) = 0 A N Y S I S D(0, j) = g(j) と初期化 A N この行列上で次の漸化式を左上から順次といていく A L Y S I D(i, j) = max { max(d(i - m, j) - g(m)), m=1, i max(d(i, j - n) - g(n)), } n=1, i D(i-1,j-1)+s(i, j) S D(i, 0) = g(i) と初期化 s(i, j) は配列 A の i 番目のアミノ酸と配列 B の j 番目のアミノ酸のスコアの値

117 A N A L Y S I S A N Y S I S この順番でも良い D(i, j) = max { max(d(i - m, j) - g(m)), m=1, i max(d(i, j - n) - g(n)), n=1, i D(i-1,j-1)+s(i, j) }

118 D(2, 3): A N 配列 A の部分配列 AN と配列 B の部分配列 ANY のスコア A N Y S I S D(3,4) をこれから求める要素には部分配列の最適並置のスコアが入っているものとする A L Y S I S D(2, 4): D(3,3): 配列 A の部分配列 AN と配列 B の部分配列 ANYS のスコア D(3,4) 配列 A の部分配列 ANA と配列 B の部分配列 ANY のスコア D(3,4) のスコアとは配列 A の部分配列 ANA と配列 B の部分配列 ANYS の最適並置のアラインメントスコアを意味する

119 配列 A の部分配列 ANA と配列 B の部分配列 ANYS の最適並置のアラインメントスコアはその上流の最適並置から構成 D(2, 4) D(3, 4) 配列 A の部分配列 AN と配列 B の部分配列 ANYS の最適並置に配列 A の 3 番目の A をギャップ (-) に対応させて接続スコア =max{d(2,4) - 8, D(1,4) - 9, D(0,4) - 10} D(3, 3) D(2, 3) D(3, 4) D(3, 4) 配列 A の部分配列 ANA と配列 B の部分配列 ANY の最適並置に配列 B の 4 番目の S をギャップ (-) に対応させて接続スコア =max{d(3,3) - 8, D(3,2) - 9, D(3,1)-10, D(3, 0) -11} 配列 A の部分配列 AN と配列 B の部分配列 ANY の最適並置に配列 A の 3 番目の A と配列 B の 4 番目の S を対応させて接続スコア = D(2,3) + s(a, S)

120 A N A L Y S I S A N Y S I S D(3,4) のスコアを求めるには =17 ステップ必要より一般には D(i,j) のスコアを求めるには (i + j + 1) ステップ必要

121 したがって全ての要素のスコアを求めるステップ数は M N j=1 (i + j) +1 i=1 M = N i + M j +1 = i=1 NM(M +1) 2 N j=1 + MN(N +1) 2 +1 最も次数の高い項をとり定数の和と定数倍を無視すると g(l) = βl の時の計算量は O(NM 2 + MN 2 ) O(NM)

122 A N Y S I S A N この行列上で次の漸化式を左上から順次といていく A L Y S I S D(i, j) = max { max(d(i - m, j) - g(m)), m=1, i max(d(i, j - n) - g(n)), } n=1, i D(i-1,j-1)+s(i, j) ここからバックトラック各ステップで最も高いスコア (gap penalty を考慮 ) を示す要素を選択する再び O(MN 2 +NM 2 ) の計算量が必要となる

123 バックトラックの効率化 A N Y S I S A N A L Y S I S D(i, j) = max { max(d(i - m, j) - g(m)), m=1, i max(d(i, j - n) - g(n)), } n=1, i D(i-1,j-1)+s(i, j) 漸化式を解く際に同じサイズの行列を 2 つ用意しておく

124 A N A L Y S I S バックトラックの効率化 A N Y S I S D(i, j) = max { max(d(i - m, j) - g(m)), m=1, i max(d(i, j - n) - g(n)), } n=1, i D(i-1,j-1)+s(i, j) (i, j) (i, j) k l (k,l) (i, j) 行方向の記憶用配列縦方向の記憶用配列に入っている数字からバックトラック

125 時間計算量の削減後藤のアルゴリズム D と同じサイズの行列 E と F を用意する E(0,0) = F(0,0) = D(0,0) = 0 E(i, 0) = F(i, 0) = D(i, 0) = g(i) E(0, j) = F(0, j) = D(0, j) = g(j) 先の処理に同じとし次の3つの漸化式をとく E(i, j) = max {D(i, j -1) - α, E(i, j -1) - β} F(i, j) = max {D(i -1, j) - α, F(i -1, j) - β} D(i, j) = max{d(i -1, j -1) + s(i, j), E(i, j), F(i, j) }

126 後藤のアルゴリズムの漸化式が先の漸化式と等価であることの直感的な証明 (1) E(i, j) = max {D(i, j -1) - α, E(i, j -1) - β} F(i, j) = max {D(i -1, j) - α, F(i -1, j) - β} D(i, j) = max{d(i -1, j -1) + s(i, j), E(i, j), F(i, j) } D(i, j) の式に E(i, j) F(i, j) を代入してみれば良い

127 後藤のアルゴリズムの漸化式が先の漸化式と等価であることの直感的な証明 (2) E(i, j) = max {D(i, j -1) - α, E(i, j -1) - β} F(i, j) = max {D(i -1, j) - α, F(i -1, j) - β} D(i, j) = max{d(i -1, j -1) + s(i, j), E(i, j), F(i, j) } D(i, j) = max{d(i -1, j -1) + s(i, j), max {D(i, j -1) - α, E(i, j -1) - β}, max {D(i -1, j) - α, F(i -1, j) - β} } = max{d(i -1, j -1) + s(i, j), D(i, j -1) - α, E(i, j -1) - β, D(i -1, j) - α, F(i -1, j) - β } 漸化式を再び代入

128 後藤のアルゴリズムの漸化式が先の漸化式と等価であることの直感的な証明 (3) E(i, j) = max {D(i, j -1) - α, E(i, j -1) - β} F(i, j) = max {D(i -1, j) - α, F(i -1, j) - β} D(i, j) = max{d(i -1, j -1) + s(i, j), E(i, j), F(i, j) } E(i, j -1) = max {D(i, j -2) - α, E(i, j -2) - β} F(i - 1, j) = max {D(i -2, j) - α, F(i -2, j) - β} このように変形してから代入する

129 後藤のアルゴリズムの漸化式が先の漸化式と等価であることの直感的な証明 (4) E(i, j -1) = max {D(i, j -2) - α, E(i, j -2) - β} F(i - 1, j) = max {D(i -2, j) - α, F(i -2, j) - β} D(i, j) = max{d(i -1, j -1) + s(i, j), D(i, j -1) - α, E(i, j -1) - β, D(i -1, j) - α, F(i -1, j) - β } = max{d(i -1, j -1) + s(i, j), D(i, j -1) - α, max {D(i, j -2) - α - β, E(i, j -2) - 2β}, D(i -1, j) - α, max {D(i -2, j) - α - β, F(i -2, j) - 2β} } = max{d(i -1, j -1) + s(i, j), D(i, j -1) - g(1), D(i, j -2) - g(2), E(i, j -2) - 2β, D(i -1, j) - g(1), D(i -2, j) - g(2), F(i -2, j) - 2β }

130 後藤のアルゴリズムの漸化式が先の漸化式と等価であることの直感的な証明 (5) 同じ処理を繰り返すと先の漸化式が得られるこの時の計算量 E(i, j) = max {D(i, j -1) - α, E(i, j -1) - β} F(i, j) = max {D(i -1, j) - α, F(i -1, j) - β} > 2MN > 2MN D(i, j) = max{d(i -1, j -1) + s(i, j), E(i, j), F(i, j) } > 3MN 行列 E, F を使用することで時間計算量を減少 2MN + 2MN + 3MN > O(MN) しかし行列 E, F の分だけ領域計算量は増加

131 計算量 (complexity) 入力データのサイズ (n) の関数として表現 n 2 に比例する時は O(n 2 ) と書いてオーダー n 2 あるいは n 2 のオーダーと読む実行時間が f(n) のアルゴリズムを O(f(n))( オーダー f(n)) のアルゴリズムとよぶ時間計算量 (5me complexity) 実行に要求される時間領域計算量 (space complexity) 実行に必要な領域の大きさ時間と空間のトレードオフ

132 後藤のアルゴリズムの時もバックトラックのために 2 つの行列を準備また E, F に対応する行列をそれぞれ 1 つづつ準備 (E も F も動く方向は一方向のみなのでそれぞれ 1 つで良い ) バックトラック用にこのような配列を準備することも時間計算量と領域計算量のトレードオフの例

133 参考資料ローカルアラインメントにおける declump 処理

134

135 declump 法による suboptimal alignment の除去 3 input: A, B, s(a, b) output: D(i, j), 0 < i < L, 0 < j < M D(i, 0) 0, E(i, 0) 0, F(i, 0) 0 for 1 < i < L D(0, j) 0, E(0, j) 0, F(0, j) 0 for 1< j < M for i = 1 to L for j = 1 to M E(i, j) max{ D(i, j-1) - α, E(i, j-1) - β} F(i, j) max { D(i-1, j) - α, F(i-1, j) - β} D(i, j) max{ 0, D(i-1, j-1) + s(ai, bj), E(i, j), F(i, j) アラインメントパス上でのみ以下の操作に変更 E*(i, j) max{ D*(i, j-1) - α, E*(i, j-1) - β} F*(i, j) max { D*(i-1, j) - α, F*(i-1, j) - β} D*(i, j) max{ 0, E*(i, j), F*(i, j) }

136 declump 処理の意味漸化式中 D* と D の違いは D(i-1, j-1) + s(ai, bj) が含まれているか否か漸化式中この処理の意味は ai, bj を並べることを意味するすなわち D* ではアラインメトパス中のアミノ酸残の対応付けを解消している

A Constructive Approach to Gene Expression Dynamics

A Constructive Approach to Gene Expression Dynamics 配列アラインメント (I): 大域アラインメント http://www.lab.tohou.ac.jp/sci/is/nacher/eaching/bioinformatics/ week.pdf 08/4/0 08/4/0 基本的な考え方バイオインフォマティクスにはさまざまなアルゴリズムがありますがその多くにおいて基本的な考え方は配列が類似していれば機能も類似しているというものである例えば