�

2016年度「バイオインフォマティクス」
講義予定表
1. 配列アライメント（五斗）
2. データベースサーチ（五斗）
3. 機能・構造予測（五斗）
4. 配列モチーフ・隠れマルコフモデル（五斗）
5. アセンブリとマッピング（Blanc-Mathieu）
6. 分子進化（緒方）7. 分子系統解析（緒方）8. 分子系統解析【演習】（Blanc-Mathieu）
9. 遺伝子予測（緒方）
10. 機能アノテーション・比較ゲノム（緒方）11. システムズバイオロジー（五斗）
12. メタゲノム解析（緒方）13. メタゲノム解析（緒方）http://goto.kuicr.kyoto-u.ac.jp/lecture/bioinfo.html

1

本日のトピック
マルチプルアライメントn

多数の配列を並べて同時に比較

配列モチーフ：パターン表現n

共通の機能を持つ遺伝子で保存されている領域

配列モチーフ：プロファイル表現2

マルチプルアライメント
マルチプルアライメントとは
n

多数の配列を並べて同時に比較

マルチプルアライメントが利用される局面
n

特定配列グループの機能的に重要な部位の同定
w ファミリー共通のモチーフ探索n

配列相互の進化的関連の解析
w 系統樹解析nその他
w RNAやタンパク質の高次構造予測w 相同遺伝子のフラグメントからPCRプライマーを設計

進化的な関係があることが予め分かっている
多数の配列間の関係を調べる方法�
3マルチプルアライメントの例
トリオースリン酸イソメラーゼ（TIM）の一部

E.coli	 	 	 	 	 	 	 	 	 	 	 	 	 EEVCARQIDAVLKT----------------QGAAAFEGAVIAYEPVWAIGTGKSATPAQA

H.influenzae	 	 	 	 	 	 	 EEVCARQIDAVINA----------------LGVEAFNGAVIAYEPIWAIGTGKSATPAQA

X.fastidiosa	 	 	 	 	 	 	 EAILRAQLEPVLSL----------------VGSAGFARAVVAYEPIWAIGTGRTATPDQA

Buchnera	 	 	 	 	 	 	 	 	 	 	 EQVIQRQLNLILKN----------------LGTSAFKNIIIAYEPIWAIGTGVSADPEHVS.aureus	 	 	 	 	 	 	 	 	 	 	 NDVVGEQVKKAVAG----------------LSEDQLKSVVIAYEPIWAIGTGKSSTSEDA

A.thaliana	 	 	 	 	 	 	 	 	 MDVVAAQTKAIADR----------------VTN--WSNVVIAYEPVWAIGTGKVASPAQA

H.pylori	 	 	 	 	 	 	 	 	 	 	 FKAVKEFLSEQLEN----------------IDLN-YPNLVVAYEPIWAIGTKKSASLEDI

T.whipplei	 	 	 	 	 	 	 	 	 LSRFRSVLSHLKAISDKKHSIGYALGSKTHFLDSDQLHMLVAYEPSSAINSGNCANSGDI	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 .	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 ::****	 	 **.:	 	 	 :	 	 	 .	 

E.coli	 	 	 	 	 	 	 	 	 	 	 	 	 QAVHKFIRDHIAKVDAN-IAEQVIIQYGGSVNASNAAELFAQPDIDGALVGGASLKADAF

H.influenzae	 	 	 	 	 	 	 QAVHAFIRGHIAAKSQA-VAEQVIIQYGGSVNDANAAELFTQPDIDGALVGGASLKAPAF

X.fastidiosa	 	 	 	 	 	 	 QAVHAFIRGEVAKADAR-IADSLPILYGGSVKPDNASELFSQPDVDGGLVGGASLVAEDF

Buchnera	 	 	 	 	 	 	 	 	 	 	 QLIHVFIKNYILKYSSI-NRNDIIIQYGGSINHTNVKKFIEQPDINGLLIGNSSLSAKEF

S.aureus	 	 	 	 	 	 	 	 	 	 	 NEMCAFVRQTIADLSSKEVSEATRIQYGGSVKPNNIKEYMAQTDIDGALVGGASLK---V

A.thaliana	 	 	 	 	 	 	 	 	 QEVHDELRKWLAKNVSADVAATTRIIYGGSVNGGNCKELGGQADVDGFLVGGASLKP-EF

