bioinfo pptx

バイオインフォマティクス

第

2

回

藤　博幸

バイオインフォマティクス

第

2回

藤　博幸

BIO

IT

アラインメントのアルゴリズムについて

- 動的計画法 (dynamic programing) -

動的計画法は組み合わせ最適化の一般的な手法であり、

配列アラインメントばかりでなくバイオインフォマティクスの様々

な分野で利用されている

二本の配列から可能なアラインメントの例�

ギャップ・ペナルティ�

�

　　

可能なアラインメントの中で一つを選択する

目的関数

を定め、それを最大化（最小化）するものを

求めるという形で選択

アミノ酸残基ペアに対するスコアとギャップペナルティ

を用いた

アラインメントスコア

(alignment score)

を

目的関数として、それを最大化するものを

最適アラインメント

(op5mal alignment)

として選択

A - T G G C T

A A G S - - W

物理化学的性質

の似ていないアミノ酸

-10

物理化学的性質の類似

するアミノ酸

＋５

一致するアミノ酸

+10

アミノ酸ペアに対するスコア

スコア・テーブル 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 1 1 2 T 0 1 1 3 P -1 1 1 0 6 L -4 -2 -3 -2 -3 6 I -3 -1 -1 0 -2 2 5 M -3 -1 -2 -1 -2 4 2 6 V -1 0 -1 0 -1 2 4 2 4 D 1 0 0 0 -1 -4 -2 -3 -2 4 N 0 0 1 0 -1 -3 -2 -2 -2 2 2 E 0 0 0 0 -1 -3 -2 -2 -2 3 1 4 Q -1 0 -1 -1 0 -2 -2 -1 -2 2 1 2 4 F -5 -4 -3 -3 -5 2 1 0 -1 -6 -4 -5 -5 9 Y -5 -3 -3 -3 -5 -1 -1 -2 -2 -4 -2 -4 -4 7 10 W -7 -6 -2 -5 -6 -2 -5 -4 -6 -7 -4 -7 -5 0 0 17 K -2 -1 0 0 -1 -3 -2 0 -2 0 1 0 1 -5 -4 -3 5 R -3 -2 0 -1 0 -3 -2 0 -2 -1 0 -1 1 -4 -4 2 3 6 H -2 -1 -1 -1 0 -2 -2 -2 -2 1 2 1 3 -2 0 -3 0 2 6 C -3 -2 0 -2 -3 -6 -2 -5 -2 -5 -4 -5 -5 -4 0 -8 -5 -4 -3 12

