中国科技大学课件系列：《生物信息学》04学习资料

生物(shēngwù)信息学第三章序列(xùliè)比对Ⅱ第一页，共72页。本章(běnzhānɡ)内容提要第一节：数学基础：概率及概率模型第二节：双序列比对算法的介绍Dotmatrix动态(dòngtài)规划算法(Needleman-Wunsch,Smith-Waterman算法)FASTA和BLAST算法第三节：打分矩阵及其含义第四节：多序列比对第二页，共72页。第三节打分矩阵(jǔzhèn)及其含义1，计分(jìfēn)方法2，Dayhoff:PAM系列矩阵3，Henikoff:BLOSUM系列矩阵第三页，共72页。1，计分(jìfēn)方法匹配计分：UM矩阵(Unitarymatrix) 相同的氨基酸记1分，否则(fǒuzé)记0分。BLAST中核酸比对结构域性质计分：SGM矩阵(Structure-GeneticMatrix) 主要根据氨基酸的结构和化学性质的相似程度来记分(如D和E，S和T，V和I有很高的相似性)，同时还考虑密码子之间相互转换的难易程度。可观测变换计分：PAM矩阵(PointAcceptedMutation)BLOSUM矩阵(BLOcksSUbstitutionMatrix)第四页，共72页。2，PAM系列(xìliè)矩阵MargaretDayhoff,1978;通过对物种进化的研究，根据一种氨基酸被另一种氨基酸替代(tìdài)的频度而提出的，最常用的是PAM250;Acceptedpointmutation(PAM):可接受的点突变，氨基酸的改变不显著影响蛋白质的功能；第五页，共72页。PAM矩阵(jǔzhèn)71个蛋白质家族的1572种变化(biànhuà)；序列相似性>85%；功能同源的蛋白质通过中性进化(jìnhuà)，引入可接受的点突变；进化(jìnhuà)模型：A.基本假设：中性进化(jìnhuà)，Kimura,1968;B.进化(jìnhuà)的对称性:A->B=B->A;C.扩展性：通过对较短时间内氨基酸替代关系的计算来计算较长时间的氨基酸替代关系；第六页，共72页。PAM1矩阵(jǔzhèn)两个蛋白质序列(xùliè)的~1%氨基酸发生变化；定义进化时间以氨基酸的变异比例为准，而不是时间；因为各个蛋白质家族进化的速度并不相等；PAM2=PAM1*PAM1PAM3=(PAM1)3PAM250=(PAM1)250第七页，共72页。PAMn矩阵(jǔzhèn)的构建选取多个家族的相似性>85%的保守序列；根据匹配计分进行多重比对(不含空位)；以比对结果构建进化树，反映氨基酸替换(tìhuàn)关系；计算每种氨基酸转换成其它氨基酸的次数；计算每种氨基酸突变率；计算每对氨基酸突变率，得到突变概率矩阵，将此矩阵自乘n次；将突变概率矩阵转化为PAMn矩阵。第八页，共72页。例6：PAM矩阵(jǔzhèn)的构建已知3个蛋白质家族若干保守序列片段(piànduàn)：家族一：FKILK，FKIKK，FFILL，FFIKL家族二：IIFFF，IIFIF，IKFFL，IKFIL家族三：KIFKK，KIFLK，KLFKL，KLFLL按Doyhoff方法构建PAM1与PAM2矩阵第九页，共72页。Step1：多重比对位置对齐，多重比对（不考虑空位）：统计(tǒngjì)每种氨基酸出现的频率； fi=氨基酸i的数目/总氨基酸数目fL=12/60=0.2..家族一家族二家族三FKILKIIFFFKIFKKFKIKKIIFIFKIFLKFFILLIKFFLKLFKLFFIKLIKFILKLFLL第十页，共72页。Step2：构建(ɡòujiàn)进化树最大简约法家族一:L和K间相互(xiānghù)转换次数：N(LK)=3家族二，家族三…FKILKFKIKKFKIKKFFIKLFFILLFFIKL(LK)(KF)(LK)(LK)第十一页，共72页。Step3：计算氨基酸间的转换(zhuǎnhuàn)次数计算每种氨基酸转换成其它氨基酸的次数(cìshù)。假设两种氨基酸间相互转换一样。e.g.N(LK)=3+0+3=6KFILK116F121I121L611第十二页，共72页。Step4：计算(jìsuàn)各氨基酸相对突变率每种氨基酸相对(xiāngduì)突变率mii：第i种氨基酸；fi：每种氨基酸出现的频率；mK=8/(12×2×fK×100)=0.0125…第十三页，共72页。Step5：计算(jìsuàn)氨基酸i替换为j的突变率氨基酸i替换(tìhuàn)为j的突变率mije.g.mKK=1-mK=0.9875mKF=mF×1/4=0.001389…第十四页，共72页。Step5：氨基酸一步(yībù)转移概率矩阵氨基酸突变概率——一步转移(zhuǎnyí)概率矩阵M1ij原氨基酸KFIL替换氨基酸K0.98750.0015630.0015630.009375F0.0013890.9944440.0027780.001389I0.0017860.0035710.9928570.001786L0.01250.0020830.0020830.983333第十五页，共72页。Step6:计算(jìsuàn)PAM1计分矩阵由突变率mij计算计分(jìfēn)矩阵中的分值rij：将rij=rji取平均值，再取整数； （按先前假设，rij=rji）rKK=10lg(mkk/fk)=5.6857≈6(rKF+rFK)/2=-22.833≈-23…第十六页，共72页。Step6:PAM1计分(jìfēn)矩阵结果三个家族序列片段得到(dédào)的PAM1计分矩阵：KFILK6F-235I-22-196L-13-22-207第十七页，共72页。Step7:计算(jìsuàn)PAM2计分矩阵将氨基酸突变(tūbiàn)概率矩阵自乘一次，得到两步转移概率矩阵M2ijM2ij=M1ij×M1ij三个家族序列片段得到的PAM2计分矩阵：KFILK6F-205I-19-166L-10-19-187第十八页，共72页。PAM250矩阵(jǔzhèn)PAM250:250%期望的突变(tūbiàn)；蛋白质序列仍然有15-30%左右的相似性；第十九页，共72页。PAM250打分(dǎfēn)矩阵第二十页，共72页。打分(dǎfēn)矩阵的使用PAM250:~15-30%的序列(xùliè)相似性；PAM120:~40%的序列(xùliè)相似性；PAM80:~50%PAM60:~60%如何选择最合适的矩阵？多种尝试…第二十一页，共72页。PAM矩阵(jǔzhèn)的问题及改进1.PAM系列矩阵存在的问题：A.氨基酸的打分矩阵，不关心(guān〃xīn)核酸；B.进化模型的构建需要系统发育树的分析，因此，成为一个循环论证的问题：序列比对矩阵构建打分进行新的序列比对；C.数据集很小；2.打分矩阵的改进A.选用大量的序列数据，构建PAM矩阵；B.BLOSUM系列矩阵;C.核酸的打分矩阵;第二十二页，共72页。3，BLOSUM矩阵(jǔzhèn)最被广泛使用的氨基酸打分矩阵;根据蛋白质模块数据库BLOCKS中蛋白质序列的高度保守部分(bùfen)的比对而得到的，最常用的是BLOSUM62;BLOCK:蛋白质家族保守的一段氨基酸，无gap，一般几个至上百个氨基酸；Prosite家族：至少有一个BLOCK存在于该家族的所有蛋白质序列中；BLOSUM62:序列的平均相似性为62%的BLOCK构建的打分矩阵；第二十三页，共72页。BLOSUM62矩阵(jǔzhèn)构建步骤：提取Prosite数据库中504个家族的2万多蛋白质序列，合并(hébìng)其中相似性≥62%的序列；统计各BLOCK的氨基酸对数量f；计算氨基酸对的出现频率q；计算每种氨基酸的期望频率p；计算氨基酸对出现的期望频率e；计算BLOSUM62矩阵分量rij第二十四页，共72页。BLOSUM62打分(dǎfēn)矩阵第二十五页，共72页。BLOSUM&PAM序列(xùliè)相似性与PAM及BLOSUM矩阵的大致对应关系：序列相似性%999080706050403020PAM数值11123385680112159246BLOSUM数值908062-45第二十六页，共72页。第四节，多序列(xùliè)比对不同物种中，许多基因的功能保守，序列相似性较高，通过多条序列的比较，发现保守与变异(biànyì)的部分；可构建HMM模型，搜索更多的同源序列；构建进化的树的必须步骤；比较基因组学研究；两类：全局或局部的多序列比对；第二十七页，共72页。全局性的多序列(xùliè)比对MadebyGENEDOC第二十八页，共72页。双序列(xùliè)比对GapVDSCYGap0-11-22-33-44-55V-114-7-18-29-40E-22-76-5-16-27S-33-18-510-1-12L-44-29-16-19-3C-55-40-27-1287Y-66-51-38-23-31542时间(shíjiān)复杂度：O(n2)第二十九页，共72页。多序列(xùliè)比对：最优算法三条(sāntiáo)序列：时间复杂度：O(lmn)=O(n3)四条序列(xùliè)：时间复杂度：O(n4)，非多项式时间！多项式时间复杂度要求：≤O(n3)m条序列：时间复杂度：O(nm)，NPC问题！…第三十页，共72页。动态规划(guīhuà)算法：全空间第三十一页，共72页。动态(dòngtài)规划算法：优化算法SequenceASequenceBSequenceC