H.pylori	 	 	 	 	 	 	 	 	 	 	 YLTHGFLKQILN--------QKTPLLYGGSVNTQNAKEILGIDSVDGLLIGSASWELENF

T.whipplei	 	 	 	 	 	 	 	 	 VRMAAAIKDIVN----------VRVLYGGGVNLFNASAVFNEDLLDGILVGRASLNASDF	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 ::	 	 :	 	 	 	 	 	 	 	 	 	 	 	 	 :	 ***.::	 	 *	 	 	 	 	 	 	 	 	 ::*	 *:*	 :*	 	 	 	 	 .

4FASTA のアライメントでは大腸菌(eco) と黄色ブドウ球菌 (sav) の TIM	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 10	 	 	 	 	 	 	 	 20	 	 	 	 	 	 	 	 	 	 	 	 	 30	 	 	 	 	 	 	 	 40	 	 	 	 	 	 	 	 50	 	 	 	 	 	 	 	 60	 	 	 	 	 eco:b3	 MRHPLVMGNWKLNGSRHMVHELVSNL-----RKELAGVAGCAVAIAPPEMYIDMAKREAEGSHIMLGAQN	 	 	 	 	 	 	 ::	 :..	 ::::.:	 .	 .	 ....:.	 :	 	 	 	 	 	 ::.	 .:	 	 ::	 ::	 	 	 	 .	 	 	 .	 .	 .:.:	 .:	 	 ::::sav:SA	 MRTPIIAGNWKMNKTVQEAKDFVNALPTLPDSKEVESVI-CAPAIQLDALTTAVKEGKAQGLEI--GAQN	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 10	 	 	 	 	 	 	 	 20	 	 	 	 	 	 	 	 30	 	 	 	 	 	 	 	 	 40	 	 	 	 	 	 	 	 50	 	 	 	 	 	 	 	 60	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 70	 	 	 	 	 	 	 	 80	 	 	 	 	 	 	 	 90	 	 	 	 	 	 	 100	 	 	 	 	 	 	 110	 	 	 	 	 	 	 120	 	 	 	 	 	 	 130	 	 	 	 	 eco:b3	 VDLNLSGAFTGETSAAMLKDIGAQYIIIGHSERRTYHKESDELIAKKFAVLKEQGLTPVLCIGETEAENE	 	 	 	 	 	 	 .	 ..	 .::::::::	 .	 :	 :.:..:..:::::::	 	 	 .:.::	 :	 ::	 	 ..	 ..:.::..:.:::.	 :	 :sav:SA	 TYFEDNGAFTGETSPVALADLGVKYVVIGHSERRELFHETDEEINKKAHAIFKHGMTPIICVGETDEERE	 	 	 	 	 	 	 	 70	 	 	 	 	 	 	 	 80	 	 	 	 	 	 	 	 90	 	 	 	 	 	 	 100	 	 	 	 	 	 	 110	 	 	 	 	 	 	 120	 	 	 	 	 	 	 130	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 140	 	 	 	 	 	 	 150	 	 	 	 	 	 	 160	 	 	 	 	 	 	 170	 	 	 	 	 	 	 180	 	 	 	 	 	 	 190	 	 	 	 	 	 	 200	 	 	 	 	 eco:b3	 AGKTEEVCARQIDAVLKTQGAAAFEGAVIAYEPVWAIGTGKSATPAQAQAVHKFIRDHIAKVDAN-IAEQ	 	 	 	 	 	 	 .::...:	 ..:.	 	 ..	 	 	 .	 	 	 ....::::::.::::::::.:	 	 .:.	 .	 	 :.:.	 ::	 ....	 ..:	 sav:SA	 SGKANDVVGEQVKKAVAGLSEDQLKSVVIAYEPIWAIGTGKSSTSEDANEMCAFVRQTIADLSSKEVSEA	 	 	 	 	 	 	 140	 	 	 	 	 	 	 150	 	 	 	 	 	 	 160	 	 	 	 	 	 	 170	 	 	 	 	 	 	 180	 	 	 	 	 	 	 190	 	 	 	 	 	 	 200	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 210	 	 	 	 	 	 	 220	 	 	 	 	 	 	 230	 	 	 	 	 	 	 240	 	 	 	 	 	 	 250	 	 	 	 	 eco:b3	 VIIQYGGSVNASNAAELFAQPDIDGALVGGASLKADAFAVIVKAAEAAKQA	 	 	 	 	 	 	 .	 :::::::.	 .:	 	 :	 .::	 :::::::::::::..	 :.	 ....:.	 	 	 	 	 sav:SA	 TRIQYGGSVKPNNIKEYMAQTDIDGALVGGASLKVEDFVQLLEGAK	 	 	 	 	 	 	 	 	 	 	 	 210	 	 	 	 	 	 	 220	 	 	 	 	 	 	 230	 	 	 	 	 	 	 240	 	 	 	 	 	 	 250	 5マルチプルアライメント法
ダイナミックプログラミングの多次元化
n

