ゲノム統合データベースからの知識発見

数理科学特別講義
バイオインフォマティクスにおける
確率モデル
阿久津達也
京都大学化学研究所
バイオインフォマティクスセンター
講義内容 I （基礎編）
①
②
③
④
⑤
分子生物学の基本事項
バイオインフォマティクスに必要な確
率統計の基礎
配列アラインメントとスコア関数
隠れマルコフモデル
EMアルゴリズム
講義内容 II（応用編）
①
②
③
④
⑤
確率文脈自由文法とRNA二次構造予測
進化系統樹構成法
タンパク質立体構造予測
遺伝子ネットワーク推定
実習
実習内容
①
②
③
④
配列検索プログラム
マルチプルアラインメント
PSI-BLASTによる検索
立体構造予測
ゲノム研究と情報科学

ゲノム解析計画の急速な進展




情報解析の必要性



既に数十種の微生物の全塩基配列が決定
線虫（１０００細胞）、しょうじょうばえも決定
ヒトも概要配列が公開済み
DNA配列⇔プログラムのオブジェクトコード
意味の解析が必要
DNA配列：A,C,G,Tの４文字からなる文字列

様々な情報技術が利用可能
遺伝子と蛋白質

遺伝情報の流れ


遺伝子


DNA配列中で直接的に
機能する部分
エキソン
転写制御領域
（プロモーターなど）

スプライシング
mRNA
GGU

アミノ酸（２０種類）の鎖
GCA
翻訳
GGU → Gly
GCA → Ala
染色体全体（半数体）
遺伝情報の総体
タンパク質
エキソン
転写・
ゲノム


DNA⇒RNA⇒タンパク
エキソン
タンパク質
DNA
DNAとアミノ酸
DNAはA,C,G,Tの４文
字の並び

DNAは二重ラセン構
造⇒相補鎖

塩基：DNA１文字、
残基：アミノ酸１文字

DNA３文字がアミノ酸
１文字に対応
（アミノ酸は２０種類）

コード表
2文字目
T
TTT
TTC
T
１
文
字
目
C
A
TTA
TTG
CTT
CTC
CTA
CTG
ATT
ATC
ATA
ATG
相補鎖
G
A C G T C G T C
T G C A G C A G
GTT
GTC
GTA
GTG
C
F
L
L
I
M
V
TCT
TCC
TCA
TCG
CCT
CCC
CCA
CCG
ACT
ACC
ACA
ACG
GCT
GCC
GCA
GCG
A
S
P
T
A
TAT
TAC
TAA
TAG
G
Y
stop
CAT
CAC
H
CAA
CAG
TGT
TGC
TGA
TGG
C
stop
W
Q
CGT
CGC
CGA
CGG
R
AAT
AAC
N
AGT
AGC
S
AAA
AAG
K
AGA
AGG
R
GAT
GAC
D
GAA
GAG
E
GGT
GGC
GGA
GGG
G
アミノ酸と蛋白質


アミノ酸：２０種
類
蛋白質：アミノ酸
の鎖（短いもの
はペプチドと呼
ばれる）
アミノ酸
R
H
側鎖
OH
C
N
アミノ基
C
カルボシキル基
H
H
O
蛋白質
R
N
H
C
H
H
C
O
N
H
C
R
ペプチド結合
O
C
側鎖の例
Ala アラニン
Phe フェニル
アラニン
CH 3
CH
HC
Val バリン
H3 C
CH
C
CH 3
CH
O
CH
HC
Asp アスパラ
ギン酸
CH ２
O
C
-
His ヒス
チジン
Cys シス
テイン
HN
SH
+
NH
CH ２
CH 2
CH ２
Gly グリシン
H
アミノ酸コード表
Ala
Arg
Asn
Asp
Cys
Gln
Glu
Gly
His
Ile
A
R
N
D
C
Q
E
G
H
I
アラニン
アルギニン
アスパラギン
アスパラギン酸
システイン
グルタミン
グルタミン酸
グリシン
ヒスチジン
イソロイシン
Leu
Lys
Met
Phe
Pro
Ser
Thr
Trp
Tyr
Val
L ロイシン
K リシン
M メチオニン
F フェニルアラニン
P プロリン
S セリン
T トレオニン
W トリプトファン
Y チロシン
V バリン
バイオインフォマティクスにおけ
る確率統計

重要なのはデータからのモデル（もしくは
パラメータ）の推定



