生物信息學(xué)實驗市公開課一等獎百校聯(lián)賽特等獎?wù)n件

生物信息學(xué)試驗試驗2隱馬爾科夫模型上海交通大學(xué)生命科學(xué)技術(shù)學(xué)院生物信息學(xué)與生物統(tǒng)計學(xué)系10/10/1第1頁生物學(xué)中慣用統(tǒng)計模型 StructuredprobabilitymodelsMarkovmodelsHiddenmarkovmodelsArtificialNeuralNetwork(A.N.N)

10/10/2第2頁IntroductionHiddenMarkovModels(HMMs)最早是在上個世紀(jì)60年代末70年代初提出來。進入80年代以后，逐步被利用在各個領(lǐng)域。10/10/3第3頁IntroductionHiddenMarkovModels作為一個強有力統(tǒng)計學(xué)模型，主要被應(yīng)用在一些連續(xù)行或時間延續(xù)性事件建模上語音識別系統(tǒng)。生物學(xué)中DNA/protein序列分析機器人控制。文本文件信息提取。10/10/4第4頁HMM優(yōu)點1，它數(shù)學(xué)結(jié)構(gòu)非常豐富，適合用于各個領(lǐng)域研究。2，在很多領(lǐng)域中，已經(jīng)證實它結(jié)果和實際符合相當(dāng)好。10/10/5第5頁ProbabilityReview10/10/6第6頁獨立事件概率構(gòu)想我們做一連串試驗，而每次試驗所可能發(fā)生結(jié)果定為E1,E2,…En,…。（可能是有限也可能是無限）。每一個結(jié)果Ek，假如給定一個出現(xiàn)可能性pk（即概率），則某一特定樣本之序列Ej1