n本の配列であれば、n次元空間でDPをかけるw 時間的空間的制約が厳しい

累進法 (Progressive method)
逐次的にアライメントの数を増やすn 例：ClustalW
http://www.genome.jp/tools/clustalwn

反復改善法 (Iterative method)
２つのグループに分けてグループ間のアライメントn 乱数でグループ分けをし直してアライメントし、評価値を改善していくn 例：PRRN
http://www.genome.jp/tools/prrn/
n

6

累進法

すべての組み合わせのペアについて、ペアワイズアライメントで距離行列を作成する。
距離行列からガイドツリーを作成する。
n

配列の類似度をもとにクラスタ解析

ガイドツリーの枝の順番にアライメントを行う→ ツリーベース法ともいう。
n

近いものから順にペアワイズアライメントn

配列と配列，配列とグループ，グループとグループn評価関数はグループ間でのすべての配列ペアの類似度の総和

高速だが最初に発生したエラーは残ってしまう

7距離行列とクラスタ解析
階層型クラスタリングnn

近いものから順に組み合わせる方法。
近さの基準の例w 最短距離法：クラスタ間の距離に要素間の距離のうち最短のものを使う
w 最長距離法：クラスタ間の距離に要素間の距離のうち最長のものを使う
w UPGMA：クラスタ間の距離に要素間の距離の平均を使う
w 近隣結合法：全体の距離が最短になるような組み合わせを使う

距離行列の例：
A, B, C, D, E ５本のアミノ酸配列すべての組み合わせで配列の近さを計算（例えばスコアの逆数を使う）
8

最短距離法A B C D E
A
B 1
C 3 3
D 5 5 2

��A,B� C� D,E�

A,B�

��

��

��

C�

3�

��

��

D,E� 5�2�

��

E 6 7 5 1321
A

1BC

DE9

最長距離法A B C D E
A
B 1
C 3 3
D 5 5 2

��A,B� C� D,E�

A,B�

��

��

��

C�3�

��

��

D,E� 7�

5�

��

E 6 7 5 1731ガイドツリー
A1BCDE10ガイドツリーに基づいて段階的にアライメント

LWRDGRGALQLWRGGRGAAQ
DWR-GRTASG

LRR-ARTASA
L-RGARAAAELRRARTASALRGARAAAELWRDGRGALQLWRGGRGAAQLWRDGRGALQLWRGGRGAAQ

DWRGRTASG
11クラスタ間のアライメント
L W R D G R G A L Q
L W R G G R G A A Q
D W R - G R T A S G
L R R - A R T A S A
L - R G A R A A A E

スコア関数
クラスタ間のアミノ酸スコアの組み合わせ(Sum of Pairs)

4 * S(L,L) + 2 * S(L,D)

DP で計算する
ClustalWでは Sum ofPairs を重み付きで計算する

12アライメントスコア
全体のスコアは各列のスコアの和で計算する∑S(mi)
各列のスコア計算
SP (Sum of Pairs) スコア文字）

S(mi)=∑k＜l s(mik,mil)（mik = i列, k行目の最小エントロピースコア
S(mi) = -∑cia log pia���（cia= i 列における a の出現回数,�

pia = i 列における a の生起確率）
13

練習問題 4-1
クラスタ間のアライメント