(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

大きな数字 　　置換しやすい 小さい数字 　　置換しにくい

アスパラギン酸 グルタミン酸 システイン チロシン リジン アルギニン ヒスチジン セリン スレオニン アスパラギン グルタミン グリシン アラニン バリン ロイシン イソロイシン メチオニン プロリン フェニルアラニン トリプトファン

アミノ酸は

”大文字”

で表記する

アミノ酸

C

H

H

N

H

R

O

H

O

C

側鎖

カルボキシル基 アミノ基

基本構造

主鎖

Arg (R) Glu (E) Asp (D) Thr (T) Cys (C) Ser (S) Lys (K) Met (M) His (H) Phe (F) Pro (P) Trp (W) Ala (A)

Gly (G) Val (V) Leu (L) Ile (I)

Tyr (Y) Gln (Q) Asn (N) 親水性 アミノ酸 解離性アミノ酸 疎水性アミノ酸

置換頻度に基づくスコアマトリクス上で

アミノ酸が物理化学的性質に対応するグループが

形成されること

進化の過程で、アミノ酸の置換の多くは物理化学的性質の

類似するものの間で生じやすい。

すなわち、アミノ酸置換は

保存的（中立的）

である。

LUSTAL format alignment by MAFFT L-INS-i (v7.130b) gi|443546|pdb|7 PQITLW---QRPLVTIRIGGQL---KEALLDTGADDTVLEEMNLPG HIV2 ---VTAYIEDQP---VEVLLDTGADDSIVAGIELGD simian ---SLW---NRPTTVVEIEGQK---VEALLDTGADDTVIKDLDLKG gi|4389337|pdb| LAMTMEHK---DRPLVRVILTNTGSHPVKQRSVYITALLDTGADDTVISEEDWPT gi|224443|prf|| ---TLDDQGGQGQEPPPEPRITLKVGGQP---VTFLVDTGAQHSVLTQNPGPL : . *:****:.::: gi|443546|pdb|7 KW---KPKMIGGIGGFIKVRQ---YDQIPVEIXGHKAIGTVL----VGPTPVNIIGR HIV2 NY---TPKIVGGIGGFINTKE---YKNVEIKVLNKRVRATIM----TGDTPINIFGR simian NW---KPQIIGGIGGSINVKQ---FFNCKVTIAGKTTHASVL----VGPTPVNIVGR gi|4389337|pdb| DWPVMEAANPQ-IHGIGGGIPVRKSRDMIELGVINRDGSLERPLLLFPLVAMTPVNILGR gi|224443|prf|| SD---KSAWVQGATGGKRYRW---TTDRKVHLATGKVTHSFLH---VPDCPYPLLGR . .. : * * : : : ..: . * :.** gi|443546|pdb|7 NLLTQIGXTLN---F HIV2 NILT---simian NVLKKLGCTLN---gi|4389337|pdb| DCLQGLGLRLT---NL gi|224443|prf|| DLLTKLKAQIHFEGSGAQVMGPMGQPLQVL : *

Clustal形式

のアラインメント

強く保存しているセグメント（モチーフ）が２ケ所見いだされる

Clustal形式アラインメント下段のシンボルの意味

“*”では，完全に保存


“:”では，強い物理化学的類似性のあるグループで保存 


“.”では，弱い類似性のあるグル―プで保存


強い弱いの基準は，

_{PAM250 行列において，アミノ酸間のスコアが0.5よ}

り大きいか，

_{0.5以下かで分けている}

PAM250行列については次回説明

アフィン・ ギャップ・ペナルティ

� �

g

(L)

=α＋β(

L

-1)��

�

L

はギャップの長さ �

・挿入・欠失（

inser5on/dele5on)は、ギャップとよばれる

空記号をいれて対応

・挿入・欠失は略して

INDEL

と呼ばれる

。

可能なアラインメントの数�

全てを数え上げ てスコア最大のものを見つける

ことは困難

���������� 動的計画法(dynamic programming)

が利用される。�

長さmとnの配列の可能なアラインメントの数をc(m, n)とする。 挿入/欠失を除くと並置される残基対が同じ組み合わせのアラインメント の数をg(m, n)とする。この時、 g(m, n)�< c(m, n)。 k個の残基がそれぞれ並置されているとすると、一方の配列からは mCk通りの対応させる残基を選べる。同様に他方の残基礎からも nCk通りの対応させる残基を選べる。よって ����� g(m, n) =

Σ

k=1to min{m,n} mCk nCk = m+n Cn m = nの場合を考えてみると、Stirlingの公式を用いて ����� g(n, n) = _2n C_n ~ 22n _{/ πn} n = 10　の場合、g(10,10) = 187079 n =100 の場合、g(100,100) = 9.066177 × 1058

動的計画法によるペアワイズアラインメントを

簡単な例で考えてみる。

○ スコアはDayhoff の　PAM250

○　g(L) = βL β = 8 とする

○　配列は

　

ANALYSIS　　　　８残基

ANYSIS　　　　　　6残基

の２本を考える。

配列

A

ANALYSIS　　　　８残基

配列

B

ANYSIS　　　　　　6残基

この時、

(8+1)×(6+1)のサイズの行列Dを考え

る。

一般には、アラインメントする配列の長さが

M残基と、L残基の時、(M+1) x (L+1)の行列

を考える。

配列

Aのアミノ酸を２行目以降に対応させ、

配列

Bのアミノ酸を２列目以降に対応させる。

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

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

A N A L Y S I S A N Y S I S アミノ酸_{i, jが} 並置される i j アミノ酸 _{i が} ギャップに対応 i - アミノ酸 _{j が} ギャップに対応 - j

行列上のパスが一つのアラインメントを表す

最もスコアの高くなるパスを