最尤法
ベイズ推定
最大事後確率推定（MAP）
最尤推定

P(D|θ) （尤度）


最尤法


モデルパラメータ θ のもとでのデータ D の出現確
率
P(D|θ) を最大化する θ を選ぶ
例




コインを5回投げて、表が3回出た後、裏が2回出た
p(表)=a, p(裏)=1-a とするとP(D|θ)=a3(1-a)2
a=3/5の時、 P(D|θ) は最大
一般に表が出る頻度を f とすると a=f で尤度は最大
ベイズ推定とMAP推定

ベイズ推定：尤度とモデル（パラメータ）の事前確
率から、ベイズの定理により、事後確率を推定
P( D | θ ) P(θ )
P(θ | D) 
P( D)
ただし、 P( D)   P( D | θ' ) P(θ' ) （ θが連続値の時）
θ'

最大事後確率（MAP）推定


P(D|θ)P(θ)を最大化するθを計算
P(θ)が一様分布なら最尤推定と同じ
不正サイコロのベイズ推定

公正サイコロと不正サイコロ




公正：P(i|公正)=1/6
不正：P(6|不正)=1/2,P(i|不正)=1/10 for i≠6
P(公正)=0.99, P(不正)=0.01
６が３回続けて出た場合の事後確率
P(666| 不正) P(不正)
P(不正 | 666) 
P(666)
(0.5)3 (0.01)

 0.21
3
1 3
(0.5) (0.01)  ( 6 ) (0.99)
アラインメント




バイオインフォマティクスの
最重要技術
２個もしくは３個以上の配列
の類似性の判定に利用
文字間の最適な対応関係を
求める（最適化問題）
２個の配列長を同じにする
ように、ギャップ記号（挿入、
欠失に対応）を挿入
A L G F G S L Y G
A L G G V S V G
A L G F G
A L G
S L Y G
G V S V
G
スコア行列（置換行列）

残基間（アミノ酸文字間）の類似性を表す行列

PAM250, BLOSUM45 など
A
A
R
N
D
C
Q
E
G
H
I
L
K
M
F
P
S
T
W
Y
V
5
-2
-1
-2
-1
-1
T
W
Y
V
-2 -1 -2 -1 -1 -1 0 -2 -1 -2 -1 -1 -3 -1 1 0
7 -1 -2 -4 1 0 -3 0 -4 -3 3 -2 -3 -3 -1 -1
-1 7 2 -2 0 0 0 1 -3 -4 0 -2 -4 -2 1 0
-2 2 8 -4 0 2 -1 -1 -4 -4 -1 -4 -5 -1 0 -1
-4 -2 -4 13 -3 -3 -3 -3 -2 -2 -3 -2 -2 -4 -1 -1
1 0 0 -3 7 2 -2 1 -3 -2 2 0 -4 -1 0 -1
R
N
D
C
Q
E
G
H
I
L
K
M
F
P
-3
-3
-4
-5
-5
-1
-2
-1
-2
-3
-3
-1
0
3
-3
-4
-1
-3
BLOSUM50 スコア行列
（置換行列）の一部分
S
ギャップ無しアラインメントのスコア
i xi yi
P ( x, y | M )
S  log
 log
P ( x, y | R )
i q xi  i q yi
p
px y
 log 
qx q y
i
i
i
i





i
x1 x2
y1 y2
 p 
ab 
 i s ( xi , y ) 但し , s(a, b)  log
q q 
i
 a b
スコア：P(x,y|M)とP(x,y|R)の対数オッズ比
P(x,y|R): ランダムモデルRにおいて、配列x,yが独立に生起する確率
qa:文字aのRにおける出現確率
P(x,y|M): 一致モデルMにおいて、配列x,yが生起する確率
pab :文字ペアa,bのMにおける出現確率
xn
yn
ギャップペナルティ

線形スコア


A L G
L Y G
A V G V S D L
アファインギャップスコア


γ(g)=-gd
(gはギャップの長さ、
ｄは定数）
ギャップ（g =3)
γ(g)=-d-e(g-1) （d:ギャップ開始ペナルティ,
e:ギャップ伸長ペナルティ）
ギャップの確率的解釈


P(gap)=f(g)Πqxi γ(g)=log(f(g))
ギャップ長の確率の対数
G
ペアワイズ・アラインメント


