讲座隐马尔可夫模型及其应用

HiddenMarkovModelsandIts马尔可夫是俄国（前苏联）数学家(1856-1922)。马尔可夫于19061912年间通过多次观察试验发现：自然界的很多系统其状态x(t1)fSSs1,s2,s3, si⑤由于马氏链在时刻m从任何一个状态Si出发，到另一时刻m+n，必然转移到Sj，j=1,2,…，诸状⑥当pij(m,m+n)与m无关时，称马尔科夫链为齐次XX x3,P p(xt1sj | sip(x0si),i1,p(xt1s3|xts1)1

p(xt1s1|xts2)1

|

)11p(xt1s1|xts3)13p(xt1s2|xts3)23p(xt1s3|xts3)0

p(xt1s3|xts2) LP(S)p(s1

列长度加2x0=‘BxL+1=‘E’，则上述公式简化为：

i f①令

为CpGf为CpGfScore(S) P(S|CpGP(S|non_CpG

fffffst

cc

cfcc t

ststtfAG具有正值的Sk就是可能的CpG岛。隐马尔可夫模型（HiddenMarkovModel记作：HMM）是马尔可夫模马尔可夫模型主要是把一个总随机O(o1o2...oT) 112O(o1o2...oT)第一个色子，投掷出每个数字的概率：p1,p2,p3,p4,p5,第二个色子，投掷出每个数字的概率：p1*,p2*,p3*,p4*,p5*,λ＝(N,M,πAB）来描述，或λ=(π,A,B)AABB{bjiA,B),如何计算P(O|λ)？(估算问题)问题2：给定观察序列O=O1,O2,…OT以及模型λ,如问题3：λ=(π,A,B),使得所有的观测序列发生的概率最大？(学问题二：Viterbi（解码问题）TP(O/S,) t

/qt,)bq(O1)bq(O2

bq(Ot qtb(O qtt

P(O/)P(OS

S,)P(S/Oaijt(

itjt1i

aijbj(ot)(t1,终结：P(O|)T前向概率为0（0j)0j1）；at(j)=at-1(i)aijbj(ot=at-1(1)a1jbj(ot)+at-1(2)a2jbj(ot )++at-1(N)aNjbj(ot (i,j=1,2,N) aij把最后时刻的前向概率取出，则p(O|T(N)…… …… …

ajj

t(

t-

N=5, T(N1,Tj0j

t(i)t1(j)bj(ot1jp(O|) Viterbi

'(1)1,'(j)0(j '(j) (i)ab t i 递推公式(t1, T;i,j1, NT最后结果p(S,O|max('T0'0率为0（0'j)0,j1）；t在t时刻，根据输出的观察符号Otj)ta'(j)=max{a'(i)ab(ot-

),a'(2)a2jbj

),a'(N)aNjbj(ot (i,j=1,2,T把最后时刻的最优前向概率取出，则pmax(S,O|'(N)①用Baum-Welch方法(或EM)对于给定的序列X,调整模型的可以得到状态转换概率（如下图在λ中为X寻找一条最优路径，要求使得

p(X|HiddenMarkovModel,GHMMs）。AAAAAAAAAAAAAAAAAAAAACTCCCTGTGTCCACGCTTATTGTTTTCTTACGGCGTTCCTTTGTTTCTCACTGCCTCTCTTTTCAGGTTTCTGTTCCGATGCGGCTTGGGTTTCTTTGCAACCACTTTGCTCCCACCGTCCCATGTGACCTGCGTATATTTATTTAACATGGCATGTGCATCCCCCCGAGTTTTCCTTTTCTACAATTCGTGTGTCTCCCCCCCTTCCATGTCCTGACGTGACGACATTTTCCACGAGGTGCCTCTCCCTCCATTACTGTC…(3编码区模型(续(3说明：x表示未编码的DN