Ala 1
Arg -5 7
Asn -5 -1 7
Asp -5 -2 2 8
Cys -5 -4 -2 -4 13
Gln -5 1 0 0 -3 7
BLOSUM50
Glu -5 0 0 2 -3 2 6
BLOck SUbstitution Matrices
Gly -5 -3 0 -1 -3 -2 -3 8
His -5 0 1 -1 -3 1 0 -2 10
Ile -5 -4 -3 -4 -2 -3 -4 -4 -4 5Leu -5 -3 -4 -4 -2 -2 -3 -4 -3 2 5
Lys -5 3 0 -1 -3 2 1 -2 0 -3 -3 6
Met -5 -2 -2 -4 -2 0 -2 -3 -1 2 3 -2 7
Phe -5 -3 -4 -5 -2 -4 -3 -4 -1 0 1 -4 0 8
Pro -5 -3 -2 -1 -4 -1 -1 -2 -2 -3 -4 -1 -3 -4 10
Ser -5 -1 1 0 -1 0 -1 0 -1 -3 -3 0 -2 -3 -1 5Thr -5 -1 0 -1 -1 -1 -1 -2 -2 -1 -1 -1 -1 -2 -1 2 5Trp -5 -3 -4 -5 -5 -1 -3 -3 -3 -3 -2 -3 -1 1 -4 -4 -3 15
Tyr -5 -1 -2 -3 -3 -1 -2 -3 2 -1 -1 -2 0 4 -3 -2 -2 2 8
Val -5 -3 -3 -4 -1 -3 -3 -4 -4 4 1 -3 1 -1 -3 -2 0 -3 -1 5
A R N D C Q E G H I L K M F P S T W Y V14反復改善法
複数配列をランダムに二つのグループに分け，グループ間のアライメントを行う
グループの再結合を行い，新たなランダム分割を行う
評価関数の値 (Weighted Sum of Pairs) が一定値に収束するまで繰り返す
PRRN では Doubly Nested Randamized
iterative method を用いる
DNR: 二重反復改善法n アライメント→系統樹→重みづけ→反復改善法n

多少時間はかかるが累進法よりも良い結果が得られることが多い
15

その他のマルチプルアライメントプログラム
MAFFTnフーリエ変換を用いて高速化。

n

累進法と反復改善法の両方に対応。

n

http://www.genome.jp/tools/maﬀt/T-COFFEE
n

累進法

n

http://tcoﬀee.vital-it.ch/cgi-bin/Tcoﬀee/tcoﬀee̲cgi/index.cgi

ProbCons
n

反復改善法

n

http://probcons.stanford.edu/

MUSCLEn

累進法＋反復改善法

16

本日のトピック
マルチプルアライメントn

多数の配列を並べて同時に比較

配列モチーフ：パターン表現n

共通の機能を持つ遺伝子で保存されている領域

配列モチーフ：プロファイル表現17配列モチーフ
機能ドメイン（機能部位）
機能的，構造的に重要な部位 は進化の過程で保存される傾向があるn 進化的に保存された ドメインn

配列モチーフ機能ドメイン中の特徴的な 保存配列パターンn マルチプルアライメント から抽出n

配列モチーフの表現方法
パターンn プロファイルn

18

機能ドメインの例
タンパク質
ペプチド鎖切断部位n リン酸や糖鎖などの修飾部位
n シグナル配列n DNA結合部位、リガンド結合部位nRNA
スプライス部位：GU/AGルールn 翻訳開始点n

DNAENCODE�

複製開始点
n プロモーターn

19

機能ドメインの例
亜鉛フィンガー DNA 結合部位
PROSITE パターンの例�
n C-x(2,4)-C-x(3)-[LIVMFYWC]-x(8)-H-x(3,5)-H.
n

http://www.genome.jp/dbget-bin/www̲bget?prosdoc:PDOC00028

20

ドメインからモチーフの抽出
マルチプルアライメント
Triose phosphate isomerase (TIM) の活性部位
E.coliH.influenzae
X.fastidiosa
Buchnera
S.aureus
A.thaliana
H.pyloriT.whipplei

EEVCARQIDAVLKT----------------QGAAAFEGAVIAYEPVWAIGTGKSATPAQAEEVCARQIDAVINA----------------LGVEAFNGAVIAYEPIWAIGTGKSATPAQAEAILRAQLEPVLSL----------------VGSAGFARAVVAYEPIWAIGTGRTATPDQA
EQVIQRQLNLILKN----------------LGTSAFKNIIIAYEPIWAIGTGVSADPEHVNDVVGEQVKKAVAG----------------LSEDQLKSVVIAYEPIWAIGTGKSSTSEDAMDVVAAQTKAIADR----------------VTN--WSNVVIAYEPVWAIGTGKVASPAQAFKAVKEFLSEQLEN----------------IDLN-YPNLVVAYEPIWAIGTKKSASLEDILSRFRSVLSHLKAISDKKHSIGYALGSKTHFLDSDQLHMLVAYEPSSAINSGNCANSGDI.
::**** **.::.