見つけてやると良い

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

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

A N A L Y S I S A N Y S I S スタート 自分がいるところ

スタートからこの点までの

最適経路が図のように

なっているということは

部分配列ANY と ANが

A N Y

A N -

とアラインされることを意味する

スコア= 2 + 2 – 8 = -4

A N A L Y S I S A N Y S I S スタート 今、ここに自分がいるとする。

スタートからこの点までの

最適経路が図のように

なっているということは

部分配列AN と ANが

A N

A N

とアラインされることを意味する

スコアは、2 + 2 = 4

A N A L Y S I S A N Y S I S スタート 今、ここに自分がいるとする。

スタートからこの点までの

最適経路が図のように

なっているということは

部分配列AN と ANAが

A N

-A N -A

とアラインされることを意味する

スコアは、2 + 2 – 8 = -4

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

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

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

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

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

A N A L Y S I S A N Y S I S スタート この処理を式で書くと

D(i, j) = max {

D(i-1,j) - β,　　　　　右上

D(i,j-1) - β,　　　　　左横

D(i-1,j-1)+s(i, j) 対角線

}

-4 4 -4 s(i, j)は、配列Aのi番目のアミノ酸と配列Bのj番目 のアミノ酸のPAM250行列の値

A N A L Y S I S A N Y S I S D(0,0) = 0 D(i, 0) = -(i ×　β) D(0, j) = -(j ×　β） とする。 ここでは β=8とする。 0 -8 -16 -24 -32 -40 -48 -8 -16 -24 -32 -40 -48 -56 -64 処理の意味 境界でのギャップの処理 赤線部分： 配列_{BのN末のANYを} ギャップと対応づけ、 配列Bの配列Aとのマッチング は４残基目以降でおこる ３残基のギャップなので 3×８=24のペナルティ を課している A N Y

-A N A L Y S I S A N Y S I S 0 　-8 -16 　-24 -32 -40 -48 -8 -16 -24 -32 -40 -48 -56 -64

この行列上で次の漸化式を

左上から順次といていく。

D(i, j) = max {

D(i-1,j) - β,

D(i,j-1) - β,

D(i-1,j-1)+s(i, j)

}

1 2 3 4 5 6 7 8

この順番で漸化式をといていけば、

○に到達した時には、

△の値は既に計算されていることがわかる。

A N A L Y S I S A N Y S I S 0 　-8 -16 -24　 -32 -40　 -48 -8 -16 -24 -32 -40 -48 -56 -64

この順番でも良い

1 2 3 4 5 6

A N A L Y S I S A N Y S I S 0 　-8 -16 -24 　-32 -40 　-48 -8 -16 -24 -32 -40 -48 -56 -64 1 2 3 4 5 6 7 8

漸化式を

N末側(左上）から

順次解いていくと、

順次部分配列のアラインメント

スコアが求められ、最終的に

D(8, 6)の要素が求まる。

動的計画法

_{(dynamic programing)とは、このように部分問題（この場合は、}

部分配列の最適並置）を順次解いていくことで、最終的には全問題について

最適な解を得るアルゴリズムである。

A N A L Y S I S A N Y S I S 0 　-8 -16 -24　 -32 -40 　-48 -8 -16 -24 -32 -40 -48 -56 -64 A N A L Y S I S A N Y S I S 0 -8 　 -16 -24　 -32 -40 -48 -8 -16 -24 -32 -40 -48 -56 -64 2 -6 -14 -22 -30 -38 -46 -54 -6 -14 -23 -33 -39 4 -4 -12 -20 -28 -8 1 -3 -11 -19 -16 -7 -2 -1 -9 -24 -6 -10 -3 -4 -29 -14 -4 -11 -1 -38 -22 -12 1 -7 -45 -30 -20 -7 3 経路行列 漸化式でスコアを計算すると同時に、３つの処理のどれが 選ばれたかを経路行列に記憶しておく。

A N A L Y S I S A N Y S I S 0 -8 -16 -24 -32 -40 -48 -8 -16 -24 -32 -40 -48 -56 -64 2 -6 -14 -22 -30 -38 -46 -54 -6 -14 -23 -33 -39 4 -4 -12 -20 -28 -8 1 -3 -11 -19 -16 -7 -2 -1 -9 -24 -6 -10 -3 -4 -29 -14 -4 -11 -1 -38 -22 -12 1 -7 -45 -30 -20 -7 3

バックトラック：

D(8,6)から経路行列を逆にたどりながら

　　　　　　　　　アラインメントを構築

(C末から構築）

A N A L Y S I S A N Y S I S 0 -8 -16 -24 -32 -40 -48 -8 -16 -24 -32 -40 -48 -56 -64 配列_{A ANALYSIS} 配列B _ANA--SIS

アフィン・ ギャップ・ペナルティ

� �

g

(L)

=α＋β(

L

-1)��

�

L

はギャップの長さ �

アフィンペナルティの場合、後藤のアルゴリズムで計算される。 後藤のアルゴリズムの必要性や説明は、この資料の後半に 参考としてつけておく

ここまでの説明、

２本の配列の全長での最適アラインメントをもとめる

ペアワイズ　グローバル　アラインメント

(pairwise global alignment)

データベース検索には、２本の配列を比較し

局所的な類似性を検出する

ペアワイズ　ローカル　アラインメント　が必要

(pairwise local alignment)

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

Global Alignment と Local Alignment の違い�

Smith-Waterman algorithm

Local Alignmentの� 漸化式の意味�

Local alignmentのアルゴリズムのスコアマトリクスへの要請

スコアマトリクスの要素

s(a, b)の中で少なくとも

一つは、負のスコアが含まれていなければならない

そうしないと、漸化式を解いた時の

Dは増加し続ける

全てが正の値をとるようなマトリクスを使用する時は

0に相当する値を設定して局所アラインメントを実行する

グローバル・アラインメント

��出力：アラインメントが一つ

ローカル・アラインメント

��出力：複数の局所的なアラインメント

��最初のアラインメントを構築した後で

��次にアラインメント・スコアの高い要素を

��見つけてアラインメントを構築すればよい

��しかし、その前に

��

サブオプティマル・アラインメント

を

��除去する必要がある。�

declump法によるsuboptimal alignment の除去��2

構造A 構造B 最大スコアのアラインメント ・パス� 2番目に大きな スコアのアライ ンメント・パス�

declump法によるsuboptimal alignment の除去��1

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

二本の配列についてのアラインメント

　　

Pairwise global alignment

　　

Pairwise local alignment

多数本の配列についてのアラインメント

mul5ple global alignment

マルチプル・アラインメント

���配列解析の第ニのステップ

(1)  多次元Needleman-Wunsch法

(2) プログレッシブ・アラインメント

�progressive alignment

ClustalW とtree-based alignment

(3) その他の方法

ペアワイズ・アラインメントの場合： ２次元配列Dの上で、漸化式を計算して アラインメントが得られた。 3本の配列のアラインメントの場合： もう一つ次元を増やして、3次元配列Dと それに対応する漸化式を計算すれば ３本の配列の最適アラインメントが得られる。 配列_A 配列_B 配列_C

N本の配列のアラインメントの場合：

N次元配列D上で漸化式を計算して最適マルチプル・

アラインメントを求める

・配列の本数が多くなると、

N次元配列Dのサイズ

　が大きくなり、莫大な記憶用量が必要となる。

・

Dの中で最適アラインメントパスを探索するのに

　莫大な計算時間を要する。

研究はなされているが、実用的観点からはまだ遠い

　　　　　　（探索空間の制限）

(2) プログレッシブ・アラインメント

ClustalW とtree-based alignment

ペアワイズ・アラインメントを繰り返す事で

マルチプル・アラインメントを構築

例：５本の配列のアラインメント

(1)  配列1と配列2をペアワイズ・

�アラインメント�

(2) 配列１、２のアラインメントを一本の配列のように

考え、配列３とペアワイズ・アラインメント

配列３ ２次元配列D i j k

_{漸化式中のスコアは例えば}

　S(i,j) + S(i,k)

(3) 配列1,2,3のアラインメントを１本の配列とみなし

　配列４とアラインメント

(4) 配列1,2,3,4のアラインメントを１本の配列とみなし

　配列５とアラインメント

プログレッシブ・アラインメントの問題点：

(1) 順番に依存してアラインメントの結果が異なって来る

(2) 各ペアワイズ・アラインメントのステップでは最適な

　並置が形成されているが、５本の配列全体の並置として

　最適である保証はない

Tree-based alignment

配列が４本（

A, B, C, D)の場合

(1)  全てのペアについてアラインメントを実施し、それに基づき

Guide Tree

を作成。�

C A D B

(2) 近縁なものから順番に

　ペアワイズ・アラインメント

　で重ねる。

　・まず、

(C, A)のアラインメント

　が作成される。

　・次に、

(C, A)のペアワイズ・

　アラインメントを一つの配列

　とみなし、

Dとのアラインメント

　を構築する

((C, A), D)。

　・最後に

((C, A), D)の３本のアライン

　メントと配列

Bを並置する。

※この方法では、アラインメントと配列、あるいは二つのマルチプル・ アライメントを、ペアワイズ・アラインメントの方法で順次重ねて いく。このアラインメントの方法は、_{clustalW ではプロファイル・} アラインメントと呼ばれている。

プログレッシブ・アラインメントの順序の問題

　　　

tree-based approachは良好な結果を与え

　　　直観的にも納得できる方法である。

しかし、配列全体としての最適並置になっている

保証がないという問題は解決されていない。

これは、プログレッシブ・アラインメントの

Once a gap, forever a gapという性質のためである。

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

(3) その他の方法

・simulated annealing

・genetic algorithm

・iterative improvement

・hidden Markov model

Itera4ve Improvement

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

マルチプルアラインメントのツールとしては、Clustal Wが多く使用されているが、 非常に大量の配列を精度よくアラインメントするのであれば、_{mah, MUSCLE,} T-Coffeeなどのツールを使用した方が良い。これらのツ―ルでは、高速、高精度 のアラインメントを実現するための様々な工夫（アルゴリズム）がなされている

pairwise

mul5ple

global local Dynamic Programing (Needleman-Wunsch) Dynamic Programing (Smith-Waterman) BLAST Dynamic Programing A* algorithm Simulated Annealing Gene5c Algorithm Itera5ve Improvement … EM algorithm Gibbs sampling

脳型プロスタグランジン

D

₂

合成酵素の機能予測

!

- Evolution of Prostaglandin D

₂

Synthase - !

Nagata, A., Suzuki, Y., Igarashi, M., Eguchi, N., Toh, H., Urade, Y.,Hayaishi, O.

Proc. Natl. Acad. Sci. USA 88, 4020-4024 (1991).

Igarashi, M., Nagata, A., Toh, H., Urade, Y., Hayaishi, O.

COOH OH O O COOH OH HO O PGH₂ PGD₂

PGD synthase

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

NCBIでキーワード検索し

アミノ酸配列を入手

まずブラウザを立ち上げ、

NCBI を検索

ここに

prostaglandin D synthase と入力して_{Searchをクリック}

Protein をクリック

Fileをチェック

まずブラウザを立ち上げ、

NCBI を検索

NCBIで検索して

検索結果画面から

protein blastを

クリック

Algorithm parameters

をクリック

Max target sequences

をデフォルト

(100)から

1000に変更

(出力される検出

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

　配列を

Windowに入力する

かわりに選択ボタンを使って、

入力ファイルを指定することも

検索が実行している間、タイムアウトすることを避けるために

Conserved Domain Databaseによる解析結果が出力され定期的

に更新される

E-value:やや正確さにかけるが、検出された配列と同じかそれ以上の類似度を示す

配列で同じ長さのものが、使用したデータベースで偶然見いだされる本数の期待値

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

ダウンロードの確認ウィンドウが出てくるので

OKをクリックして、

human neutrophil gelatinase-associated lipocalin�

m

ous

e

PG

D

s

ynt

ha

se

�

分泌蛋白質から構成されるグループで、疎水性の低分子に結合し、その輸送に携わっている。

Lipocalin Family!

secretor

y tissue!

targe

t cell!

Small hydrophobic !

molecules!

lipocalin!

Diverse family of secretory proteins involved !

PGD synthases　　　　

Lipocalins

!

enzyme!

!

!

vertebrates!

transporter!

= non-enzyme!

!

　　

from bacteria to eukaruyotes

!

Which sites

are involved in acquisition !

of the catalytic activity ? !

PGD

₂

合成酵素とリポカリンのアラインメントを作成

　　　　　　前回練習した

mahを使用

hpp://sci-tech.ksc.kwansei.ac.jp/~tohhiro/link.html

より

“lipocalin.txt” をダウンロードしてmahの入力とする

lipocalin.txtには、PGD合成酵素を含むリポカリン24配列が mul5-FASTA形式で含まれている(メモ帳などで確認すること）

Ma2を起動する

2. 検索ウィンドウにmahと入力

4. 入力ファイルを指定するために、mul5-fasta formatのファイルが置かれた Directoryを表示する。（ここからはWindows OS上での処理）

5. ドキュメントdirectoryが表示される。

Directoryからmahのウィンドウにファイルをドラッグすると、ファイル名が入力 される。ファイル名が入力されたら_{enterキーをおす。}

6. Outputすなわち、アラインメントを出力するファイル名を聞かれる、入力

ファイル名を参考にZドライブ上のファイル（新規でも既存の者でも良い）を指定し

Enterキーをおす。出力オプションを聞いてくるので2を指定する。

7. アラインメントのオプションを聞いてくる。1の—autoオプションを指定 してenter

autoオプション　小規模データ丁寧に、大規模データそれなりにアライン

t7

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

9. ウィンドウ中に、出力が表示

PGD synthase is inac5vated by treatment with

Cys residues may be involved in the cataly5c reac5on

of the enzyme.

SH X SH-Modifier�

.

C C C C C C C C C C C C C C C

Cys Cys S

Site-Directed Mutagenesis

Cys

Ala, Ser

Mutants lost the enzyme ac5vity.

Mutants showed the

ac5vity comparable to

that of the wild type

enzyme.

Cys S SH

BLASTの原理は次回

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

計算量について

計算に要するステップ数　＝　３_MN これを O(MN)と表す。 M=Nの時、N2 これは、_{Nが大きい場合、１回目の講義で説明した可能なアライ} ンメント全ての数え上げに比べきわめて小さい。

€

c(N,N) > g(N,N) ≈

2

2N

π

N

アフィン・ ギャップ・ペナルティ

� �

g

(L)

=α＋β(

L

-1)��

�

Lはギャップの長さ � ・挿入・欠失（_{inser5on/dele5on)は、ギャップとよばれる} 空記号をいれて対応 ・挿入・欠失は略して_INDELと呼ばれる。

　

α = opening penalty

β = extension penalty

通常は、 αはスコアマトリクスの最大値と同じ程度の値 βはαの1/10程度の値 に設定される。 gap length gap penalty 1 2 3 4 5 6 7 8 g(L) = βL g(L) = α + β(L - 1) α

動的計画法によるペアワイズアラインメントを

簡単な例で考えてみる。

○ スコアはDayhoff の　MDM78 ○　g(

L

) = α + β(L - 1) (α=8, β=1とする） ○　配列は 　_{ANALYSIS　　　　８残基} ANYSIS　　　　　　6残基 の２本を考える。

配列

A

ANALYSIS　　　　８残基

配列

B

ANYSIS　　　　　　6残基

この時、

(8+1)×(6+1)のサイズの行列Dを考える。

一般には、アラインメントする配列の長さが

M残基と、L残基の時、(M+1) x (L+1)の行列

を考える。

配列

Aのアミノ酸を２行目以降に対応させ、

配列

Bのアミノ酸を２列目以降に対応させる。

C言語の様式にならって、１行目と１列目の要素

を表す添字は０とする。プログラミング言語で

いうと行列ではなく配列である。

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

A N A L Y S I S A N Y S I S 0 -8 -9 -10 -11 -12 --13 -8 -9 -10 -11 -12 -13 -14 -15 この行列上で次の漸化式を 左上から順次といていく。 1 2 3 4 5 6 7 8 s(i, j)は、配列Aのi番目のアミノ酸と配列Bのj番目のアミノ酸 のスコアの値 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) } D(0, j) = g(j)と初期化 D(i, 0) = g(i)と初期化 D(0,0) = 0

A N A L Y S I S A N Y S I S 0 　-8 -9 　-10 -11 -12　 -13 -8 -9 -10 -11 -12 -13 -14 -15 この順番でも良い

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)

}