搜索有限空间，类似于BLAST算法第三十二页，共72页。动态规划(guīhuà)算法：Hyperlattice第三十三页，共72页。注意(zhùyì)最优的多序列(xùliè)比对，其两两序列(xùliè)之间的比对不一定最优。最优的多序列(xùliè)比对非最优的双序列比对第三十四页，共72页。MSA程序(chéngxù)MSA-MultipleSequenceAlignmentDavidLipman等，1989年初始开发；应用(yìngyòng)多维动态规划算法，得到最优的全局比对。工具资源：/CBBresearch/Schaffer/msa.html/general/software/packages/msa/manual/manual.php第三十五页，共72页。MSA：

打分(dǎfēn)方式第三十六页，共72页。多序列比对：方法(fāngfǎ)改进1.渐进方法：progressivemethods代表：ClustalW/X,T-Coffee2.迭代方法：iterativemethods代表:PRRP,DIALIGN3.部分有向图算法(suànfǎ)：PartialOrderAlgorithm(POA)4.全局多序列比对的隐马尔科夫模型profileHMM5.整合算法(suànfǎ)：MUSCLE第三十七页，共72页。1.Progressivemethods(1)ClustalW/X(2)T-Coffee第三十八页，共72页。(1)ClustalW/X1.Clustal:1988年开发；2.ClustalW:1994年，JulieD.Thompson等人改进(gǎijìn)、发展；3.ClustalX:1997年，图形化软件；第三十九页，共72页。ClustalW/X：计算(jìsuàn)过程1.将所有(suǒyǒu)序列两两比对，计算距离矩阵；2.构建邻接进化树(neighbor-joiningtree)/指导树(guidetree)；3.将距离最近的两条序列用动态规划的算法进行比对；4.“渐进”的加上其他的序列。第四十页，共72页。两两比对，构建(ɡòujiàn)距离矩阵指导(zhǐdǎo)树的构建渐进(jiànjìn)比对第四十一页，共72页。ClustalW的打分(dǎfēn)原则每条序列(xùliè)的权值Score:BLOSUM62的分数(fēnshù)第四十二页，共72页。ClustalX的使用(shǐyòng)1.FASTA序列(xùliè)格式，多序列(xùliè)：第四十三页，共72页。ClustalX的使用