Ej2…Ejn出現(xiàn)概率為p(Ej1

Ej2…Ejn)=pj1…Pjn。10/10/7第7頁馬爾科夫鏈普通及慣用統(tǒng)計中，彼此相互「獨立」大約是最有用一個觀念。用簡單術(shù)語來說，相互「獨立」就是彼此毫不相干，一點牽涉都沒有。不過實際生活中很多事件是相互關(guān)聯(lián)[不是相互獨立」也就是相互關(guān)聯(lián)意思，不過要怎樣相關(guān)呢？怎樣在相關(guān)中作一些簡單分類呢？馬爾科夫鏈就是要描述在「相關(guān)」這個概念中最簡單一個。但即使如此，相關(guān)馬可夫鏈理論已經(jīng)相當(dāng)豐富了。在概率理論中，它幾乎占了絕大部分。10/10/8第8頁馬爾科夫鏈在馬爾科夫鏈中考慮最簡單「相關(guān)」性。在在這種情況下，我們不能給任一個事件Ej一個概率pj但我們給一對事件(Ej,Ek)一個概率pjk，這個時候pjk解釋是一個條件概率，就是假設(shè)在某次試驗中Ej已經(jīng)出現(xiàn)，而在下一次試驗中Ek出現(xiàn)概率。除了pjk之外，還需要知道第一次試驗中Ej出現(xiàn)機率aj。有了這些資料后，一個樣本序列Ej0

Ej1…Ejn（也就是說第零次試驗結(jié)果是Ej0，第一次一次是Ej1……第n次試驗是Ejn）概率就很清楚是P(Ej0,Ej1,Ejn)=aj

pj0j1

pj1j2…pjn-1jn。10/10/9第9頁隱馬爾科夫模型不過在大多數(shù)情況下我們所觀察到值并不是序列本身元素。即觀察值不等于狀態(tài)值。故我們引入隱馬爾科夫模型。10/10/10第10頁定義一個HMM是一個五元組：(ΩX,ΩO,A,B,π)其中：ΩX={q1,...qN}：狀態(tài)有限集合ΩO={v1,...,vM}：觀察值有限集合A={aij}，aij=p(Xt+1=qj|Xt=qi)：轉(zhuǎn)移概率B={bik}，bik=p(Ot=vk|Xt=qi)：輸出概率π={πi}，πi=p(X1=qi)：初始狀態(tài)分布10/10/11第11頁假設(shè)對于一個隨機事件，有一個觀察值序列：O1,...,OT該事件隱含著一個狀態(tài)序列：X1,...,XT假設(shè)1：馬爾可夫假設(shè)（狀態(tài)組成一階馬爾可夫鏈）

p(Xi|Xi-1…X1)=p(Xi|Xi-1)假設(shè)2：不動性假設(shè)（狀態(tài)與詳細時間無關(guān)）p(Xi+1|Xi)=p(Xj+1|Xj)，對任意i,j成立假設(shè)3：輸出獨立性假設(shè)（輸出僅與當(dāng)前狀態(tài)相關(guān)）

p(O1,...,OT|X1,...,XT)=Πp(Ot|Xt)10/10/12第12頁馬爾科夫鏈Vs隱馬爾科夫模型Markovchainshaveentirelyobservablestates.Howevera“HiddenMarkovModel”isamodelofaMarkovSourcewhichadmitsanelementeachtimeslotdependinguponthestate.Thestatesarenotdirectlyobserved10/10/13第13頁Problems令λ={A,B,π}為給定HMM參數(shù)，令σ=O1,...,OT為觀察值序列，隱馬爾可夫模型（HMM）三個基本問題：評定問題：對于給定模型，求某個觀察值序列概率p(σ|λ)；forwardalgorithm解碼問題：對于給定模型和觀察值序列，求可能性最大狀態(tài)序列；viterbialgorithm學(xué)習(xí)問題：對于給定一個觀察值序列，調(diào)整參數(shù)λ，使得觀察值出現(xiàn)概率p(σ|λ)最大。Forward-backwardalgorithm10/10/14第14頁SolutionsEvaluationproblem：forwardalgorithm定義向前變量采取動態(tài)規(guī)劃算法，復(fù)雜度O(N2T)Decodingproblem：Viterbialgorithm采取動態(tài)規(guī)劃算法，復(fù)雜度O(N2T)Learningproblem：forward-backwardalgorithmEM算法一個特例，帶隱變量最大似然預(yù)計10/10/15第15頁StructHMMtypedefstruct{

/*numberofstates;Q={1,2,...,N}*/

intN; /*numberofobservationsymbols;V={1,2,...,M}*/ intM; /*A[1..N][1..N].a[i][j]isthetransitionprobofgoingfromstatei*attimettostatejattimet+1*/

double**A; /*B[1..N][1..M].b[j][k]istheprobabilityofobservingsymbolkinstatej*/

double**B; /*pi[1..N]pi[i]istheinitialstatedistribution.*/ double*pi;

}HMM;10/10/16第16頁算法：向前算法（1）10/10/17第17頁算法：向前算法（2）定義前向變量為HMM在時間t輸出序列O1…Ot，而且位于狀態(tài)Si概率：10/10/18第18頁算法：向前算法（3）迭代公式為：結(jié)果為：10/10/19第19頁Forwardalgorithm10/10/20第20頁算法：向后算法（1）10/10/21第21頁算法：Viterbi算法（1）TheViterbialgorithmisadynamicprogrammingalgorithmthatcomputesthemostlikelystatetransitionpathgivenanobservedsequenceofsymbols.Itisactuallyverysimilartotheforwardalgorithm。10/10/22第22頁Viterbialgorithm10/10/23第23頁Viterbiinc/*1.Initialization*/

for(i=1;i<=phmm->N;i++){

delta[1][i]=phmm->pi[i]*(phmm->B[i][O[1]]);

psi[1][i]=0;

}

/*2.Recursion*/

for(t=2;t<=T;t++){

for(j=1;j<=phmm->N;j++){

maxval=0.0;

maxvalind=1;

for(i=1;i<=phmm->N;i++){

val=delta[t-1][i]*(phmm->A[i][j]);

if(val>maxval){

maxval=val;

maxvalind=i;

}

}

delta[t][j]=maxval*(phmm->B[j][O[t]]);

psi[t][j]=maxvalind;

}

}10/10/24第24頁生物學(xué)中數(shù)學(xué)模型10/10/25第25頁馬氏鏈10/10/26第26頁馬氏鏈10/10/27第27頁馬氏鏈10/10/28第28頁隱馬可夫模型10/10/29第29頁隱馬可夫模型10/10/30第30頁隱馬可夫模型profile10/10/31第31頁RelatedsoftwareHMMER/SAM(SequenceAlignmentandModelingSystem)/

HMMproAwindowsversionforHMMTheDivisionofBiomedicalInformaticsatCincinnatiChildren'sHospitalMedicalCentermetaMEME:AmotifbasedHiddenMarkovModel10/10/32第32頁HMMERProfilehiddenMarkovmodels(profileHMMs)canbeusedtodosensitivedatabasesearchingusingstatisticaldescriptionsofasequencefamily'sconsensus.HMMERisafreelydistributableimplementationofprofileHMMsoftwareforproteinsequenceanalysis.ThecurrentversionisHMMER2.3.2(3Oct),containingminorbugfixesandupdatesfortheMayreleaseofHMMER2.3.

10/10/33第33頁HMMER10/10/34第34頁HowtocreateaHMM多序列比對相關(guān)序列選取模型構(gòu)建模型訓(xùn)練參數(shù)調(diào)整應(yīng)用確立模型10/10/35第35頁Example:1.Sequenceselection選取相關(guān)序列10/10/36第36頁2.AlignmentSaveresultasmsfformat多序列比對10/10/37第37頁模型建立3.Hmmbuild4.Hmmt5.Hmmcalibrate模型建立用相關(guān)序列對模型進行訓(xùn)練參數(shù)調(diào)整10/10/38第38頁模型文件（1）HMMER2.0[2.3.2]NAMEglobins50LENG162ALPHAminoRFnoCSnoMAPyesCOM./hmmbuildglobins.hmmglobins50.msfNSEQ50DATEThuSep1800:02:14CKSUM4694XT-8455-4-1000-1000-8455-4-8455-4NULT-4-8455NULE595-155885338-294453-1158197249902-1085-142-21-31345531201384-1998-64410/10/39第39頁模型文件（2）模型部分：HMMACDEFGHIKLMNPQRSTVWYm->mm->im->di->mi->id->md->db->mm->e-222*-28071-1412-1712-339-321-1729113-1457261-1493-15911181-1737-32-1359-178877-13532620-2119-16974--149-50023343-381399106-626210-466-7202753944596359117-369-294-249--1909-8804-451-894-1115-701-1378-110*2-1118-1371-1805-1237-1464-2231-88925282067-899-510-1267-2325-644-266-1422-1057-63-1884-14865--149-50023343-381399106-626210-466-7202753944596359117-369-294-249--18-6914-7956-894-1115-3550-129**…10/10/40第40頁6.未知序列搜索查詢Hmmsearch:searchasequenceagainsttheprofileHMM未知查詢序列Artemia.faProfileHMM：Globin.hmmCommand:hmmsearchglobin.hmmArtemia.fa查詢程序查詢未知序列文件所用模型查詢命令10/10/41第41頁查詢結(jié)果結(jié)果分為2個部分1：說明部分（數(shù)聽說明、選項、模型說明…）2:結(jié)果序列部分10/10/42第42頁Result1第一部分：相關(guān)信息說明軟件信息：版本、權(quán)限等HMM文件名稱，查詢閾值等HMM文件一些描述信息10/10/43第43頁Result2.1HIT序列分值，E值，domain數(shù)目HITdomains分值、位置、E值等信息10/10/44第44頁Result2.2高分匹配序列比對10/10/45第45頁Result2.3全部序列HIT分值、E值圖形分布10/10/46第46頁Result2.4結(jié)果統(tǒng)計數(shù)據(jù)10/10/47第47頁ApplicationofHMM:pfam10/10/48第48頁ApplicationofHMMTMHMM:Predictionoftransmembranehelicesinproteinshttp://www.cbs.dtu.dk/services/TMHMM/10/10/49第49頁PFAMPfamisalargecollectionofproteinmultiplesequencealignments

andprofilehiddenMarkovmodels.PfamisavailableontheWorld

WideWebintheUKathttp://www.sanger.ac.uk/Software/Pfam/,

inSwedenathttp://www.cgb.ki.se/Pfam/,inFranceathttp://pfam.jouy.inra.fr/

andintheUSat/.10/10/50第50頁PfamIntroductionPfamisadatabaseofproteindomainfamilies.Pfamcontains

curatedmultiplesequencealignmentsforeachfamily,aswell

asprofilehiddenMarkovmodels(profileHMMs)forfindingthese

domainsinnewsequences.Pfamcontainsfunctionalannotation,

literaturereferencesanddatabaselinksforeachfamily.10/10/51第51頁PfamIntroductionVersion14.0,June,7459families

22336uniquePfam-AdomainarchitecturesTwobigfamiliesPfam-A:Ahigh-qualitymanualpartofPfam.Pfam-B:Low-qualityautomaticallygeneratedalignmentsofsequenceclustersinSWISSPROTandTrEMBLthatarenotmodelledinthecuratedpartofPfam.10/10/52第52頁PfamIntroductionThere

aretwomultiplealignmentsforeachPfamfamily,theseedalignment

thatcontainsarelativelysmallnumberofrepresentativemembers

ofthefamilyandthefullalignmentthatcontainsallmembers

inthedatabasethatcanbedetected.Allalignmentsusesequences

takenfrompfamseq,whichisanon-redundantproteinsetcomposed

ofSWISS-PROTandSP-TrEMBL.TheprofileHMMisbuiltfromthe

seedalignmentusingtheHMMERpackage,whichisthenusedtosearchthepfamseqsequencedatabase10/10/53第53頁PfamGoalsOneofthemaingoalsofPfamwastoaidthea