E.coliH.influenzae
X.fastidiosa
Buchnera
S.aureus
A.thaliana
H.pylori
T.whipplei

QAVHKFIRDHIAKVDAN-IAEQVIIQYGGSVNASNAAELFAQPDIDGALVGGASLKADAFQAVHAFIRGHIAAKSQA-VAEQVIIQYGGSVNDANAAELFTQPDIDGALVGGASLKAPAFQAVHAFIRGEVAKADAR-IADSLPILYGGSVKPDNASELFSQPDVDGGLVGGASLVAEDFQLIHVFIKNYILKYSSI-NRNDIIIQYGGSINHTNVKKFIEQPDINGLLIGNSSLSAKEFNEMCAFVRQTIADLSSKEVSEATRIQYGGSVKPNNIKEYMAQTDIDGALVGGASLK---VQEVHDELRKWLAKNVSADVAATTRIIYGGSVNGGNCKELGGQADVDGFLVGGASLKP-EFYLTHGFLKQILN--------QKTPLLYGGSVNTQNAKEILGIDSVDGLLIGSASWELENF
VRMAAAIKDIVN----------VRVLYGGGVNLFNASAVFNEDLLDGILVGRASLNASDF:: :: ***.:: *::* *:* :*.
[AVG]-[YLV]-E-P-[LIVMEPKST]-[WYEAS]-[SAL]-[IV]-[GN]-[TEKDVS]-[GKNAD]

A-Y-E-P-[IVS]-[WS]-A-I-[GN]-[TS]-[GK]�
配列パターン
データベースに登録されている配列パターンはhttp://www.genome.jp/dbget-bin/www̲bget?prosite:PS00171
�21

配列パターン
保存配列をアミノ酸のパターンとして表現n

正規表現による表現方法w 文字列の集合を一つの文字列で表現する方法n例w [AV]-Y-E-P-[LIVM]-W-[SA]-I-G-T-[GK]w C-x(2,4)-C-x(3)-[LIVMFYWC]-x(8)-H-x(3,5)-H

x: 任意のアミノ酸n x(2,4): 任意のアミノ酸が２〜４個続くn []: この中のアミノ酸のどれか
n {}: この中のアミノ酸以外のどれか
n

見た目に分かりやすいが、アミノ酸の出現頻度情報は失われてしまう
22

練習問題 4-2
マルチプルアライメントからのモチーフ（パターン）抽出23

PROSITE でのパターン表現
機能部位の説明n パターンn パターンを持つ配列のIDn 機能部位を持つ配列のIDn 短いパターンは偽陽性(Falsepositive) の問題があるn

POSITIVE: 機能部位に当該パターンを持つ配列の数
FALSE̲POS: 機能部位を持たないが、パターンを持つ配列の数
FALSE̲NEG: 機能部位を持つが、パターンを持たない配列の数�
24

PROSITE でのパターン表現

疑陽性が多いパターンは、SKIP-FLAG で区別できるようにしている25

本日のトピック
マルチプルアライメントn

多数の配列を並べて同時に比較

配列モチーフ：パターン表現n

共通の機能を持つ遺伝子で保存されている領域

配列モチーフ：プロファイル表現26

頻度情報の導入
Triose phosphate isomerase (TIM) の活性部位
E.coliH.influenzae
X.fastidiosa
Buchnera
S.aureus
A.thaliana
H.pylori
T.whipplei

EEVCARQIDAVLKT----------------QGAAAFEGAVIAYEPVWAIGTGKSATPAQAEEVCARQIDAVINA----------------LGVEAFNGAVIAYEPIWAIGTGKSATPAQAEAILRAQLEPVLSL----------------VGSAGFARAVVAYEPIWAIGTGRTATPDQAEQVIQRQLNLILKN----------------LGTSAFKNIIIAYEPIWAIGTGVSADPEHVNDVVGEQVKKAVAG----------------LSEDQLKSVVIAYEPIWAIGTGKSSTSEDAMDVVAAQTKAIADR----------------VTN--WSNVVIAYEPVWAIGTGKVASPAQAFKAVKEFLSEQLEN----------------IDLN-YPNLVVAYEPIWAIGTKKSASLEDILSRFRSVLSHLKAISDKKHSIGYALGSKTHFLDSDQLHMLVAYEPSSAINSGNCANSGDI.
::**** **.::.