配列が２個の場合でも可能なアラインメントの個数は
指数オーダー
しかし、スコア最大となるアラインメント（最適アライン
メント）は動的計画法により、O(mn)時間で計算可能
（m,n:入力配列の長さ）
入力配列
AGCT, ACGCT
アラインメント
AGCT ACGCT
スコア -3
AG - CT
ACGCT
1
最適アラ
インメント
A - GCT
ACGCT
3
- AGC - - T
AC - - GCT
-5
（同じ文字の時1、違う文字の時-1,ギャップ1文字-1）
動的計画法による最適アラインメント
DP (動的計画法)による
最長経路の計算
最長経路計算による最適アライメント
G
G
F
V
D
5
K
-2
Y
-5
D
1
F (0, j )   jd , F (i,0)  id
-7
GK Y
G
 F (i  1, j  1)  s ( xi , y j )

F (i, j )  max
F (i  1, j )  d

F (i, j  1)  d

-5
-5
7
-1
-2
-2
-2
-7
1
0
-4
4
-7
-7
-7
-7
-7
-6
-7
D
F V D
行列からの経路の復元は、
F(m,n)からmaxで＝となっている
F(i,j)を逆にたどることに行う
（トレースバック）
局所アラインメント

H
G
A
W
E
D
0

 F (i  1, j  1)  s( , y )
xi j

F (i, j )  max
F (i  1, j )  d

F (i, j  1)  d


配列の一部のみに
共通部分があること
が多い
⇒共通部分のみの
アラインメント
E
A
W
G
E
H
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
2
1
0
0
0
0
1
0
1
0
2
1
0
0
0
0
0
0
1
1
AWGE
AW - E
（スコア：ギャップ-1、
置換-1、一致1）
配列検索の実用プログラム（１）
O(mn):mは数百だが、nは数ＧＢにもなる
⇒実用的アルゴリズムの開発
 FASTA:短い配列（アミノ酸の場合、1,2文字、
DNAの場合、4-6文字）の完全一致をもとに対角
線を検索し、さらにそれを両側に伸長し、最後に
ＤＰを利用
 BLAST:固定長（アミノ酸では3, DNAでは11）の全
ての類似単語のリストを生成し、ある閾値以上の
単語ペアを探し、それをもとに両側に伸長させる。
ギャップは入らない。

配列検索の実用プログラム（２）


SSEARCH: 局所アラインメント（SmithWatermanアルゴリズム）をそのまま実行
PSI-BLAST: ギャップを扱えるように拡張
したBLASTを繰り返し実行。「BLASTで見
つかった配列からプロファイルを作り、そ
れをもとに検索」という作業を繰り返す。
スコアのベイズ論的解釈




P(M|x,y)をベイズの定理に基づき導出
P(M):２個の配列に関連性がある事前確率
P(R)=1-P(M):ランダムモデルの事前確率
以下の式より尤度比にオッズ比を掛け合わせたものを
０と比較すべきであることがわかる
P ( x, y | M ) P ( M )
P ( x, y )
P ( x, y | M ) P ( M )

P ( x, y | M ) P ( M )  P ( x, y | R ) P ( R )
P ( x, y | M ) P ( M ) / P ( x, y | R ) P ( R )

 σ (S ' )
1  P ( x, y | M ) P ( M ) / P ( x, y | R ) P ( R )
σ(x)
P ( M | x, y ) 
1.0
0.5
0
x
 P ( x, y | M ) 
 P( M ) 
  log
, σ ( x)  e x
但し、 S '  log
1 e
 P ( x, y | R ) 
 P( R) 
-4
-2
0
2
ロジスティック関数
4
x
スコア行列の導出


基本的には頻度の比の対数をスコアとする
BLOSUM行列




既存のスコア行列を用いて多くの配列のアラインメ
ントを求め、ギャップ無しの領域（ブロック）を集める
残基がL％以上一致しているものを同一クラスタに
集める
同じクラスタ内で残基aが残基bにアラインされる頻
度Aabを計算
qa=∑b Aab / ∑cd Acd, pab=Aab / ∑cd Acd を求め、
ｓ
（a,b)=log(pab/qaqb) としたのち、スケーリングし近傍
の整数値に丸める
マルチプルアラインメント

３本以上の配列が与えられた時、長さが同じで、かつ、スコアが最適とな
るように各配列にギャップを挿入したもの
HBA_HUMAN
HBB_HUMAN
MYG_PHYCA
GLB5_PETMA
LGB2_LUPLU
GLB1_GLYDI