1 2 3 4 5 6

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

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

D(3, 4) D(2, 3) 配列Aの部分配列ANと配列Bの部分配列ANYの最適並置 に、配列_{Aの３番目のAと配列Bの4番目のSを対応させて} 接続 スコア = D(2,3) ＋　s(A, S)

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

したがって、全ての要素のスコアを求めるステップ数は

€

(i + j)

j=1 N

∑

i=1 M

∑

+ 1

= N

i

i=1 M

∑

+ M

j

j=1 N

∑

+ 1

=

NM(M + 1)

2

+

MN(N + 1)

2

+ 1

最も次数の高い項をとり、定数の和と定数倍を無視すると

€

O(NM

2

_{+ MN}

2

)

g(L) = βLの時の計算量は、

€

O(NM)

A N A L Y S I S A N Y S I S 0 　 -8 -9 　 -10 -11 -12 --13 -8 -9 -10 -11 -12 -13 -14 -15 この行列上で次の漸化式を 左上から順次といていく。 1 2 3 4 5 6 7 8 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(MN2_+NM2_{)の計算量が必要となる。}

A N A L Y S I S A N Y S I S 0 -8 -9 -10 -11 -12 --13 -8 -9 -10 -11 -12 -13 -14 -15 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) } バックトラックの効率化 漸化式を解く際に 同じサイズの行列を ２つ用意しておく

