数学模型64隐马氏模型应用

1、6.4 隐马氏模型应用基因序列CpG岛识别本ppt修改自网上资料http：//moshep/Projects/ProjectPresentations2003_2/HMM/CpG_Islands_HMM_final.ppt什么是CpG岛？CG-poor regions: P(CG) 0.07!CG-rich region: P(CG) 0.25Gene coding regionPromoter regionCpG岛Away from gene regions: The C in CG pairs is usually methylated Methyla

2、tion inhibits gene transcription These CGs tend to mutate to TGNear promoter and coding regions: Methylation is suppressed: CGs remain CGs Makes transcription easier!CpG岛的生物学意义CpG-rich regions are associated with geneswhich are frequently transcribed.Helps to understand gene expression related to lo

3、cation in genome.HMM对于CpG岛识别的意义Q: Why an HMM?It can answer the questions: Short sequence: does it come from a CpG island or not? Long sequence: where are the CpG islands?So, whats a good m? Well, we need states for ISLAND bases andNON-ISLAND bases HMM模型框架A+P(A) = 1C+P(C) = 1CpG NON-Island (-)STARTEN

4、DA-P(A) = 1C-P(C) = 1T+P(T) = 1G+P(G) = 1STARTENDCpG Island (+)G-P(G) = 1T-P(T) = 1HMM模型框架CpG IslandA+C+G+P(G) = 1T+P(T) = 1P(A) = 1P(C) = 1STARTENDA-P(A) = 1C-P(C) = 1G-P(G) = 1T-P(T) = 1CpG NON-IslandHMM示意Visible:CTAGCpG IslandHidden:A+C+G+T+STARTENDA-C-G-T-CpG NON-IslandHMM训练问题CG-RICHsequencesAAT

5、AGAGAGGTTCGACTCTG CATTTCCCAAATACGTAATGCT TACGGTACACGACCCAAGCTC TCTGCTTGAATCCCAAATCTG AGCGGACAGATGAGGGGGC GCAGAGGAAAAACAGGTTTT GGACCCTACATAAANAGAGA GGTTCGTAAATAGAGACG-POORsequencesGGTTCGACTCTGCATTTCCCA AATACGTAATGCTTACGGTTA AATAGAGAGGTTCGACTCTG CATTTCCCAAATACGTAATGCT TACGGTACACGACCCAAGCTC TCTGCTTGTAA

6、CTTGTTTTNG TCGCAGCTGGTCTTGCCTTTG CTGGGGCTGCTGAHOW?ML or Forward/ Backward algorithmA+C+G+T+A-C-G-T-A+C+G+T+iA-C-G-T-0.17 0.26 0.42 0.11 0.01 0.01 0.01 0.010.16 0.36 0.26 0.18 0.01 0.01 0.01 0.010.15 0.33 0.37 0.11 0.01 0.01 0.01 0.010.07 0.35 0.37 0.17 0.01 0.01 0.01 0.010.01 0.01 0.01 0.01 0.29 0.2

7、 0.27 0.20.01 0.01 0.01 0.01 0.31 0.29 0.07 0.290.01 0.01 0.01 0.01 0.24 0.23 0.29 0.20.01 0.01 0.01 0.01 0.17 0.23 0.28 0.28HMM解码问题Viterbi AlgorithmDecoding- Meaning of observation sequence by looking at the underlying states.Hidden states A+,C+,G+,T+,A-,C-,G-,T- Observation sequence CGCGAState seq

8、uences C+,G+,C+,G+,A+ oror C+,G-,C+,G-,A+Most Probable Path C+,G+,C+,G+,A+C-,G-,C-,G-,A-HMM解码问题Viterbi AlgorithmHidden Markov m: S, akl, , el(x).Observed symbol sequence E = x1,.,xn.Find - Most probable path of states that resulted in symbol sequence ELet vk(i) be the partial probability of the most

9、 probable path of the symbol sequence x1, x2, ., xi ending in state k. Then:v l(i + 1) =e l(xi+1)max(vk(i)akl)HMM解码问题A+A+A+A+A+C+C+C+C+C+G+G+G+G+G+T+T+T+T+T+A-A-A-A-A-C-C-C-C-C-G-G-G-G-G-T-T-T-T-T-AGCGCHMM基因识别应用GENSCAN (Burge 1997)FGENESH (Solovyev 1997)HMMgene (Krogh 1997)GENIE (Kulp 1996)GENMARK (

10、Borodovsky & McIninch 1993) VEIL (Henderson, Salzberg, & Fasman 1997)参考文献ReferencesR.Dubin,S.Eddy, A.Krogh, and G. Mitchison. "Biologiclal Sequence Analysis: Probablisticms of Proteins and nucleic acids. Cambridge University Press, 1998. chapters 3and 5.A.Krogh,M.Brown,I.Saira Mian,Kimmen Sjolander and David Haussler "Hidden MarkovMs in Computational Biology Appications to Protein Ming J.Mol Biol. (1994)253, 1501-