中国科技大学课件系列：生物信息学幻灯片.ppt

生物信息学,第三章 序列比对 Ⅱ,本章内容提要,第一节：数学基础：概率及概率模型 第二节：双序列比对算法的介绍 Dot matrix 动态规划算法 (Needleman-Wunsch, Smith-Waterman算法) FASTA和BLAST算法 第三节：打分矩阵及其含义 第四节：多序列比对,第三节 打分矩阵及其含义,1，计分方法 2，Dayhoff: PAM系列矩阵 3，Henikoff: BLOSUM系列矩阵,1， 计分方法,匹配计分： UM矩阵(Unitary matrix) 相同的氨基酸记1分，否则记0分 BLAST中核酸比对 结构域性质计分： SGM矩阵(Structure-Genetic 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): 可接受的点突变，氨基酸的改变不显著影响蛋白质的功能；,PAM矩阵,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%的保守序列； 根据匹配计分进行多重比对(不含空位)； 以比对结果构建进化树，反映氨基酸替换关系； 计算每种氨基酸转换成其它氨基酸的次数； 计算每种氨基酸突变率； 计算每对氨基酸突变率，得到突变概率矩阵，将此矩阵自乘n次； 将突变概率矩阵转化为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 ,Step2：构建进化树,最大简约法 家族一: L和K间相互转换次数：N(LK) = 3 家族二，家族三 …,Step3：计算氨基酸间的转换次数,计算每种氨基酸转换成其它氨基酸的次数 假设两种氨基酸间相互转换一样 e.g. N(LK)= 3 + 0 + 3 = 6,Step4：计算各氨基酸相对突变率,每种氨基酸相对突变率mi i：第i种氨基酸； fi ：每种氨基酸出现的频率； mK = 8/(12×2× fK ×100) = 0.0125 …,Step5：计算氨基酸i替换为j的突变率,氨基酸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计分矩阵,将氨基酸突变概率矩阵自乘一次，得到两步转移概率矩阵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. 进化模型的构建需要系统发育树的分析，因此，成为一个循环论证的问题：序列比对矩阵构建打分进行新的序列比对； C. 数据集很小； 2. 打分矩阵的改进 A. 选用大量的序列数据，构建PAM矩阵； B. BLOSUM系列矩阵; C. 核酸的打分矩阵;,3， BLOSUM矩阵,最被广泛使用的氨基酸打分矩阵; 根据蛋白质模块数据库BLOCKS中蛋白质序列的高度保守部分的比对而得到的，最常用的是BLOSUM62; BLOCK: 蛋白质家族保守的一段氨基酸，无gap，一般几个至上百个氨基酸； Prosite家族：至少有一个BLOCK存在于该家族的所有蛋白质序列中； BLOSUM62: 序列的平均相似性为62%的BLOCK构建的打分矩阵；,BLOSUM62矩阵构建步骤：,提取Prosite数据库中504个家族的2万多蛋白质序列，合并其中相似性≥62%的序列； 统计各BLOCK的氨基酸对数量f； 计算氨基酸对的出现频率q； 计算每种氨基酸的期望频率p； 计算氨基酸对出现的期望频率e； 计算BLOSUM62矩阵分量rij,BLOSUM62打分矩阵,,BLOSUM & PAM,序列相似性与PAM及BLOSUM矩阵的大致对应关系：,第四节， 多序列比对,不同物种中，许多基因的功能保守，序列相似性较高，通过多条序列的比较，发现保守与变异的部分； 可构建HMM模型，搜索更多的同源序列； 构建进化的树的必须步骤； 比较基因组学研究； 两类：全局或局部的多序列比对；,全局性的多序列比对,Made by GENEDOC,双序列比对,4,2,,,,,,,,,时间复杂度：O(n2),多序列比对：最优算法,三条序列：时间复杂度：O(lmn) = O(n3),四条序列：时间复杂度：O(n4)，非多项式时间！,多项式时间复杂度要求：≤O(n3),m条序列：时间复杂度：O(nm)，NPC问题！,…,动态规划算法：全空间,动态规划算法：优化算法,动态规划算法：Hyperlattice,注意,最优的多序列比对，其两两序列之间的比对不一定最优。

