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

1、生物信息学,第三章 序列比对 ,本章内容提要,第一节：数学基础：概率及概率模型 第二节：双序列比对算法的介绍 Dot matrix 动态规划算法 (Needleman-Wunsch, Smith-Waterman算法) FASTA和BLAST算法 第三节：打分矩阵及其含义 第四节：多序列比对,第三节 打分矩阵及其含义,1，计分方法 2，Dayhoff: PAM系列矩阵 3，Henikoff: BLOSUM系列矩阵,1， 计分方法,匹配计分： UM矩阵(Unitary matrix) 相同的氨基酸记1分，否则记0分。 BLAST中核酸比对 结构域性质计分： SGM矩阵(Structure-Gen

2、etic Matrix) 主要根据氨基酸的结构和化学性质的相似程度来记分(如D和E，S和T，V和I有很高的相似性)，同时还考虑密码子之间相互转换的难易程度。 可观测变换计分： PAM矩阵 (Point Accepted Mutation) BLOSUM矩阵 (BLOcks SUbstitution Matrix),2， PAM系列矩阵,Margaret Dayhoff, 1978; 通过对物种进化的研究，根据一种氨基酸被另一种氨基酸替代的频度而提出的，最常用的是PAM250; Accepted point mutation (PAM): 可接受的点突变，氨基酸的改变不显著影响蛋白质的功能；,P

3、AM矩阵,71个蛋白质家族的1572种变化； 序列相似性 85%；,功能同源的蛋白质 通过中性进化，引入可接受的点突变； 进化模型： A. 基本假设：中性进化，Kimura,1968; B. 进化的对称性: A-B = B-A; C. 扩展性：通过对较短时间内氨基酸替代关系的计算来计算较长时间的氨基酸替代关系；,PAM1矩阵,两个蛋白质序列的1%氨基酸发生变化； 定义进化时间以氨基酸的变异比例为准，而不是时间；因为各个蛋白质家族进化的速度并不相等； PAM2 = PAM1*PAM1 PAM3 = (PAM1)3 PAM250= (PAM1)250,PAMn矩阵的构建,选取多个家族的相似性85%

4、的保守序列； 根据匹配计分进行多重比对(不含空位)； 以比对结果构建进化树，反映氨基酸替换关系； 计算每种氨基酸转换成其它氨基酸的次数； 计算每种氨基酸突变率； 计算每对氨基酸突变率，得到突变概率矩阵，将此矩阵自乘n次； 将突变概率矩阵转化为PAMn矩阵。,例6：PAM矩阵的构建,已知3个蛋白质家族若干保守序列片段： 家族一：FKILK，FKIKK，FFILL，FFIKL 家族二：IIFFF， IIFIF ， IKFFL ， IKFIL 家族三： KIFKK，KIFLK，KLFKL，KLFLL 按Doyhoff方法构建PAM1与PAM2矩阵,Step1：多重比对,位置对齐，多重比对（不考虑空位

5、）： 统计每种氨基酸出现的频率； fi = 氨基酸i的数目/总氨基酸数目 fL = 12/60 = 0.2 .,Step2：构建进化树,最大简约法 家族一: L和K间相互转换次数：N(LK) = 3 家族二，家族三 ,Step3：计算氨基酸间的转换次数,计算每种氨基酸转换成其它氨基酸的次数。 假设两种氨基酸间相互转换一样。 e.g. N(LK)= 3 + 0 + 3 = 6,Step4：计算各氨基酸相对突变率,每种氨基酸相对突变率mi i：第i种氨基酸； fi ：每种氨基酸出现的频率； mK = 8/(122 fK 100) = 0.0125 ,Step5：计算氨基酸i替换为j的突变率,氨基酸

6、i替换为j的突变率mij e.g. mKK = 1- mK = 0.9875 mKF = mF 1/4 = 0.001389 ,Step5：氨基酸一步转移概率矩阵,氨基酸突变概率一步转移概率矩阵M1ij,Step6: 计算PAM1计分矩阵,由突变率mij计算计分矩阵中的分值rij： 将rij = rji取平均值，再取整数； （按先前假设， rij = rji） rKK = 10lg(mkk/ fk) = 5.6857 6 (rKF + rFK )/2 = -22.833 -23 ,Step6: PAM1计分矩阵结果,三个家族序列片段得到的PAM1计分矩阵：,Step7: 计算PAM2计分矩阵,