VGAHAGEY
VNVDEV
VEADVAGH
VYSTYETA
FNANIPKH
IAGADNGAGV
HBA_HUMAN
HBB_HUMAN
MYG_PHYCA
GLB5_PETMA
LGB2_LUPLU
GLB1_GLYDI
V
V
V
V
F
I
G
E
Y
N
A
A
A
S
A
G
A
D
H
N
D
T
N
N
A
V
V
Y
I
G
G
D
A
E
P
A
E
E
G
T
K
G
スコアづけ（全体スコアは基本的に各列のスコアの和:∑S(mi)）
 最小エントロピースコア


S(mi) = -∑cia log pia
SPスコア(Sum-of-Pairs)

S(mi)=∑k＜ｌ s(mik,mil)
（cia= i列におけるaの出現回数,
pia = i列におけるaの生起確率）
（mik = i列, k行目の文字）
Y
V
H
A
H
V
多次元DPによる
マルチプルアラインメント

N個の配列に対するマルチ
プルアラインメント


N次元DPによりO(2NnN)時間
（各配列の長さはO(n)を仮定）
(i,j,k-1)
例：N=3
 F (i  1, j  1, k  1)  S ( 1 , 2 , 3 )
xi x j x k

 F (i, j  1, k  1)  S (, 2 , 3 )
x j xk

 F (i  1, j , k  1)  S ( 1 ,, 3 )
xi x k

1
2

F (i, j , k )  max  F (i  1, j  1, k )  S ( xi , x j ,)

3
 F (i, j , k  1)  S (,, xk )

2
 F (i, j  1, k )  S (, x j ,)

 F (i  1, j , k )  S ( x1i ,,)

(i,j-1,k)
(i-1,j,k) (i,j,k)
実用的マルチプルアラインメント法

ヒューリスティックアルゴリズム
の開発



STEP 1
N次元DPは（N=4ですら）
非実用的
一般にはNP困難
プログレッシブアラインメント
1.
2.

入力配列
近隣結合法などを用いて案内
木を作る
類似度が高い節点から低い節
点へという順番で、配列対配列、
配列対プロファイル、プロファイ
ル対プロファイルのアラインメン
トを順次計算
逐次改善法

「配列を一本取り除いては、アラ
インメントしなおす」を繰り返す
STEP 2
③
①
②
マルチプルアラインメントの
近似アルゴリズム(1)


スコアに三角不等
式を仮定し、最小
化問題として定義
アルゴリズム
1.
2.
∑k≠iS(xk,xi)が最小と
なるxkを求める
S(xk,xi)をもとに
ギャップを適切に挿
入し、マルチプルア
ラインメントA を構
成
x1
x2
STAR-1
STAR-2
STAR-3
STAR-4
x3
ACGT
A-GT
A-CGT
AACGT
ACG-T
A-GGT
x4
A-CG-T
A--G-T
AACG-T
A--GGT
マルチプルアラインメントの
近似アルゴリズム(2)

定理


A のSPスコア ≦
(2-2/N)・最適解の
SPスコア
図１
x1
x2
x3
x4
証明


N・Starのスコア ≦
2・最適解のスコア
(図１でNスターにより、各辺
を２回ずつカバー)
A のスコア ≦
(N-１)・Starのスコア
(図２でｘ１に接続しない辺の
スコアの合計はスター(N-2)
個分以下)
図２
三角不等式
x1
x2
xk
xi
x3
x4
xj
局所マルチプルアラインメント
(Local Multiple Alignment)


複数配列と長さLが与えられた時、スコア最大と
なるように各配列から長さLの部分列を抽出
モチーフ（共通の性質を持つ遺伝子などに共通
の部分パターン）抽出などに有用
Sequence 1
Sequence 2
Sequence 3
A A T C G G T
A A T C C G T
A T T C G G A
相対エントロピースコアのもとでの
局所マルチプルアラインメント

相対エントロピースコアの定義





fj(a): （モチーフ領域の）j列目におけるaの出現頻度
p(a): aの出現頻度（事前確率）
L: モチーフ領域の長さ
f j (a)
L
score   j 1a f j (a) log
p(a)
実用的アルゴリズム
 Gibbsサンプリング, EM