最优的多序列比对,非最优的双序列比对,MSA程序,MSA - Multiple Sequence Alignment David Lipman等，1989年初始开发； 应用多维动态规划算法，得到最优的全局比对 工具资源： http://www.ncbi.nlm.nih.gov/CBBresearch/Schaffer/msa.html http://www.psc.edu/general/software/packages/msa/manual/manual.php,MSA： 打分方式,多序列比对：方法改进,1. 渐进方法：progressive methods 代表：ClustalW/X, T-Coffee 2. 迭代方法：iterative methods 代表: PRRP, DIALIGN 3. 部分有向图算法： Partial Order Algorithm (POA) 4. 全局多序列比对的隐马尔科夫模型 profile HMM 5. 整合算法： MUSCLE,1. Progressive methods,(1) ClustalW/X (2) T-Coffee,(1) ClustalW/X,1. Clustal: 1988年开发； 2. ClustalW: 1994年，Julie D. Thompson等人改进、发展； 3. ClustalX: 1997年，图形化软件；,ClustalW/X：计算过程,1. 将所有序列两两比对，计算距离矩阵； 2. 构建邻接进化树(neighbor-joining tree)/指导树(guide tree)； 3. 将距离最近的两条序列用动态规划的算法进行比对； 4. “渐进”的加上其他的序列。

两两比对，构建距离矩阵,指导树的构建,渐进比对,ClustalW的打分原则,每条序列的权值,,,Score:BLOSUM62的分数,ClustalX的使用,1. FASTA序列格式，多序列：,ClustalX的使用 ——导入序列文件,,执行比对,,文件导出,,,多序列比对：结果处理,BioEdit, GeneDoc等软件,GeneDoc软件，导入.aln文件,选择文件格式,,成功导入文件,选择需要拷贝的行,(2) T-Coffee,1. 采用Clustal程序计算两两序列之间的全局最优比对结果； 2. 采用LALIGN程序计算两两序列之间的局部最优比对的结果； 3. 设计加权系统，综合考虑以上两类结果的因素，构建指导库； 4. 最后，采用渐进式比对算法，得到最终的结果同时进行全局和局部的双序列比对,对以上打分的结果设计权重系统，找到序列中最保守的部分,渐进方法的比对，基于上述计算的primary library,,ClustalW/X：存在的问题,1. 距离最近的，有两组序列AB和CD，哪组最先比对？两种方案： A. 分别、同时比对但是，是以AB为准，加入CD，然后再加上其他序列，还是CD为准？结果可能出入很大 B. 随机挑选一组作为基准 2. 当序列差异较大时，上述问题更加明显。

例如,1. 三条序列： 2.若Seq1,2先比对，再加入Seq3： 3. Seq1,3先比对，再加入Seq2: 4. Seq2,3先比对，再加入Seq1:,Seq1: ARKCV Seq2: ARCV Seq3: AKCV,ARKCV AR-CV A-KCV,ARKCV A-RCV A-KCV,ARKCV AR-CV AK-CV,2. 迭代方法,1. 部分解决渐进算法存在的问题,主要是ClustalW/X存在的问题； 2. PRRP 3. DIALIGN,(1) PRRP,1. 先用“渐进”算法进行多序列比对; 2. 基于多序列比对的结果构建进化树； 3. 重新计算序列之间的距离，再用“渐进”算法进行多序列比对； 4. 重复上述步骤，直到结果不再发生改变为止2) DIALIGN,1. 对所有序列进行两两之间的局部最优化的比对； 2. 找到所有能够匹配的部分M1；将重叠的、前后连续(consistency)的匹配部分连接起来(diagonals)，为M2； 3. 将剩下的未比对的序列重新比对，再发现能够匹配的部分，构成新M1，将consistency部分构成M2； 4. 重复上述步骤，直到结果收敛。

DIALIGN: 算法流程,3. 部分有向图算法,激酶的多序列比对,4. 隐马尔科夫模型: ProbCons,主要改进： 1. 所有序列的两两比对，通过profile HMM的方法进行双序列比对； 2. 将渐进算法与迭代算法整合； 3. 目前，性能最优5. 整合算法MUSCLE,算法分为三个部分，每个部分相对独立； 1. Draft progressive: (1) 对两条序列，计算距离采用k-mer的思想； (2) 用UPGMA算法构建引导树； (3) 使用渐进算法进行多。