隐马尔可夫模型及其在生物信息学中的应用

隐马尔科夫模型隐马尔科夫模型(HMM)(HMM)及其在生物信息学中的应用及其在生物信息学中的应用主讲：戴培山主讲：戴培山中南大学信息物理工程学院中南大学信息物理工程学院生物医学工程研究所生物医学工程研究所生物信息学专题内容提要内容提要1.1.HMMHMM的概述与应用的概述与应用2.2.HMMHMM的定义及三个基本问题的定义及三个基本问题3.3.三个基本问题的求解算法三个基本问题的求解算法4.4.应用中注意的一些问题应用中注意的一些问题5.5.课外文献阅读及练习题课外文献阅读及练习题HMMHMM的概述与应用的概述与应用„„HMMHMM模型是一项发展多年的建模技术模型是一项发展多年的建模技术,,它曾它曾经在经在语音识别语音识别、、光字符识别光字符识别(OCR)(OCR)等领域得等领域得到过最成功的应用。到过最成功的应用。„„上世纪八九十年代，上世纪八九十年代，HMMHMM开始应用于生物信开始应用于生物信息学息学,,对于研究蛋白质家族同源性对于研究蛋白质家族同源性,,揭示进化揭示进化保守性发挥了重要作用。保守性发挥了重要作用。„„在生物信息学中的主要应用在生物信息学中的主要应用••DNADNA的编码区的编码区//非编码区建模非编码区建模••进化发育分析进化发育分析••蛋白质结构预测研究蛋白质结构预测研究马尔科夫及隐马尔科夫模型马尔科夫及隐马尔科夫模型„„18701870年，俄国有机化学家年，俄国有机化学家VladimirV.VladimirV.MarkovnikovMarkovnikov首次提出马尔科夫模型首次提出马尔科夫模型„„马尔科夫模型马尔科夫模型„„马尔科夫链马尔科夫链„„隐马尔科夫模型隐马尔科夫模型VladimirV.VladimirV.MarkovnikovMarkovnikov例子例子::赌场的欺诈赌场的欺诈某赌场在掷骰子根据点数决定胜负时某赌场在掷骰子根据点数决定胜负时,,暗中采取暗中采取了如下作弊手段了如下作弊手段在连续多次掷骰子的过程中在连续多次掷骰子的过程中,,通常使用公平骰子通常使用公平骰子A,A,偶而偶而混入一个灌铅骰子混入一个灌铅骰子BBAB0.90.10.80.2赌场的欺诈赌场的欺诈((续续))公平骰子公平骰子AA与灌铅骰子与灌铅骰子BB的区别的区别骰子骰子AA骰子骰子BB11点点1/61/60022点点1/61/61/81/833点点1/61/61/81/844点点1/61/63/163/1655点点1/61/63/163/1666点点1/61/63/83/8赌场的欺诈赌场的欺诈((续续))一次连续掷骰子的过程模拟一次连续掷骰子的过程模拟时间时间11223344556677骰子骰子掷出掷出点数点数1:1/62:1/63:1/64:1/65:1/66:1/61:02:1/83:1/84:3/165:3/166:3/8开始骰子A骰子B1.000.10.80.90.2赌场的欺诈赌场的欺诈((续续))一次连续掷骰子的过程模拟一次连续掷骰子的过程模拟时间时间11223344556677骰子骰子AA掷出掷出点数点数1:1/62:1/63:1/64:1/65:1/66:1/61:02:1/83:1/84:3/165:3/166:3/8开始骰子A骰子B1.000.10.80.90.2赌场的欺诈赌场的欺诈((续续))一次连续掷骰子的过程模拟一次连续掷骰子的过程模拟时间时间11223344556677骰子骰子AA掷出掷出点数点数331:1/62:1/63:1/64:1/65:1/66:1/61:02:1/83:1/84:3/165:3/166:3/8开始骰子A骰子B1.000.10.80.90.2赌场的欺诈赌场的欺诈((续续))一次连续掷骰子的过程模拟一次连续掷骰子的过程模拟时间时间11223344556677骰子骰子AAAA掷出掷出点数点数331:1/62:1/63:1/64:1/65:1/66:1/61:02:1/83:1/84:3/165:3/166:3/8开始骰子A骰子B1.000.10.80.90.2赌场的欺诈赌场的欺诈((续续))一次连续掷骰子的过程模拟一次连续掷骰子的过程模拟时间时间11223344556677骰子骰子AAAA掷出掷出点数点数33331:1/62:1/63:1/64:1/65:1/66:1/61:02:1/83:1/84:3/165:3/166:3/8开始骰子A骰子B1.000.10.80.90.2赌场的欺诈赌场的欺诈((续续))一次连续掷骰子的过程模拟一次连续掷骰子的过程模拟时间时间11223344556677骰子骰子AAAAAA掷出掷出点数点数33331:1/62:1/63:1/64:1/65:1/66:1/61:02:1/83:1/84:3/165:3/166:3/8开始骰子A骰子B1.000.10.80.90.2赌场的欺诈赌场的欺诈((续续))一次连续掷骰子的过程模拟一次连续掷骰子的过程模拟时间时间11223344556677骰子骰子AAAAAA掷出掷出点数点数3333441:1/62:1/63:1/64:1/65:1/66:1/61:02:1/83:1/84:3/165:3/166:3/8开始骰子A骰子B1.000.10.80.90.2赌场的欺诈赌场的欺诈((续续))一次连续掷骰子的过程模拟一次连续掷骰子的过程模拟时间时间11223344556677骰子骰子AAAAAABB掷出掷出点数点数3333441:1/62:1/63:1/64:1/65:1/66:1/61:02:1/83:1/84:3/165:3/166:3/8开始骰子A骰子B1.000.10.80.90.2赌场的欺诈赌场的欺诈((续续))一次连续掷骰子的过程模拟一次连续掷骰子的过程模拟时间时间11223344556677骰子骰子AAAAAABB掷出掷出点数点数333344551:1/62:1/63:1/64:1/65:1/66:1/61:02:1/83:1/84:3/165:3/166:3/8开始骰子A骰子B1.000.10.80.90.2赌场的欺诈赌场的欺诈((续续))一次连续掷骰子的过程模拟一次连续掷骰子的过程模拟时间时间11223344556677骰子骰子AAAAAABBAA掷出掷出点数点数333344551:1/62:1/63:1/64:1/65:1/66:1/61:02:1/83:1/84:3/165:3/166:3/8开始骰子A骰子B1.000.10.80.90.2赌场的欺诈赌场的欺诈((续续))一次连续掷骰子的过程模拟一次连续掷骰子的过程模拟时间时间11223344556677骰子骰子AAAAAABBAA掷出掷出点数点数33334455111:1/62:1/63:1/64:1/65:1/66:1/61:02:1/83:1/84:3/165:3/166:3/8开始骰子A骰子B1.000.10.80.90.2赌场的欺诈赌场的欺诈((续续))一次连续掷骰子的过程模拟一次连续掷骰子的过程模拟时间时间11223344556677骰子骰子AAAAAABBAAAAAA掷出掷出点数点数333344551166221:1/62:1/63:1/64:1/65:1/66:1/61:02:1/83:1/84:3/165:3/166:3/8开始骰子A骰子B1.000.10.80.90.2赌场的欺诈赌场的欺诈((续续))一次连续掷骰子的过程模拟一次连续掷骰子的过程模拟时间时间11223344556677骰子骰子AAAAAABBAAAAAA掷出掷出点数点数33334455116622隐序列明序列查封赌场后,调查人员发现了一些连续掷骰子的记录,其中有一个骰子掷出的点数记录如下:33451625536634411346254453342233…问题问题11––评估问题评估问题给定给定一个骰子掷出的点数记录一个骰子掷出的点数记录124552124552664466214214661414661313661313666666116666446666116633666611663366661166336611665155156615115141511514661235123566234234问题问题会出现这个点数记录的概率有多大会出现这个点数记录的概率有多大??评估问题评估问题((EVALUATIONEVALUATION))问题问题22––解码问题解码问题给定给定一个骰子掷出的点数记录一个骰子掷出的点数记录124552124552664466214214661414661313661313666666116666446666116633666611663366661166336611665155156615115141511514661235123566234234问题问题点数序列中的哪些点数是用骰子点数序列中的哪些点数是用骰子BB掷出的掷出的??解码问题解码问题((DECODINGDECODING))问题问题33––学习问题学习问题给定给定一个骰子掷出的点数记录一个骰子掷出的点数记录124552124552664466214214661414661313661313666666116666446666116633666611663366661166336611665155156615115141511514661235123566234234问题问题作弊骰子掷出各点数的概率是怎样的作弊骰子掷出各点数的概率是怎样的??公平骰子公平骰子掷出各掷出各点数点数的概率又是怎样的的概率又是怎样的??赌场是何时赌场是何时换用骰子的换用骰子的??赌场的欺诈赌场的欺诈::三个问题三个问题1.1.从骰子点数序列中推断是否使用了上述从骰子点数序列中推断是否使用了上述““作作弊弊””模型模型??2.2.如果确实使用了上述如果确实使用了上述““作弊作弊””模型模型,,推断骰子推断骰子点数序列中的哪些点数是用骰子点数序列中的哪些点数是用骰子BB掷出的掷出的??3.3.仅仅给定大量的点数序列仅仅给定大量的点数序列,,如何从中推断如何从中推断““作弊作弊””模型中的细节模型中的细节((如如::骰子骰子AA与与BB之间的之间的转换概率转换概率、、骰子骰子BB掷出各点的概率值掷出各点的概率值)?)?HMMHMM的定义的定义HMMHMM的定义的定义„„赌场的例子中赌场的例子中隐状态集隐状态集::S={S={骰子骰子A,A,骰子骰子B}B}明字符集明字符集::V={1,2,3,4,5,6}V={1,2,3,4,5,6}初始状态概率初始状态概率::ππ11=1,=1,ππ22=0=0隐状态转移概率隐状态转移概率::aa1111=0.9,a=0.9,a1212=0.1=0.1aa2121=0.8,a=0.8,a2222=0.2=0.2明字符生成概率明字符生成概率bb1111=b=b1212==……=b=b1616=1/6=1/6bb2121=0,b=0,b2222=b=b2323=1/8,b=1/8,b2424=b=b2525=3/16,b=3/16,b2626=3/8=3/81:1/62:1/63:1/64:1/65:1/66:1/61:02:1/83:1/84:3/165:3/166:3/8哑状态骰子A骰子B初始状态1.000.10.80.90.2HMMHMM的定义的定义((续续))„„一阶离散一阶离散HMMHMM是一个关于是一个关于时间时间序列的随机生序列的随机生成模型成模型„„基本要素基本要素有限隐状态集有限隐状态集S={SS={S11,,……,S,SNN}}离散明字符集离散明字符集V={VV={V11,,……,V,VMM}}初始状态概率矢量初始状态概率矢量ππ=(=(ππ11,,……,,ππNN))状态转移概率矩阵状态转移概率矩阵A=(A=(aaijij))NN××NN明字符生成概率矩阵明字符生成概率矩阵B=(B=(bbjkjk))NN××MM„„HMMHMM记作记作λλ=(S,V,=(S,V,ππ,A,B),A,B)或或λλ=(=(ππ,A,B),A,B)aa