E.coliH.influenzae
X.fastidiosa
Buchnera
S.aureus
A.thaliana
H.pylori
T.whipplei

QAVHKFIRDHIAKVDAN-IAEQVIIQYGGSVNASNAAELFAQPDIDGALVGGASLKADAFQAVHAFIRGHIAAKSQA-VAEQVIIQYGGSVNDANAAELFTQPDIDGALVGGASLKAPAFQAVHAFIRGEVAKADAR-IADSLPILYGGSVKPDNASELFSQPDVDGGLVGGASLVAEDFQLIHVFIKNYILKYSSI-NRNDIIIQYGGSINHTNVKKFIEQPDINGLLIGNSSLSAKEFNEMCAFVRQTIADLSSKEVSEATRIQYGGSVKPNNIKEYMAQTDIDGALVGGASLK---VQEVHDELRKWLAKNVSADVAATTRIIYGGSVNGGNCKELGGQADVDGFLVGGASLKP-EF
YLTHGFLKQILN--------QKTPLLYGGSVNTQNAKEILGIDSVDGLLIGSASWELENF
VRMAAAIKDIVN----------VRVLYGGGVNLFNASAVFNEDLLDGILVGRASLNASDF:: :: ***.:: *::* *:* :*.

A-Y-E-P-[IVS]-[WS]-A-I-[GN]-[TS]-[GK]�
V: 2/8
I: 5/8
S: 1/8+ pseudocount27配列プロファイル

マルチプルアライメントの各残基位置のアミノ酸出現頻度をカウント
Pseudocount などを導入して正規化
表現方法n

位置特異的スコアマトリックス（PSSM: Position
Speciﬁc Score Matrix または SSSM: Site
Speciﬁc Score Matrix）n

隠れマルコフモデル

n

ブロック
28

配列プロファイル：位置特異的スコアマトリックス
位置 i におけるアミノ酸 j の出現頻度
n(i,j) : 位置 i においてアミノ酸 j が出現した個数n N : アライメントに含まれる配列の本数n

位置 i におけるアミノ酸 j のスコアn

P(j) : アライメントを構築している配列全体またはデータベース全体から得られるアミノ酸組成29配列プロファイル：位置特異的スコアマトリックス
PROSITE ProﬁleSY�

位置１234：

SY: コンセンサス

M: マトリックス
30

配列プロファイル：隠れマルコフモデル
隠れマルコフモデル（HMM: Hidden Markov Model）
1次のマルコフモデル＋隠れ状態確率
プロファイルの長さを決めてモデル化
欠失状態

d1

d2

d3

d4

i0i1i2i3i4

挿入状態

m0m1m2m3m4m5

マッチ状態
31

配列プロファイル：隠れマルコフモデル
隠れマルコフモデル 有限オートマトン＋確率
・状態とその間をつなぐ遷移確率がある。
・状態から出力される記号は確率的に決まる。
出力記号集合Σ
状態集合 S={1,2,…,n}
遷移確率（状態 k → 状態 l ）ak,l
出力確率 ek(b)0.30.4
A: 0.2
B: 0.8

10.6

20.730.5

A: 0.1
B: 0.90.5
A: 0.9
B: 0.132

配列プロファイル：隠れマルコフモデル
隠れマルコフモデルのアルゴリズム
Viterbi アルゴリズム
出力記号列から状態列を推定
BABBABBが観測された時どの経路を通った可能性が一番高いか？
1312312BABBABB�
0.30.4
A: 0.2
B: 0.810.6

A: 0.1
B: 0.920.7
30.50.5
A: 0.9
B: 0.133

隠れマルコフモデルの Viterbi アルゴリズム

v(l,i) の定義：状態 l において、配列x1,x2,…xi が観測されている時の最大確率
今、BABBABB が観測されたとして、v(3,2) は状態3の時点で BA が観測されている最大確率1312312BABBABB�
0.30.4
A: 0.2
B: 0.810.6

A: 0.1
B: 0.9
20.7
3

0.5

0.5
A: 0.9
B: 0.134

隠れマルコフモデルの Viterbi アルゴリズム
v(l,i) を与える直前の状態を kmax、そこまでの確率を pmaxとすると、
v(l,i) = pmax akmax,l el(xi)各々の k に対して、ak,l は一定
k1el(xi)

k2ekmax(xi-1)
akmax,l�kmax
pmax = v(kmax,i-1)�
k4

lv(l,i)�

