《中国科技大学系列生物信息学ppt课件》由会员分享，可在线阅读，更多相关《中国科技大学系列生物信息学ppt课件（72页珍藏版）》请在金锄头文库上搜索。
1、1生物信息学生物信息学第三章第三章 序列比对序列比对 2本章内容提要本章内容提要r第一节：数学基础：概率及概率模型第一节：数学基础：概率及概率模型r第二节：双序列比对算法的介绍第二节：双序列比对算法的介绍Dot matrix动态规划算法动态规划算法w(Needleman-Wunsch, Smith-Waterman算法算法) FASTA和和BLAST算法算法r第三节：打分矩阵及其含义第三节：打分矩阵及其含义r第四节：多序列比对第四节：多序列比对3第三节第三节 打分矩阵及其含义打分矩阵及其含义r 1，计分方法，计分方法r 2，Dayhoff: PAM系列矩阵系列矩阵r 3，Henikoff: B
2、LOSUM系列矩阵系列矩阵41 1， 计分方法计分方法r匹配计分：匹配计分： UM矩阵矩阵(Unitary matrix)相同的氨基酸记相同的氨基酸记1分，否则记分，否则记0分。分。BLAST中核酸比对中核酸比对r结构域性质计分：结构域性质计分： SGM矩阵矩阵(Structure-Genetic Matrix) 主要根据氨基酸的结构和化学性质的相似程度来记分主要根据氨基酸的结构和化学性质的相似程度来记分(如如D和和E，S和和T，V和和I有很高的相似有很高的相似性性)，同时还考虑密码子之间相互转换的难易程度。，同时还考虑密码子之间相互转换的难易程度。r可观测变换计分：可观测变换计分：PAM矩阵
3、矩阵 (Point Accepted Mutation)BLOSUM矩阵矩阵 (BLOcks SUbstitution Matrix)52 2， PAMPAM系列矩阵系列矩阵r Margaret Dayhoff, 1978;r通过对物种进化的研究，根据一种氨基酸被另一种氨基酸替代的频度而提出的，最常用通过对物种进化的研究，根据一种氨基酸被另一种氨基酸替代的频度而提出的，最常用的是的是PAM250;r Accepted point mutation (PAM): 可接受的点突变，氨基酸的改变不显著影响蛋白质的可接受的点突变，氨基酸的改变不显著影响蛋白质的功能；功能；6PAMPAM矩阵矩阵r71个
4、蛋白质家族的个蛋白质家族的1572种变化；种变化；r序列相似性序列相似性 85%；r功能同源的蛋白质功能同源的蛋白质 通过中性进化，引入可接受的点突变；通过中性进化，引入可接受的点突变；r 进化模型：进化模型：A. 基本假设：中性进化，基本假设：中性进化，Kimura,1968;B. 进化的对称性进化的对称性: A-B = B-A;C. 扩展性：通过对较短时间内氨基酸替代关系的计算来计算较长时间的氨基酸替扩展性：通过对较短时间内氨基酸替代关系的计算来计算较长时间的氨基酸替代关系；代关系；7PAM1PAM1矩阵矩阵r 两个蛋白质序列的两个蛋白质序列的1%氨基酸发生变化；氨基酸发生变化；r 定义进
5、化时间以氨基酸的变异比例为准，而不是时间；因为各个蛋白质家族进化的速度定义进化时间以氨基酸的变异比例为准，而不是时间；因为各个蛋白质家族进化的速度并不相等；并不相等；r PAM2 = PAM1*PAM1 PAM3 = (PAM1)3 PAM250= (PAM1)2508PAMnPAMn矩阵的构建矩阵的构建1.选取多个家族的相似性选取多个家族的相似性85%的保守序列；的保守序列；2.根据匹配计分进行多重比对根据匹配计分进行多重比对(不含空位不含空位)；3.以比对结果构建进化树，反映氨基酸替换关系；以比对结果构建进化树，反映氨基酸替换关系；4.计算每种氨基酸转换成其它氨基酸的次数；计算每种氨基酸转
6、换成其它氨基酸的次数；5.计算每种氨基酸突变率；计算每种氨基酸突变率；6.计算每对氨基酸突变率，得到突变概率矩阵，将此矩阵自乘计算每对氨基酸突变率，得到突变概率矩阵，将此矩阵自乘n次；次；7.将突变概率矩阵转化为将突变概率矩阵转化为PAMn矩阵。矩阵。9例例6 6：PAMPAM矩阵的构建矩阵的构建r 已知已知3个蛋白质家族若干保守序列片段：个蛋白质家族若干保守序列片段：家族一：家族一：FKILK，FKIKK，FFILL，FFIKL家族二：家族二：IIFFF， IIFIF ， IKFFL ， IKFIL家族三：家族三： KIFKK，KIFLK，KLFKL，KLFLL按按Doyhoff方法构建方法
7、构建PAM1与与PAM2矩阵矩阵10Step1Step1：多重比对：多重比对r位置对齐，多重比对（不考虑空位）：位置对齐，多重比对（不考虑空位）：r统计每种氨基酸出现的频率；统计每种氨基酸出现的频率；fi = 氨基酸氨基酸i的数目的数目/总氨基酸数目总氨基酸数目fL = 12/60 = 0.2.家族一家族一家族二家族二家族三家族三F K I L KII F F FK I F K KF K I K KII F I FK I F L KF F I L LI K F F LK L F K LF F I K LI K F I LK L F L L11Step2Step2：构建进化树：构建进化树r最大简
8、约法最大简约法家族一家族一:wL和和K间相互转换次数：间相互转换次数：N(LK) = 3家族二，家族三家族二，家族三 FKILKFKIKKFKIKKFFIKLFFILLFFIKL(LK)(KF)(LK)(LK)12Step3Step3：计算氨基酸间的转换次数：计算氨基酸间的转换次数r计算每种氨基酸转换成其它氨基酸的次数。计算每种氨基酸转换成其它氨基酸的次数。r假设两种氨基酸间相互转换一样。假设两种氨基酸间相互转换一样。e.g. N(LK)= 3 + 0 + 3 = 6KFILK116F121I121L61113Step4Step4：计算各氨基酸相对突变率：计算各氨基酸相对突变率r每种氨基酸相对
9、突变率每种氨基酸相对突变率miri：第：第i种氨基酸；种氨基酸；rfi ：每种氨基酸出现的频率；：每种氨基酸出现的频率；mK = 8/(122 fK 100) = 0.012514Step5Step5：计算氨基酸：计算氨基酸i i替换为替换为j j的突变率的突变率r氨基酸氨基酸i替换为替换为j的突变率的突变率mije.g.mKK = 1- mK = 0.9875mKF = mF 1/4 = 0.00138915Step5Step5：氨基酸一步转移概率矩阵：氨基酸一步转移概率矩阵r氨基酸突变概率氨基酸突变概率一步转移概率矩阵一步转移概率矩阵M1ij原氨基酸原氨基酸KFIL替换氨基酸替换氨基酸K0
10、.98750.0015630.0015630.009375F0.0013890.9944440.0027780.001389I0.0017860.0035710.9928570.001786L0.01250.0020830.0020830.98333316Step6:Step6:计算计算PAM1PAM1计分矩阵计分矩阵r由突变率由突变率mij计算计分矩阵中的分值计算计分矩阵中的分值rij：r将将rij = rji取平均值，再取整数；取平均值，再取整数；（按先前假设，（按先前假设， rij = rji） rKK = 10lg(mkk/ fk) = 5.6857 6 (rKF + rFK )/2
11、= -22.833 -23 17Step6:PAM1Step6:PAM1计分矩阵结果计分矩阵结果r三个家族序列片段得到的三个家族序列片段得到的PAM1计分矩阵：计分矩阵：KFILK6F-235I-22-196L-13-22-20718Step7:Step7:计算计算PAM2PAM2计分矩阵计分矩阵r将氨基酸突变概率矩阵自乘一次，得到两步转移概率矩阵将氨基酸突变概率矩阵自乘一次，得到两步转移概率矩阵M2ij M2ij = M1ij M1ijr三个家族序列片段得到的三个家族序列片段得到的PAM2计分矩阵：计分矩阵：KFILK6F-205I-19-166L-10-19-18719PAM250PAM2
12、50矩阵矩阵r PAM250: 250%期望的突变；期望的突变；r 蛋白质序列仍然有蛋白质序列仍然有15-30%左右的相似性；左右的相似性；20PAM250PAM250打分矩阵打分矩阵21打分矩阵的使用打分矩阵的使用rPAM250: 15-30%的序列相似性；的序列相似性；rPAM120: 40%的序列相似性；的序列相似性；rPAM80: 50%rPAM60: 60%r如何选择最合适的矩阵？如何选择最合适的矩阵？r 多种尝试多种尝试22PAMPAM矩阵的问题及改进矩阵的问题及改进r1. PAM系列矩阵存在的问题：系列矩阵存在的问题：A. 氨基酸的打分矩阵，不关心核酸；氨基酸的打分矩阵，不关心核
13、酸；B. 进化模型的构建需要系统发育树的分析，因此，成为一个循环论证的问题：序列进化模型的构建需要系统发育树的分析，因此，成为一个循环论证的问题：序列比对比对矩阵构建矩阵构建打分打分进行新的序列比对；进行新的序列比对；C. 数据集很小；数据集很小；r2. 打分矩阵的改进打分矩阵的改进A. 选用大量的序列数据，构建选用大量的序列数据，构建PAM矩阵；矩阵；B. BLOSUM系列矩阵系列矩阵;C. 核酸的打分矩阵核酸的打分矩阵;233 3， BLOSUMBLOSUM矩阵矩阵r最被广泛使用的氨基酸打分矩阵最被广泛使用的氨基酸打分矩阵;r根据蛋白质模块数据库根据蛋白质模块数据库BLOCKS中蛋白质序列
14、的高度保守部分的比对而得到的，最常用中蛋白质序列的高度保守部分的比对而得到的，最常用的是的是BLOSUM62;rBLOCK: 蛋白质家族保守的一段氨基酸，无蛋白质家族保守的一段氨基酸，无gap，一般几个至上百个氨基酸；，一般几个至上百个氨基酸；rProsite家族：至少有一个家族：至少有一个BLOCK存在于该家族的所有蛋白质序列中；存在于该家族的所有蛋白质序列中；rBLOSUM62: 序列的平均相似性为序列的平均相似性为62%的的BLOCK构建的打分矩阵；构建的打分矩阵；24BLOSUM62BLOSUM62矩阵构建步骤：矩阵构建步骤：1.提取提取Prosite数据库中数据库中504个家族的个家
15、族的2万多蛋白质序列，合并其中相似性万多蛋白质序列，合并其中相似性62%的序列；的序列；2.统计各统计各BLOCK的氨基酸对数量的氨基酸对数量f；3.计算氨基酸对的出现频率计算氨基酸对的出现频率q；4.计算每种氨基酸的期望频率计算每种氨基酸的期望频率p；5.计算氨基酸对出现的期望频率计算氨基酸对出现的期望频率e；6.计算计算BLOSUM62矩阵分量矩阵分量rij25BLOSUM62BLOSUM62打分矩阵打分矩阵26BLOSUM&PAMBLOSUM&PAMr序列相似性与序列相似性与PAM及及BLOSUM矩阵的大致对应关系：矩阵的大致对应关系：序列相似性序列相似性 %99908070605040
16、3020PAM数值数值11123385680112159246BLOSUM数值数值908062-4527第四节，第四节， 多序列比对多序列比对r 不同物种中，许多基因的功能保守，序列相似性较高，通过多条序列的比较，发现保守与不同物种中，许多基因的功能保守，序列相似性较高，通过多条序列的比较，发现保守与变异的部分；变异的部分；r 可构建可构建HMM模型，搜索更多的同源序列；模型，搜索更多的同源序列；r 构建进化的树的必须步骤；构建进化的树的必须步骤；r 比较基因组学研究；比较基因组学研究；r 两类：全局或局部的多序列比对；两类：全局或局部的多序列比对；28全局性的多序列比对全局性的多序列比对Ma
17、de by GENEDOC29双序列比对双序列比对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)30多序列比对：最优算法多序列比对：最优算法三条序列：时间复杂度：三条序列：时间复杂度：O(lmn) = O(n3)四条序列：时间复杂度：四条序列：时间复杂度：O(n4)，非多项式时间！，非多项式时间！多项式时间复杂度要求：O(n3)m条序列：时间复杂度：条序列：时间复
18、杂度：O(nm)，NPC问题！问题！31动态规划算法：全空间动态规划算法：全空间32动态规划算法：优化算法动态规划算法：优化算法Sequence ASequence BSequence C 搜索有限空间，类似于搜索有限空间，类似于BLAST算法算法33动态规划算法：动态规划算法：HyperlatticeHyperlattice34注意注意r 最优的多序列比对，其两两序列之间的比对不一定最优。最优的多序列比对，其两两序列之间的比对不一定最优。 最优的多序列比对最优的多序列比对非最优的双序列比对非最优的双序列比对35MSAMSA程序程序rMSA - Multiple Sequence Alignm
19、entrDavid Lipman等，等，1989年初始开发；年初始开发；r应用多维动态规划算法，得到最优的全局比对。应用多维动态规划算法，得到最优的全局比对。r工具资源：工具资源：36MSAMSA：打分方式打分方式37多序列比对：方法改进多序列比对：方法改进r1. 渐进方法：渐进方法：progressive methods代表：代表：ClustalW/X, T-Coffeer2. 迭代方法：迭代方法：iterative methods 代表代表: PRRP, DIALIGNr3. 部分有向图算法：部分有向图算法：Partial Order Algorithm (POA)r4. 全局多序列比对的
20、隐马尔科夫模型全局多序列比对的隐马尔科夫模型pror5. 整合算法：整合算法： MUSCLE381.Progressivemethods1.Progressivemethodsr(1) ClustalW/Xr(2) T-Coffee39(1)ClustalW/X(1)ClustalW/Xr1. Clustal: 1988年开发；年开发；r2. ClustalW: 1994年，年，Julie D. Thompson等人改进、发展；等人改进、发展；r3. ClustalX: 1997年，图形化软件；年，图形化软件；40ClustalW/XClustalW/X：计算过程：计算过程r1. 将所有序列两
21、两比对，计算距离矩阵；将所有序列两两比对，计算距离矩阵；r2. 构建邻接进化树构建邻接进化树(neighbor-joining tree)/指导树指导树(guide tree)；r3. 将距离最近的两条序列用动态规划的算法进行比对；将距离最近的两条序列用动态规划的算法进行比对；r4. “渐进渐进”的加上其他的序列。的加上其他的序列。41两两比对，构建距离矩阵指导树的构建指导树的构建渐进比对渐进比对42ClustalWClustalW的打分原则的打分原则每条序列的权值每条序列的权值Score:BLOSUM62的分数的分数43ClustalXClustalX的使用的使用r1. FASTA序列格式，
22、多序列：序列格式，多序列：44ClustalXClustalX的使用的使用导入序列文件导入序列文件45执行比对执行比对46文件导出文件导出47多序列比对：结果处理多序列比对：结果处理r BioEdit, GeneDoc等软件等软件GeneDocGeneDoc软件，导入软件，导入.aln.aln文件文件48选择文件格式选择文件格式49成功导入文件成功导入文件50选择需要拷贝的行选择需要拷贝的行51(2)T-Coffee(2)T-Coffeer1. 采用采用Clustal程序计算两两序列之间的全局最优比对结果；程序计算两两序列之间的全局最优比对结果；r2. 采用采用LALIGN程序计算两两序列之间
23、的局部最优比对的结果；程序计算两两序列之间的局部最优比对的结果；r3. 设计加权系统，综合考虑以上两类结果的因素，构建指导库；设计加权系统，综合考虑以上两类结果的因素，构建指导库；r4. 最后，采用渐进式比对算法，得到最终的结果。最后，采用渐进式比对算法，得到最终的结果。52同时进行全局和局部的双序列比对同时进行全局和局部的双序列比对对以上打分的结果设计权重系统，找对以上打分的结果设计权重系统，找到序列中最保守的部分到序列中最保守的部分渐进方法的比对，基于上述计算的渐进方法的比对，基于上述计算的primary library53ClustalW/XClustalW/X：存在的问题：存在的问题r
24、1. 距离最近的，有两组序列距离最近的，有两组序列AB和和CD，哪组最先比对？两种方案：，哪组最先比对？两种方案：A. 分别、同时比对。但是，是以分别、同时比对。但是，是以AB为准，加入为准，加入CD，然后再加上其他序列，还是，然后再加上其他序列，还是CD为准？结果可能出入很大为准？结果可能出入很大B. 随机挑选一组作为基准随机挑选一组作为基准r2. 当序列差异较大时，上述问题更加明显。当序列差异较大时，上述问题更加明显。54例如例如r1. 三条序列：三条序列：r2.若若Seq1,2先比对，再加入先比对，再加入Seq3：r3. Seq1,3先比对，再加入先比对，再加入Seq2:r4. Seq2
25、,3先比对，再加入先比对，再加入Seq1:Seq1: ARKCVSeq2: ARCVSeq3: AKCVARKCVAR-CVA-KCVARKCVA-RCVA-KCVARKCVAR-CVAK-CV552.2.迭代方法迭代方法r1. 部分解决渐进算法存在的问题部分解决渐进算法存在的问题,主要是主要是ClustalW/X存在的问题；存在的问题；r2. PRRPr3. DIALIGN56(1)PRRP(1)PRRP1. 1. 先用先用“渐进渐进”算法进行多序列比对算法进行多序列比对; ;2. 2. 基于多序列比对的结果构建进化树；基于多序列比对的结果构建进化树；3. 3. 重新计算序列之间的距离，再用
26、重新计算序列之间的距离，再用“渐渐进进”算法进行多序列比对；算法进行多序列比对；4. 4. 重复上述步骤，直到结果不再发生改重复上述步骤，直到结果不再发生改变为止。变为止。57(2)DIALIGN(2)DIALIGNr1. 对所有序列进行两两之间的局部最优化的比对；对所有序列进行两两之间的局部最优化的比对；r2. 找到所有能够匹配的部分找到所有能够匹配的部分M1；将重叠的、前后连续；将重叠的、前后连续(consistency)的匹配部分连接起的匹配部分连接起来来(diagonals)，为，为M2；r3. 将剩下的未比对的序列重新比对，再发现能够匹配的部分，构成新将剩下的未比对的序列重新比对，再
27、发现能够匹配的部分，构成新M1，将，将consistency部分构成部分构成M2；r4. 重复上述步骤，直到结果收敛。重复上述步骤，直到结果收敛。58DIALIGN:DIALIGN:算法流程算法流程593.3.部分有向图算法部分有向图算法6061激酶的多序列比对激酶的多序列比对624.4.隐马尔科夫模型隐马尔科夫模型:ProbCons:ProbConsr主要改进：主要改进：1. 所有序列的两两比对，通过所有序列的两两比对，通过pro的方法进行双序列比对；的方法进行双序列比对；2. 将渐进算法与迭代算法整合；将渐进算法与迭代算法整合；3. 目前，性能最优。目前，性能最优。635.5.整合算法整合
28、算法MUSCLEMUSCLEr算法分为三个部分，每个部分相对独立；算法分为三个部分，每个部分相对独立；r1. Draft progressive: (1) 对两条序列，计算距离采用对两条序列，计算距离采用k-mer的思想；的思想；(2) 用用UPGMA算法构建引导树；算法构建引导树；(3) 使用渐进算法进行多序列比对；使用渐进算法进行多序列比对；r优点：两条序列之间的距离不采用动态规划算法进行比对，节省时间。优点：两条序列之间的距离不采用动态规划算法进行比对，节省时间。64MUSCLEMUSCLEr2. Improved progressive: (1)基于基于k-mer得到的树可能会产生次优
29、结果，因此，采用得到的树可能会产生次优结果，因此，采用Kimura距离的方法对距离的方法对k-mer产生的树重新计算距离矩阵；产生的树重新计算距离矩阵；(2)重新用重新用UPGMA构建进化树；构建进化树；(3)使用渐进算法进行多序列比对；使用渐进算法进行多序列比对；65r3. Refinement: (1)随机从进化树上挑出一条边，删除；随机从进化树上挑出一条边，删除；(2)得到两组树，对每组树，计算得到两组树，对每组树，计算profile；(3)将两组将两组profile进行比对；进行比对；(4)如果最终得分提高，保留结果，否则丢弃。如果最终得分提高，保留结果，否则丢弃。MUSCLEMUSC
30、LE66MUSCLEMUSCLE的算法流程的算法流程67MUSCLE:MUSCLE:使用指南使用指南68MUSCLEMUSCLE的使用的使用69多序列比对：性能检验多序列比对：性能检验r1. BAliBASE：基于蛋白质结构，将同一家族的蛋白质序列进行多序列比较。：基于蛋白质结构，将同一家族的蛋白质序列进行多序列比较。r2. 检验多序列比对工具的性能：是否能够很好的重复检验多序列比对工具的性能：是否能够很好的重复BAliBASE中已明确的比对结果。中已明确的比对结果。70AMPAMP结合酶的结构结合酶的结构/ /序列比较序列比较71性能比较性能比较r ProbCons：目前综合性能最好；：目前综合性能最好；r T-Coffee：序列相似性高时最准确；：序列相似性高时最准确；r DIALIGN: 序列相似性低时最准确；序列相似性低时最准确；r POA：性能接近：性能接近T-Coffee和和DIALIGN，速度最快；，速度最快；r ClustalW/X: 最经典、被广泛接受的工具；最经典、被广泛接受的工具；r MUSCLE: 目前最流行的多序列比对工具；目前最流行的多序列比对工具；72运算时间比较运算时间比较