NP困難
Gibbs サンプリング
1.
2.
各配列xjからランダム
に部分配列tjを選ぶ
1個の配列xiをランダム
に選ぶ
3.
4.
5.
Step 1
x1
t1
x2
x3
t2
t3
f j (t 'i[ j])

j 1 p(t 'i[ j ])
L
xiの部分列ti’を
に比例する確率で選ぶ
ti をti’ でおきかえる
ステップ2-4を十分な回
数だけ繰り返す
( ti[j]: 部分列ti のj列目の文字 )
Step 2-3
Probabilistic Search
x2
t2’
Step 4
x1
x2
x3
t1
t2’
t3
隠れマルコフモデル(HMM)


HMM=有限オートマトン＋確率
定義



出力記号集合Σ
状態集合
S={1,2,…n}
遷移確率(k→ｌ)
0.4
0.3
akl

1
出力確率
ek(b)

（開始状態=
終了状態= 0)
2
0.5
0.5
A: 0.2
B: 0.8
0.6
3
0.7
A: 0.1
B: 0.9
A: 0.7
B: 0.3
HMMにおける基本アルゴリズム

Viterbiアルゴリズム




BABBBAB
出力記号列から状
態列を推定
Parsing（構文解析）
Baum-Welchアルゴ
リズム
(EMアルゴリズム）

0.4
出力記号列からパ
ラメータを推定
Learning（学習）
2
0.3
1
0.5
0.5
0.6
A: 0.2
B: 0.8
0.7
A: 0.1
B: 0.9
A: 0.7
B: 0.3
3
2312131
2
1
0.4
0.3
3
BABBBAB
ABBABBAAB
BBBABBABAB
BAABBBBA
2
1
0.5 0.7
0.5
A: 0.2
B: 0.8
0.6
3
A: 0.1
B: 0.9
A: 0.7
B: 0.3
時々いかさまをするカジノ





サイコロの出目だけが観測可能、どちらのサイコロを振っているか
は観測不可能
サイコロの出目から、どちらのサイコロを振っているかを推定
6,2,6,6,3,6,6,6,
4,6,5,3,6,6,1,2
0.95
0.9
→不正サイコロ
6,1,5,3,2,4,6,3,
1: 1/6
0.05
1: 1/10
2,2,5,4,1,6,3,4
2: 1/6
2: 1/10
3: 1/6
3: 1/10
→公正サイコロ
4: 1/6
4: 1/10
5: 1/6
5: 1/10
6,6,3,6,5,6,6,1,
0.1
6: 1/6
6: 1/2
5,4,2,3,6,1,5,2
→途中で公正サイ
不正サイコロ
公正サイコロ
コロに交換
Viterbi アルゴリズム(1)



観測列（出力配列データ） x=x1…xLと状態列π=π1…πLが与えられた時、
その同時確率は
P(x,π)=a0 π1Πeπi (xi)aπiπi+1 但し、πL+1=0
xが与えられた時の、最も尤もらしい状態列は π*=argmaxπ P(x,π)
例：どちらのサイコロがいつ使われたかを推定
0.95
x1=4
公
0.05
不
0.9
0.5
0.1
公
x2=3
0.95
公
0.05
0
不
0.95
公
0.05
0.1
0.5
x3=2
0
0.1
0.9
不
0.9
不
max P( x1 x2 x3 , π)  P( x1 x2 x3 , 公公公 )  0.5  16  0.95  16  0.95  16
π
Viterbiアルゴリズム(2)


xから、π*=argmaxπ P(x,π) を計算
そのためにはx1…xiを出力し状態kに至る確率最
大の状態列の確率 vk(i) を計算
v (i)  max
k

π
i 1
a0π1  eπ j( x j)a π j π j 1
j 1
vk(i)は以下の式に基づき動的計画法で計算
v (i  1)  e ( x
l
l
)
i 1
max (v
k
k
(i ) a kl )
Viterbiアルゴリズム(3)
0.95
i-1
i
i+1
4
6
1
公
0.05
0.1
公
v
公
公
0.05
不
0.95
公
0.05
0.1
不
0.9
0.95
0.1
0.9
不
0.9
不
(i  1)  max{e公 (1)  0.95 v公 (i), e公 (1)  0.1 v不 (i) }
EM(Expectation Maximization)
アルゴリズム

「欠けているデータ」のある場合の最尤推定のた
めの一般的アルゴリズム
x : 観測データ、 y : 欠けているデータ、
θ : パラメータ集合
目標： log P( x|θ )  log  P( x,y|θ ) の最大化
y


最大化は困難であるので、反復により尤度を単調
増加させる（θtよりθt+1を計算）
HMMの場合、「欠けているデータ」は状態列
EMアルゴリズムの導出
log P( x | θ)  log P( x, y | θ)  log P( y | x, θ)
両辺にP( y | x, θ t )をかけて yについての和をとり、
log P( x | θ)   P( y | x, θ t ) log P( x, y | θ)   P( y | x,θ t ) log P( y | x, θ)
y
y
右辺第１項を Q(θ | θ t )とおくと、
log P( x | θ)  log P( x | θ t ) 
P ( y | x, θ t )
Q(θ | θ )  Q(θ | θ )   P( y | x, θ ) log
P ( y | x, θ )
y
t
t
t
t
最後の項は相対エントロピーで常に正なので、
log P( x | θ)  log P( x | θ t )  Q(θ | θ t )  Q(θ t | θ t )
よって、 θ t 1  arg maxQ(θ | θ t ) とすれば尤度は増大
θ
EMアルゴリズムの一般形
1.
2.
3.
4.
初期パラメータ Θ0 を決定。t=0とする。
Q(θ|θt)=∑P(y|x, θt) log P(x,y|θ) を計算。
Q(θ|θt)を最大化するθ*を計算し、 θt+1 =
θ* とする。t=t+1とする。
Qが増大しなくなるまで、２，３を繰り返す。
前向きアルゴリズム
配列xの生成確率
P(x)=∑P(x,π) を計
算
 Viterbiアルゴリズ
ムと類似
 fk(i)=P(x1…xi,πi=k)
をDPにより計算

f 0 (0)  1, f k (0)  0
f l (i )  el ( xi ) f k (i  1) akl
k
P ( x )  k f k ( L ) a k 0
1 a11
2
3
a21
a31
1
2
3
f 1 (i )  e1 ( xi )
( f 1 (i  1) a11 
f 2 (i  1) a 21 
f 3 (i  1) a 31)
後向きアルゴリズム
bk(i)=
P(xi+1…xL|πi=k)
をDPにより計算
 P(πi=k|x) =
fk(i)bk(i)/P(x)
b ( L)  a
b (i)   a kl e ( x )b (i  1)

k0
k
k
i 1
l
l
k
P( x)  k a0l el ( x1) bl (1)
1
2
3
a11 1 b (i) 
a12
(a e ( x ) b (i  1) 
2
a e ( x ) b (i  1) 
a13
3 a e ( x ) b (i  1))
1
1
i 1
1
12
2
i 1
2
13
3
i 1
3
11
HMMに対するEMアルゴリズム
（Baum-Welchアルゴリズム）
j
x : j番目の配列
Akl: a
E k (b) : 文字bが状態kから現れる回数の期待値
が使われる回数の期待値
kl
Akl
Ek

j
(b) 
1
P( x
j

)
i
f (i) akl el ( xi 1) bl (i  1)
1
 P(
j
j
j
k

i|
j
j
b
j
f (i) bk (i )
x ) x 
j
j
k
j
パラメータの更新式
aˆ  A
A
kl
kl
l'
kl '
(b)
E
eˆ (b)   (b' )
E
k
k
b'
k
Baum-WelchのEMによる解釈
M
P ( x, π | θ )  
k 1
b
E k ( b ,π )
e (b)
k
M
M
Akl ( π ) および
 akl
k  0 l 1
Q(θ | θ t )   P (π | x, θ t ) log P ( x, π | θ ) より、
π
M M
M

Q (θ | θ )   P (π | x, θ )    E k (b, π ) log ek (b)   Akl (π ) log a kl 
π
k  0 l 1
 k 1 b

t
t
M
M
M
  E k (b) log ek (b)   Akl log a kl
k 1 b
ここで
k  0 l 1
 p log q は q  p の時、最大より、
(b)
E
A
(
b
)

,

e
a
(
b
'
)
E
A
i
i
i
i
i
k
kl
kl
k
k
b'
l'
kl
プロファイルHMM(1)


配列をアラインメントするためのHMM
一致状態(M)、欠失状態(D)、挿入状態(I)を持つ
D
D
D
I
I
I
I
BEGIN
M
M
M
END
プロファイルHMM(2)
マルチプル
アラインメント
プロファイル
HMM
M M ・・・ M
D
D
D
I
I
I
I
BEGIN
M
M
M
こうもり A G －－－ C
ラット
A －A G －C
ネコ
A G －A A －
ハエ
－－A A A C
ヤギ
A G －－－C
END

Download Report