生物信息学实验.ppt

《生物信息学实验.ppt》由会员分享，可在线阅读，更多相关《生物信息学实验.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、生物信息学实验 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望生物学中常用的统计模型生物学中常用的统计模型l Structured probability modelsMarkov modelsHidden markov modelslArtificial Neural Network(A.N.N)11/13/20222IntroductionHidden Markov Models(HMMs)最早是在上个世纪60年代末70年代初提出来的。进入80年代以后，逐渐被

2、利用在各个领域。11/13/20223IntroductionHidden Markov Models 作为一种强有力的统计学模型，主要被应用在一些连续行的或时间延续性的事件建模上语音识别系统。生物学中的DNA/protein序列的分析机器人的控制。文本文件的信息提取。11/13/20224HMM的优点的优点1，它的数学结构非常丰富，适用于各个领域的研究。2，在很多领域中，已经证明它的结果和实际符合的相当好。11/13/20225Probability Review11/13/20226独立事件概率独立事件概率l设想我们做一连串的实验，而每次实验所可能发生的结果定为 E1,E2,En,。（可能

3、是有限也可能是无限）。每一个结果 Ek，如果给定一个出现的可能性 pk（即概率），则某一特定样本之序列 Ej1 Ej2 Ejn出现的概率为 p(Ej1 Ej2 Ejn)=pj1 Pjn。11/13/20227马尔科夫链马尔科夫链l一般及常用的统计中，彼此相互独立大概是最有用的一个观念。用简单的术语來说，互相独立就是彼此毫不相干，一点牵涉都沒有。l但是实际生活中很多事件是相互关联的l不是互相独立也就是相互关联的意思，但是要怎样相关呢？如何在相关中作一些简单的分类呢？马尔科夫链就是要描述在相关这个概念中最简单的一种。但即使如此，有关马可夫链的理论已经相当丰富了。在概率理论中，它几乎占了绝大的部分。

4、11/13/20228马尔科夫链马尔科夫链l在马尔科夫链中考虑最简单的相关性。在在这种情况下，我们不能给任一个事件 Ej 一個概率 pj 但我们给一对事件(Ej,Ek)一個概率 pjk，这个时候 pjk 的解释是一种条件概率，就是假设在某次实验中 Ej 已经出现，而在下一次实验中 Ek 出现的概率。除了 pjk 之外，还需要知道第一次实验中 Ej 出現的機率 aj。有了这些资料后，一個样本序列 Ej0 Ej1 Ejn（也就是说第零次实验结果是Ej0，第一次一次是 Ej1第 n 次实验是 Ejn）的概率就很清楚的是 P(Ej0,Ej1,Ejn)=aj pj0j1 pj1j2 pjn-1jn。11

5、/13/20229隐马尔科夫模型隐马尔科夫模型l但是在大多数情况下我们所观察到的值并不是序列本身的元素。l即观察值不等于状态值。l故我们引入隐马尔科夫模型。11/13/202210定义定义一个HMM 是一个五元组：(X,O,A,B,)其中：X=q1,.qN：状态的有限集合 O=v1,.,vM：观察值的有限集合 A=aij，aij=p(Xt+1=qj|Xt=qi)：转移概率 B=bik，bik=p(Ot=vk|Xt=qi)：输出概率 =i，i=p(X1=qi)：初始状态分布11/13/202211假设假设对于一个随机事件，有一个观察值序列：O1,.,OT该事件隐含着一个状态序列：X1,.,XT假

6、设1：马尔可夫假设（状态构成一阶马尔可夫链）p(Xi|Xi-1X1)=p(Xi|Xi-1)假设2：不动性假设（状态与具体时间无关）p(Xi+1|Xi)=p(Xj+1|Xj)，对任意i,j成立假设3：输出独立性假设（输出仅与当前状态有关）p(O1,.,OT|X1,.,XT)=p(Ot|Xt)11/13/202212马尔科夫链马尔科夫链 Vs 隐马尔科夫模型隐马尔科夫模型 lMarkov chains have entirely observable states.However a“Hidden Markov Model”is a model of a Markov Source which a

7、dmits an element each time slot depending upon the state.The states are not directly observed 11/13/202213Problems令 =A,B,为给定HMM的参数，令 =O1,.,OT 为观察值序列，隐马尔可夫模型（HMM）的三个基本问题：1.评估问题：对于给定模型，求某个观察值序列的概率p(|)；forward algorithm2.解码问题：对于给定模型和观察值序列，求可能性最大的状态序列；viterbi algorithm3.学习问题：对于给定的一个观察值序列，调整参数，使得观察值出现的概率