A N A L Y S I S A N Y S I S 0 -8 -9 -10 -11 -12 --13 -8 -9 -10 -11 -12 -13 -14 -15 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) (k,l) (i, j) (i, j) k l 行方向の 記憶用配列 縦方向の 記憶用配列 に入っている数字からバックトラック

時間計算量の削減　　　後藤のアルゴリズム

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) }

先の処理に同じ

後藤のアルゴリズムの漸化式が先の漸化式と等価で あることの直感的な証明　　　（１） 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) を代入してみれば良い

後藤のアルゴリズムの漸化式が先の漸化式と等価で あることの直感的な証明　　（２） 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) - β 　} 漸化式を再び代入

後藤のアルゴリズムの漸化式が先の漸化式と等価で あることの直感的な証明　　（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) - β} このように変形してから代入する

後藤のアルゴリズムの漸化式が先の漸化式と等価で あることの直感的な証明　　（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) - ２β} } = 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) - ２β }

後藤のアルゴリズムの漸化式が先の漸化式と等価で あることの直感的な証明　　（5） 同じ処理を繰り返すと、先の漸化式が得られる。 この時の計算量 E(i, j) = max {D(i, j -1) - α, E(i, j -1) - β}　　　---> 2MN F(i, j) = max {D(i -1, j) - α, F(i -1, j) - β} ---> 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の分だけ領域計算量は増加

計算量　（

complexity)

入力データ のサイズ(n)の関数として表現

　　

n

2

_{に比例する時は}

_O(n

2

_{)と書いてオーダーn}

2

_あるいは

　　

n

2

のオーダーと読む

　　実行時間が

f(n) のアルゴリズムを、O(f(n))(オーダー

　　

f(n))のアルゴリズムとよぶ

時間計算量 (5me complexity)

実行に要求される時間

領域計算量 (space complexity)

　　　　　実行に必要な領域の大きさ

　時間と空間のトレードオフ

後藤のアルゴリズムの時も

バックトラックのために２つの行列を準備

また、

E, Fに対応する行列をそれぞれ１つづつ準備

(EもFも動く方向は一方向のみなので、それぞれ１つで良い）

バックトラック用に、このような配列を準備することも

時間計算量と領域計算量のトレードオフの例

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) } アラインメントパス上でのみ以下の操作に変更� declump法によるsuboptimal alignment の除去 3

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