7、将氨基酸突变概率矩阵自乘一次，得到两步转移概率矩阵M2ij M2ij = M1ij M1ij 三个家族序列片段得到的PAM2计分矩阵：,PAM250矩阵,PAM250: 250%期望的突变； 蛋白质序列仍然有15-30%左右的相似性；,PAM250打分矩阵,打分矩阵的使用,PAM250: 15-30%的序列相似性； PAM120: 40%的序列相似性； PAM80: 50% PAM60: 60% 如何选择最合适的矩阵？ 多种尝试,PAM矩阵的问题及改进,1. PAM系列矩阵存在的问题： A. 氨基酸的打分矩阵，不关心核酸； B. 进化模型的构建需要系统发育树的分析，因此，成为一个循环论证的问题

8、：序列比对矩阵构建打分进行新的序列比对； C. 数据集很小； 2. 打分矩阵的改进 A. 选用大量的序列数据，构建PAM矩阵； B. BLOSUM系列矩阵; C. 核酸的打分矩阵;,3， BLOSUM矩阵,最被广泛使用的氨基酸打分矩阵; 根据蛋白质模块数据库BLOCKS中蛋白质序列的高度保守部分的比对而得到的，最常用的是BLOSUM62; BLOCK: 蛋白质家族保守的一段氨基酸，无gap，一般几个至上百个氨基酸； Prosite家族：至少有一个BLOCK存在于该家族的所有蛋白质序列中； BLOSUM62: 序列的平均相似性为62%的BLOCK构建的打分矩阵；,BLOSUM62矩阵构建步骤：,

9、提取Prosite数据库中504个家族的2万多蛋白质序列，合并其中相似性62%的序列； 统计各BLOCK的氨基酸对数量f； 计算氨基酸对的出现频率q； 计算每种氨基酸的期望频率p； 计算氨基酸对出现的期望频率e； 计算BLOSUM62矩阵分量rij,BLOSUM62打分矩阵,BLOSUM 2. 基于多序列比对的结果构建进化树； 3. 重新计算序列之间的距离，再用“渐进”算法进行多序列比对； 4. 重复上述步骤，直到结果不再发生改变为止。,(2) DIALIGN,1. 对所有序列进行两两之间的局部最优化的比对； 2. 找到所有能够匹配的部分M1；将重叠的、前后连续(consistency)的匹配

10、部分连接起来(diagonals)，为M2； 3. 将剩下的未比对的序列重新比对，再发现能够匹配的部分，构成新M1，将consistency部分构成M2； 4. 重复上述步骤，直到结果收敛。,DIALIGN: 算法流程,3. 部分有向图算法,激酶的多序列比对,4. 隐马尔科夫模型: ProbCons,主要改进： 1. 所有序列的两两比对，通过profile HMM的方法进行双序列比对； 2. 将渐进算法与迭代算法整合； 3. 目前，性能最优。,5. 整合算法MUSCLE,算法分为三个部分，每个部分相对独立； 1. Draft progressive: (1) 对两条序列，计算距离采用k-mer

11、的思想； (2) 用UPGMA算法构建引导树； (3) 使用渐进算法进行多序列比对； 优点：两条序列之间的距离不采用动态规划算法进行比对，节省时间。,MUSCLE,2. Improved progressive: (1)基于k-mer得到的树可能会产生次优结果，因此，采用Kimura距离的方法对k-mer产生的树重新计算距离矩阵； (2)重新用UPGMA构建进化树； (3)使用渐进算法进行多序列比对；,3. Refinement: (1)随机从进化树上挑出一条边，删除； (2)得到两组树，对每组树，计算profile； (3)将两组profile进行比对； (4)如果最终得分提高，保留结果，否则丢弃。,MUSCLE,MUSCLE的算法流程,MUSCLE: 使用指南,MUSCLE的使用,多序列比对：性能检验,1. BAliBASE：基于蛋白质结构，将同一家族的蛋白质序列进行多序列比较。 2. 检验多序列比对工具的性能：是否能够很好的重复BAliBAS