——导入序列(xùliè)文件第四十四页，共72页。执行(zhíxíng)比对第四十五页，共72页。文件(wénjiàn)导出第四十六页，共72页。多序列(xùliè)比对：结果处理BioEdit,GeneDoc等软件(ruǎnjiàn)GeneDoc软件(ruǎnjiàn)，导入.aln文件第四十七页，共72页。选择(xuǎnzé)文件格式第四十八页，共72页。成功(chénggōng)导入文件第四十九页，共72页。选择需要(xūyào)拷贝的行第五十页，共72页。(2)T-Coffee1.采用Clustal程序计算两两序列之间的全局最优比对结果；2.采用LALIGN程序计算两两序列之间的局部最优比对的结果；3.设计加权系统，综合考虑以上两类结果的因素，构建指导库；4.最后(zuìhòu)，采用渐进式比对算法，得到最终的结果。第五十一页，共72页。同时进行(jìnxíng)全局和局部的双序列比对对以上打分的结果设计(shèjì)权重系统，找到序列中最保守的部分渐进方法的比对，基于(jīyú)上述计算的primarylibrary第五十二页，共72页。ClustalW/X：存在(cúnzài)的问题1.距离最近的，有两组序列AB和CD，哪组最先比对？两种方案：A.分别、同时比对。但是，是以AB为准，加入(jiārù)CD，然后再加上其他序列，还是CD为准？结果可能出入很大B.随机挑选一组作为基准2.当序列差异较大时，上述问题更加明显。第五十三页，共72页。例如(lìrú)1.三条(sāntiáo)序列：2.若Seq1,2先比对，再加入Seq3：3.Seq1,3先比对，再加入Seq2:4.Seq2,3先比对，再加入Seq1:Seq1:ARKCVSeq2:ARCVSeq3:AKCVARKCVAR-CVA-KCVARKCVA-RCVA-KCVARKCVAR-CVAK-CV第五十四页，共72页。2.迭代(diédài)方法1.部分解决(jiějué)渐进算法存在的问题,主要是ClustalW/X存在的问题；2.PRRP3.DIALIGN第五十五页，共72页。(1)PRRP1.先用“渐进”算法进行多序列比对;2.基于多序列比对的结果构建进化树；3.重新计算序列之间的距离，再用“渐进”算法进行多序列比对；4.重复(chóngfù)上述步骤，直到结果不再发生改变为止。第五十六页，共72页。(2)DIALIGN1.对所有序列进行两两之间的局部最优化的比对；2.找到所有能够匹配的部分M1；将重叠的、前后连续(consistency)的匹配部分连接起来(diagonals)，为M2；3.将剩下(shènɡxià)的未比对的序列重新比对，再发现能够匹配的部分，构成新M1，将consistency部分构成M2；4.重复上述步骤，直到结果收敛。第五十七页，共72页。DIALIGN:算法(suànfǎ)流程第五十八页，共72页。3.部分(bùfen)有向图算法第五十九页，共72页。第六十页，共72页。激酶(jīméi)的多序列比对第六十一页，共72页。4.隐马尔科夫模型(móxíng):ProbCons主要(zhǔyào)改进：1.所有序列的两两比对，通过profileHMM的方法进行双序列比对；2.将渐进算法与迭代算法整合；3.目前，性能最优。第六十二页，共72页。5.整合(zhěnɡhé)算法MUSCLE算法分为三个部分，每个部分相对独立；1.Draftprogressive:(1)对两条序列，计算距离采用(cǎiyòng)k-mer的思想；(2)用UPGMA算法构建引导树；