8、p(|)最大。Forward-backward algorithm11/13/202214SolutionslEvaluation problem：forward algorithm定义向前变量采用动态规划算法，复杂度O(N2T)lDecoding problem：Viterbi algorithm采用动态规划算法，复杂度O(N2T)lLearning problem：forward-backward algorithmEM算法的一个特例，带隐变量的最大似然估计11/13/202215Struct HMMtypedef struct/*number of states;Q=1,2,.,N*/i

9、nt N;/*number of observation symbols;V=1,2,.,M*/int M;/*A1.N1.N.aij is the transition prob of going from state i *at time t to state j at time t+1*/double*A;/*B1.N1.M.bjk is the probability of observing symbol k in state j*/double*B;/*pi1.N pii is the initial state distribution.*/double*pi;HMM;11/13

10、/202216算法：向前算法（算法：向前算法（1）11/13/202217算法：向前算法（算法：向前算法（2）定义前向变量为HMM在时间t输出序列O1Ot，并且位于状态Si的概率：11/13/202218算法：向前算法（算法：向前算法（3）迭代公式为：结果为：11/13/202219Forward algorithm11/13/202220算法：向后算法（算法：向后算法（1）11/13/202221算法：算法：Viterbi算法（算法（1）lThe Viterbi algorithm is a dynamic programming algorithm that computes the mo

11、st likely state transition path given an observed sequence of symbols.It is actually very similar to the forward algorithm。11/13/202222Viterbi algorithm11/13/202223Viterbi in c/*1.Initialization*/for(i=1;i N;i+)delta1i=phmm-pii*(phmm-BiO1);psi1i=0;/*2.Recursion*/for(t=2;t=T;t+)for(j=1;j N;j+)maxval=

12、0.0;maxvalind=1;for(i=1;i N;i+)val=deltat-1i*(phmm-Aij);if(val maxval)maxval=val;maxvalind=i;deltatj=maxval*(phmm-BjOt);psitj=maxvalind;11/13/202224生物学中的数学模型生物学中的数学模型11/13/202225马氏链马氏链11/13/202226马氏链马氏链11/13/202227马氏链马氏链11/13/202228隐马可夫模型隐马可夫模型11/13/202229隐马可夫模型隐马可夫模型11/13/202230隐马可夫模型隐马可夫模型 profile

13、11/13/202231Related softwarelHMMERhttp:/hmmer.wustl.edu/lSAM(Sequence Alignment and Modeling System)http:/www.soe.ucsc.edu/lHMMproA windows version for HMM The Division of Biomedical Informatics at Cincinnati Childrens Hospital Medical Center lmetaMEME:A motif based Hidden Markov Model11/13/202232HM

14、MERlProfile hidden Markov models(profile HMMs)can be used to do sensitive database searching using statistical descriptions of a sequence familys consensus.HMMER is a freely distributable implementation of profile HMM software for protein sequence analysis.The current version is HMMER 2.3.2(3 Oct 20

15、03),containing minor bugfixes and updates for the May 2003 release of HMMER 2.3.11/13/202233HMMER11/13/202234How to create a HMM多序列比对多序列比对相关序列选取相关序列选取模型构建模型构建模型训练模型训练参数调整参数调整应用应用确立模型确立模型11/13/202235Example:1.Sequence selection选取相关的序列选取相关的序列11/13/2022362.AlignmentSave result as msf format多序列比对多序列比对11

16、/13/202237模型建立模型建立l3.Hmmbuildl4.Hmmtl5.Hmmcalibrate模型建立模型建立用相关序列对模型用相关序列对模型进行训练进行训练参数调整参数调整11/13/202238模型文件（模型文件（1）HMMER2.0 2.3.2NAME globins50LENG 162ALPH AminoRF noCS noMAP yesCOM ./hmmbuild globins.hmm globins50.msfNSEQ 50DATE Thu Sep 18 00:02:14 2008CKSUM 4694XT -8455 -4 -1000 -1000 -8455 -4 -84

17、55 -4NULT -4 -8455NULE 595 -1558 85 338 -294 453 -1158 197 249 902 -1085 -142 -21 -313 45 531 201 384 -1998 -64411/13/202239模型文件（模型文件（2）模型部分：HMM A C D E F G H I K L M N P Q R S T V W Y m-m m-i m-d i-m i-i d-m d-d b-m m-e -222 *-2807 1 -1412 -1712 -339 -321 -1729 113 -1457 261 -1493 -1591 1181 -1737

