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

生物信息学第三章序列比对Ⅱ本章内容提要第一节：数学基础：概率及概率模型第二节：双序列比对算法的介绍Dotmatrix动态规划算法(Needleman-Wunsch,Smith-Waterman算法)FASTA和BLAST算法第三节：打分矩阵及其含义第四节：多序列比对第三节打分矩阵及其含义1，计分方法2，Dayhoff:PAM系列矩阵3，Henikoff:BLOSUM系列矩阵1，计分方法匹配计分：UM矩阵(Unitarymatrix)相同的氨基酸记1分，否则记0分。BLAST中核酸比对结构域性质计分：SGM矩阵(Structure-GeneticMatrix)主要根据氨基酸的结构和化学性质的相似程度来记分(如D和E，S和T，V和I有很高的相似性)，同时还考虑密码子之间相互转换的难易程度。可观测变换计分：PAM矩阵(PointAcceptedMutation)BLOSUM矩阵(BLOcksSUbstitutionMatrix)2，PAM系列矩阵MargaretDayhoff,1978;通过对物种进化的研究，根据一种氨基酸被另一种氨基酸替代的频度而提出的，最常用的是PAM250;Acceptedpointmutation(PAM):可接受的点突变，氨基酸的改变不显著影响蛋白质的功能；PAM矩阵71个蛋白质家族的1572种变化；序列相似性85%；功能同源的蛋白质通过中性进化，引入可接受的点突变；进化模型：A.基本假设：中性进化，Kimura,1968;B.进化的对称性:A-B=B-A;C.扩展性：通过对较短时间内氨基酸替代关系的计算来计算较长时间的氨基酸替代关系；PAM1矩阵两个蛋白质序列的~1%氨基酸发生变化；定义进化时间以氨基酸的变异比例为准，而不是时间；因为各个蛋白质家族进化的速度并不相等；PAM2=PAM1*PAM1PAM3=(PAM1)3PAM250=(PAM1)250PAMn矩阵的构建1.选取多个家族的相似性85%的保守序列；2.根据匹配计分进行多重比对(不含空位)；3.以比对结果构建进化树，反映氨基酸替换关系；4.计算每种氨基酸转换成其它氨基酸的次数；5.计算每种氨基酸突变率；6.计算每对氨基酸突变率，得到突变概率矩阵，将此矩阵自乘n次；7.将突变概率矩阵转化为PAMn矩阵。例6：PAM矩阵的构建已知3个蛋白质家族若干保守序列片段：家族一：FKILK，FKIKK，FFILL，FFIKL家族二：IIFFF，IIFIF，IKFFL，IKFIL家族三：KIFKK，KIFLK，KLFKL，KLFLL按Doyhoff方法构建PAM1与PAM2矩阵Step1：多重比对位置对齐，多重比对（不考虑空位）：统计每种氨基酸出现的频率；fi=氨基酸i的数目/总氨基酸数目fL=12/60=0.2..家族一家族二家族三FKILKIIFFFKIFKKFKIKKIIFIFKIFLKFFILLIKFFLKLFKLFFIKLIKFILKLFLLStep2：构建进化树最大简约法家族一:L和K间相互转换次数：N(LK)=3家族二，家族三…FKILKFKIKKFKIKKFFIKLFFILLFFIKL(LK)(KF)(LK)(LK)Step3：计算氨基酸间的转换次数计算每种氨基酸转换成其它氨基酸的次数。假设两种氨基酸间相互转换一样。e.g.N(LK)=3+0+3=6KFILK116F121I121L611Step4：计算各氨基酸相对突变率每种氨基酸相对突变率mii：第i种氨基酸；fi：每种氨基酸出现的频率；mK=8/(12×2×fK×100)=0.0125…1002iifim总替换数总共发生替换数氨基酸Step5：计算氨基酸i替换为j的突变率氨基酸i替换为j的突变率mije.g.mKK=1-mK=0.9875mKF=mF×1/4=0.001389…iiiiijmmjijjimmji1时，总共发生替换数氨基酸相互替换的次数与氨基酸时，Step5：氨基酸一步转移概率矩阵氨基酸突变概率——一步转移概率矩阵M1ij原氨基酸KFIL替换氨基酸K0.98750.0015630.0015630.009375F0.0013890.9944440.0027780.001389I0.0017860.0035710.9928570.001786L0.01250.0020830.0020830.983333Step6:计算PAM1计分矩阵由突变率mij计算计分矩阵中的分值rij：将rij=rji取平均值，再取整数；（按先前假设，rij=rji）rKK=10lg(mkk/fk)=5.6857≈6(rKF+rFK)/2=-22.833≈-23…)/lg(10iijijfmrStep6:PAM1计分矩阵结果三个家族序列片段得到的PAM1计分矩阵：KFILK6F-235I-22-196L-13-22-207Step7:计算PAM2计分矩阵将氨基酸突变概率矩阵自乘一次，得到两步转移概率矩阵M2ijM2ij=M1ij×M1ij三个家族序列片段得到的PAM2计分矩阵：KFILK6F-205I-19-166L-10-19-187PAM250矩阵PAM250:250%期望的突变；蛋白质序列仍然有15-30%左右的相似性；PAM250打分矩阵打分矩阵的使用PAM250:~15-30%的序列相似性；PAM120:~40%的序列相似性；PAM80:~50%PAM60:~60%如何选择最合适的矩阵？多种尝试…PAM矩阵的问题及改进1.PAM系列矩阵存在的问题：A.氨基酸的打分矩阵，不关心核酸；B.进化模型的构建需要系统发育树的分析，因此，成为一个循环论证的问题：序列比对矩阵构建打分进行新的序列比对；C.数据集很小；2.打分矩阵的改进A.选用大量的序列数据，构建PAM矩阵；B.BLOSUM系列矩阵;C.核酸的打分矩阵;3，BLOSUM矩阵最被广泛使用的氨基酸打分矩阵;根据蛋白质模块数据库BLOCKS中蛋白质序列的高度保守部分的比对而得到的，最常用的是BLOSUM62;BLOCK:蛋白质家族保守的一段氨基酸，无gap，一般几个至上百个氨基酸；Prosite家族：至少有一个BLOCK存在于该家族的所有蛋白质序列中；BLOSUM62:序列的平均相似性为62%的BLOCK构建的打分矩阵；BLOSUM62矩阵构建步骤：1.提取Prosite数据库中504个家族的2万多蛋白质序列，合并其中相似性≥62%的序列；2.统计各BLOCK的氨基酸对数量f；3.计算氨基酸对的出现频率q；4.计算每种氨基酸的期望频率p；5.计算氨基酸对出现的期望频率e；6.计算BLOSUM62矩阵分量rij)/(lg22eqrijBLOSUM62打分矩阵BLOSUM&PAM序列相似性与PAM及BLOSUM矩阵的大致对应关系：序列相似性%999080706050403020PAM数值11123385680112159246BLOSUM数值908062-45第四节，多序列比对不同物种中，许多基因的功能保守，序列相似性较高，通过多条序列的比较，发现保守与变异的部分；可构建HMM模型，搜索更多的同源序列；构建进化的树的必须步骤；比较基因组学研究；两类：全局或局部的多序列比对；全局性的多序列比对MadebyGENEDOC双序列比对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时间复杂度：O(n2)多序列比对：最优算法三条序列：时间复杂度：O(lmn)=O(n3)四条序列：时间复杂度：O(n4)，非多项式时间！多项式时间复杂度要求：≤O(n3)m条序列：时间复杂度：O(nm)，NPC问题！…动态规划算法：全空间动态规划算法：优化算法SequenceASequenceB搜索有限空间，类似于BLAST算法动态规划算法：Hyperlattice注意最优的多序列比对，其两两序列之间的比对不一定最优。最优的多序列比对非最优的双序列比对MSA程序MSA-MultipleSequenceAlignmentDavidLipman等，1989年初始开发；应用多维动态规划算法，得到最优的全局比对。工具资源：：打分方式多序列比对：方法改进1.渐进方法：progressivemethods代表：ClustalW/X,T-Coffee2.迭代方法：iterativemethods代表:PRRP,DIALIGN3.部分有向图算法：PartialOrderAlgorithm(POA)4.全局多序列比对的隐马尔科夫模型profileHMM5.整合算法：MUSCLE1.Progressivemethods(1)ClustalW/X(2)T-Coffee(1)ClustalW/X1.Clustal:1988年开发；2.ClustalW:1994年，JulieD.Thompson等人改进、发展；3.ClustalX:1997年，图形化软件；ClustalW/X：计算过程1.将所有序列两两比对，计算距离矩阵；2.构建邻接进化树(neighbor-joiningtree)/指导树(guidetree)；3.将距离最近的两条序列用动态规划的算法进行比对；4.“渐进”的加上其他的序列。两两比对，构建距离矩阵指导树的构建渐进比对ClustalW的打分原则每条序列的权值Score:BLOSUM62的分数ClustalX的使用1.FASTA序列格式，多序列：ClustalX的使用——导入序列文件执行比对文件导出多序列比对：结果处理BioEdit,GeneDoc等软件GeneDoc软件，导入.aln文件选择文件格式成功导入文件选择需要拷贝的行(2)T-Coffee1.采用Clustal程序计算两两序列之间的全局最优比对结果；2.采用LALIGN程序计算两两序列之间的局部最优比对的结果；3.设计加权系统，综合考虑以上两类结果的因素，构建指导库；4.最后，采用渐进式比对算法，得到最终的结果。同时进行全局和局部的双序列比对对以上打分的结果设计权重系统，找到序列中最保守的部分渐进方法的比对，基于上述计算的primarylibraryClustalW/X：存在的问题1.距离最近的，有两组序列AB和CD，哪组最先比对？两种方案：A.分别、同时比对。但是，是以AB为准，加入CD，然后再加上其他序列，还是CD为准？结果可能出入很大B.随机挑选一组作为基准2.当序列差异较大时，上述问题更加明显。例如1.三条序列：2.若Seq1,2先比对，再加入Seq3：3.Seq1,3先比对，再加入Seq2:4.Seq2,3先比对，再加入Seq1:Seq1:ARKCVSeq2:ARCVSeq3:AKCVARKCVAR-CVA-KCVARKCVA-RCVA-KCVARKCVAR-CVAK-CV2.迭代方法1.部分解决渐进算法存在的问题,主要是ClustalW/X存在的问题；2.PRRP3.DIALIGN(1)PRRP1.先用“渐进”算法进行多序列比对;2.基于多序列比对的结果构建进化树；3.重新计算序列之间的距离，再用“渐进”算法进行多序列比对；4.重复上述步骤，直到结果不再发生改变为止。(2)DIALIGN1.对所有序列进行两两之间的局部最优化的比对；2.找到所有能够匹配的部分M