状態 l につながる直前の状態 k�
35隠れマルコフモデルの Viterbi アルゴリズム
v(l,i) を与える直前の状態を kmax、そこまでの確率を pmaxとすると、v(l,i) = pmax akmax,l el(xi)各々の k に対して、ak,l は一定$0 if i = 0 and l ≠ 0&v(l, i) = %1 if i = 0 and l = 0&e (x )max (v(k, i −1) × a )
' l i
kk,l
各状態 l と i 番目について、最大スコア v(l,i) と方角 ptr(l,i)
を記録しておく（ダイナミックプログラミング）。�
36

隠れマルコフモデルの Viterbi アルゴリズム

?

BABB�
A: 0.1
B: 0.901.0
A: 0.2
B: 0.8

0.3
0.4
10.6

20.7
30.50.5
A: 0.9
B: 0.137

Viterbi のテーブル v(l,i)
配列の i�番目0�
0

状態 l1�

2�

3�

4�

0.1728�

0.046656�

1�

1�

0.8�

2�

0.032�

0.1944�

0.062208�

3�

0.432�

0.0224�

0.013608�

Viterbi のテーブル ptr(l,i)
配列の i�番目
0�

1�

2�

3�

4�

3�

2�

0

状態 l

1�

0�

2�

1�

3�

1�

3�

1�

2�

2�
38

隠れマルコフモデルの Viterbi アルゴリズム
配列の i�番目
0�0

状態 l1�

2�

3�

4�

0.1728�

0.046656�

1�

1�

0.8�

2�

0.032�

0.1944�

0.062208�

3�

0.432�

0.0224�

0.013608�

1312

BABB�
A: 0.1
B: 0.901.0
A: 0.2
B: 0.8

0.3
0.4
10.6

20.7
30.50.5
A: 0.9
B: 0.139

練習問題 4-3
Viterbi アルゴリズムを用いた配列とHMMの適合評価

40配列プロファイル：隠れマルコフモデル
隠れマルコフモデルのアルゴリズム
Baum-Welch アルゴリズム
EM (Expectation-Maximization) アルゴリズム
出力記号列からパラメータを推定
学習
BABBABBBBAABBABBABBABBBBABAABB�

0.3
0.4
A: 0.2
B: 0.8

1

0.6

2
120.7
30.5
3

A: 0.1
B: 0.90.5
A: 0.9
B: 0.141

配列プロファイル：隠れマルコフモデル
プロファイル HMM
ファミリーごとにプロファイルの長さを決めてモデル化

欠失状態d1d2d3d4i0i1i2i3i4

挿入状態

m0m1m2m3m4m5マッチ状態
42

配列プロファイル：隠れマルコフモデル
隠れマルコフモデルによるプロファイル作成とモチーフ検索

EM
ファミリー１（マルチプルアライメント1）�

スコア1: 20.0

HMM１�
Viterbi
問い合わせ配列�EM
ファミリー２（マルチプルアライメント２）�

HMM2�

Viterbi
スコア2: 18.543

配列モチーフデータベース
配列モチーフの表現方法による分類n

配列パターンw PROSITE Patternn

配列プロファイル：位置特異的スコアマトリックスw PROSITE Proﬁle, NCBI-CDDn

配列プロファイル：隠れマルコフモデル
w PFAMn

その他
w BLOCKS, PRODOMn

統合w InterPro(, NCBI-CDD)
44

PFAM での配列プロファイル表現45

InterPro による配列モチーフデータベースの統合

46

InterPro による配列モチーフデータベースの統合47

ホモロジー検索とモチーフ検索質問配列

質問配列

ホモロジー
知識獲得
検索
配列データベース
モチーフ辞書

類似配列

モチー
フ検索

専門知識
生物学的意味解釈

専門知識
48

関連ウェブサイト
モチーフデータベースn

キーワード検索w http://www.genome.jp/dbget-bin/www̲bﬁnd?motifdicw http://www.ebi.ac.uk/interpro/n

塩基配列w 転写因子結合サイトなど：EPD, TransFac, JASPER

モチーフ検索n

http://www.genome.jp/tools/motif/w 質問配列が既知のモチーフを持つかw 質問モチーフを持つ配列を配列データベースから探すw マルチプルアライメントからプロファイルを作るn

PSI-BLAST: Position Speciﬁc Iterated BLASTw http://www.ncbi.nlm.nih.gov/BLAST/
49