18、-32 -1359 -1788 77 -1353 2620 -2119 -1697 4 -149 -500 233 43 -381 399 106 -626 210 -466 -720 275 394 45 96 359 117 -369 -294 -249 -1909 -8804 -451 -894 -1115 -701 -1378 -110 *2 -1118 -1371 -1805 -1237 -1464 -2231 -889 2528 2067 -899 -510 -1267 -2325 -644 -266 -1422 -1057 -63 -1884 -1486 5 -149 -500

19、233 43 -381 399 106 -626 210 -466 -720 275 394 45 96 359 117 -369 -294 -249 -18 -6914 -7956 -894 -1115 -3550 -129 *11/13/2022406.未知序列的搜索查询未知序列的搜索查询lHmmsearch:search a sequence against the profile HMMl未知查询序列Artemia.falProfile HMM：Globin.hmmlCommand:hmmsearch globin.hmm Artemia.fa查询程序查询程序查询的未知序列查询的未知序

20、列文件文件所用模型所用模型查询命令查询命令11/13/202241查询结果查询结果l结果分为2个部分l1：说明部分（数据说明、选项、模型说明）l2:结果序列部分11/13/202242Result1第一部分：相关信息说明第一部分：相关信息说明软件信息：版本、权限等软件信息：版本、权限等HMM文件名称，查询的阈文件名称，查询的阈值等值等HMM文件的一些描述信息11/13/202243Result 2.1HIT序列分值，序列分值，E值，值，domain数目数目HIT domains分值、位置、分值、位置、E值等信息值等信息11/13/202244Result 2.2高分匹配序列比对高分匹配序列比对

21、11/13/202245Result 2.3所有序列所有序列HIT分值、分值、E值的值的图形分布图形分布11/13/202246Result 2.4结果统计数据结果统计数据11/13/202247Application of HMM:pfam11/13/202248Application of HMMlTMHMM:Prediction of transmembrane helices in proteinslhttp:/www.cbs.dtu.dk/services/TMHMM/11/13/202249PFAMPfam is a large collection of protein mult

22、iple sequence alignments and profile hidden Markov models.Pfam is available on the World Wide Web in the UK at http:/www.sanger.ac.uk/Software/Pfam/,in Sweden at http:/www.cgb.ki.se/Pfam/,in France at http:/pfam.jouy.inra.fr/and in the US at http:/pfam.wustl.edu/.11/13/202250Pfam IntroductionlPfam i

23、s a database of protein domain families.Pfam contains curated multiple sequence alignments for each family,as well as profile hidden Markov models(profile HMMs)for finding these domains in new sequences.lPfam contains functional annotation,literature references and database links for each family.11/

24、13/202251Pfam IntroductionlVersion 14.0,June 2004,7459 families22336 unique Pfam-A domain architectureslTwo big familieslPfam-A:A high-quality manual part of Pfam.lPfam-B:Low-quality automatically generated alignments of sequence clusters in SWISSPROT and TrEMBL that are not modelled in the curated

25、part of Pfam.11/13/202252Pfam IntroductionlThere are two multiple alignments for each Pfam family,the seed alignment that contains a relatively small number of representative members of the family and the full alignment that contains all members in the database that can be detected.All alignments us

26、e sequences taken from pfamseq,which is a non-redundant protein set composed of SWISS-PROT and SP-TrEMBL.The profile HMM is built from the seed alignment using the HMMER package,which is then used to search the pfamseq sequence database11/13/202253Pfam GoalslOne of the main goals of Pfam was to aid

27、the annotation of the Caenorhabditis elegans genome.Traditional approaches to large scale sequence annotation use a pairwise sequence comparison method such as BLAST to find similarity to proteins of known function.Annotations are then transferred from the protein of known function to the predicted

28、protein.The pairwise similarity search does not give a clear indication of the domain structure of the proteins.Mistakes in annotation can result from not considering the domain organisation of proteins.For example a protein may be misannotated as an enzyme when the similarity is only to a regulator

29、y domain.Since its inception,Pfam has been developed to provide broad support for automated protein sequence classification and annotation.During the last year there have been significant changes and extensions to Pfam,which further this role.11/13/202254蛋白二级结构分析蛋白二级结构分析lThe PredictProtein serverhttp:/blast.ym.edu.tw/tools/predictprotein/predictprotein.html 11/13/202255