《中国科技大学课件系列生物信息学.ppt》由会员分享，可在线阅读，更多相关《中国科技大学课件系列生物信息学.ppt（72页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章第三章 序列比对序列比对 第一页，编辑于星期六：十四点 五十七分。r第一节：数学基础：概率及概率模型第一节：数学基础：概率及概率模型r第二节：双序列比对算法的介绍第二节：双序列比对算法的介绍Dot matrix动态规划算法动态规划算法w(Needleman-Wunsch, Smith-Waterman算法算法) FASTA和和BLAST算法算法r第三节：打分矩阵及其含义第三节：打分矩阵及其含义r第四节：多序列比对第四节：多序列比对第二页，编辑于星期六：十四点 五十七分。r 1，计分方法，计分方法r 2，Dayhoff: PAM系列矩阵系列矩阵r 3，Henikoff: BLOSUM系列矩
2、阵系列矩阵第三页，编辑于星期六：十四点 五十七分。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)第四页，编辑于星期六：十四点 五十七分。r Margaret Dayhoff, 1978;r通过对物种进化的研究，根据一种氨基酸被另一通过对物种进化的研究，根据一种氨基酸被另一种氨基酸替代的频度而提出的，最常用的是种氨基酸替代的频度而提出的，最常用的是PAM250;r Accepted point mutation (PAM): 可接受可接受的点突变，氨基酸的改变不显著影响蛋白质的的点突变，氨基酸的改变不显著影响蛋白质的功能；功能；第五页，编辑于星期六：十四点 五
4、十七分。r71个蛋白质家族的个蛋白质家族的1572种变化；种变化；r序列相似性序列相似性 85%；r 功能同源的蛋白质功能同源的蛋白质 通过中性进化，引入通过中性进化，引入可接受的点突变；可接受的点突变；r 进化模型：进化模型：A. 基本假设：中性进化，基本假设：中性进化，Kimura,1968;B. 进化的对称性进化的对称性: A-B = B-A;C. 扩展性：通过对较短时间内氨基酸替代关系的计扩展性：通过对较短时间内氨基酸替代关系的计算来计算较长时间的氨基酸替代关系；算来计算较长时间的氨基酸替代关系；第六页，编辑于星期六：十四点 五十七分。r 两个蛋白质序列的两个蛋白质序列的1%氨基酸发生
5、变化；氨基酸发生变化；r 定义进化时间以氨基酸的变异比例为准，定义进化时间以氨基酸的变异比例为准，而不是时间；因为各个蛋白质家族进化的速而不是时间；因为各个蛋白质家族进化的速度并不相等；度并不相等；r PAM2 = PAM1*PAM1 PAM3 = (PAM1)3 PAM250= (PAM1)250第七页，编辑于星期六：十四点 五十七分。r选取多个家族的相似性选取多个家族的相似性85%的保守序列；的保守序列；r根据匹配计分进行多重比对根据匹配计分进行多重比对(不含空位不含空位)；r以比对结果构建进化树，反映氨基酸替换关以比对结果构建进化树，反映氨基酸替换关系；系；r计算每种氨基酸转换成其它氨基
6、酸的次数；计算每种氨基酸转换成其它氨基酸的次数；r计算每种氨基酸突变率；计算每种氨基酸突变率；r计算每对氨基酸突变率，得到突变概率矩阵计算每对氨基酸突变率，得到突变概率矩阵，将此矩阵自乘，将此矩阵自乘n次；次；r将突变概率矩阵转化为将突变概率矩阵转化为PAMn矩阵。矩阵。第八页，编辑于星期六：十四点 五十七分。r 已知已知3个蛋白质家族若干保守序列片段：个蛋白质家族若干保守序列片段：家族一：家族一：FKILK，FKIKK，FFILL，FFIKL家族二：家族二：IIFFF， IIFIF ， IKFFL ， IKFIL家族三：家族三： KIFKK，KIFLK，KLFKL，KLFLL按按Doyhof
7、f方法构建方法构建PAM1与与PAM2矩阵矩阵第九页，编辑于星期六：十四点 五十七分。r位置对齐，多重比对（不考虑空位）：位置对齐，多重比对（不考虑空位）：r统计每种氨基酸出现的频率；统计每种氨基酸出现的频率；fi = 氨基酸氨基酸i的数目的数目/总氨基酸数目总氨基酸数目fL = 12/60 = 0.2.家族一家族二家族三F K I L KI I F F FK I F K KF K I K KI I 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 L第十页，编辑于星期六：十四点 五十七分。r最大简约法最大简约
8、法家族一家族一:w L和和K间相互转换次数：间相互转换次数：N(LK) = 3家族二，家族三家族二，家族三 FKILKFKIKKFKIKKFFIKLFFILLFFIKL(LK)(KF)(LK)(LK)第十一页，编辑于星期六：十四点 五十七分。r计算每种氨基酸转换成其它氨基酸的次数。计算每种氨基酸转换成其它氨基酸的次数。r假设两种氨基酸间相互转换一样。假设两种氨基酸间相互转换一样。e.g. N(LK)= 3 + 0 + 3 = 6KFILK116F121I121L611第十二页，编辑于星期六：十四点 五十七分。r每种氨基酸相对突变率每种氨基酸相对突变率miri：第：第i种氨基酸；种氨基酸；rfi
9、 ：每种氨基酸出现的频率；：每种氨基酸出现的频率；mK = 8/(122 fK 100) = 0.01251002iifim总替换数总共发生替换数氨基酸第十三页，编辑于星期六：十四点 五十七分。r氨基酸氨基酸i替换为替换为j的突变率的突变率mije.g.mKK = 1- mK = 0.9875mKF = mF 1/4 = 0.001389iiiiijmmjijjimmji1时，总共发生替换数氨基酸相互替换的次数与氨基酸时，第十四页，编辑于星期六：十四点 五十七分。r氨基酸突变概率氨基酸突变概率一步转移概率矩阵一步转移概率矩阵M1ij原氨基酸KFIL替换氨基酸K0.98750.0015630.0
10、015630.009375F0.0013890.9944440.0027780.001389I0.0017860.0035710.9928570.001786L0.01250.0020830.0020830.983333第十五页，编辑于星期六：十四点 五十七分。r由突变率由突变率mij计算计分矩阵中的分值计算计分矩阵中的分值rij：r将将rij = rji取平均值，再取整数；取平均值，再取整数；（按先前假设，（按先前假设， rij = rji） rKK = 10lg(mkk/ fk) = 5.6857 6 (rKF + rFK )/2 = -22.833 -23 )/lg(10iijijfmr
11、 第十六页，编辑于星期六：十四点 五十七分。r三个家族序列片段得到的三个家族序列片段得到的PAM1计分矩阵：计分矩阵：KFILK6F-235I-22-196L-13-22-207第十七页，编辑于星期六：十四点 五十七分。r将氨基酸突变概率矩阵自乘一次，得到两步将氨基酸突变概率矩阵自乘一次，得到两步转移概率矩阵转移概率矩阵M2ij M2ij = M1ij M1ijr三个家族序列片段得到的三个家族序列片段得到的PAM2计分矩阵：计分矩阵：KFILK6F-205I-19-166L-10-19-187第十八页，编辑于星期六：十四点 五十七分。r PAM250: 250%期望的突变；期望的突变；r 蛋白
12、质序列仍然有蛋白质序列仍然有15-30%左右的相似性；左右的相似性；第十九页，编辑于星期六：十四点 五十七分。第二十页，编辑于星期六：十四点 五十七分。rPAM250: 15-30%的序列相似性的序列相似性；rPAM120: 40%的序列相似性；的序列相似性；rPAM80: 50%rPAM60: 60%r如何选择最合适的矩阵？如何选择最合适的矩阵？r 多种尝试多种尝试第二十一页，编辑于星期六：十四点 五十七分。r1. PAM系列矩阵存在的问题：系列矩阵存在的问题：A. 氨基酸的打分矩阵，不关心核酸；氨基酸的打分矩阵，不关心核酸；B. 进化模型的构建需要系统发育树的分析，因进化模型的构建需要系统
13、发育树的分析，因此，成为一个循环论证的问题：序列比对此，成为一个循环论证的问题：序列比对矩矩阵构建阵构建打分打分进行新的序列比对；进行新的序列比对；C. 数据集很小；数据集很小；r2. 打分矩阵的改进打分矩阵的改进A. 选用大量的序列数据，构建选用大量的序列数据，构建PAM矩阵；矩阵；B. BLOSUM系列矩阵系列矩阵;C. 核酸的打分矩阵核酸的打分矩阵;第二十二页，编辑于星期六：十四点 五十七分。r最被广泛使用的氨基酸打分矩阵最被广泛使用的氨基酸打分矩阵;r根据蛋白质模块数据库根据蛋白质模块数据库BLOCKS中蛋白质序中蛋白质序列的高度保守部分的比对而得到的，最常用列的高度保守部分的比对而得
14、到的，最常用的是的是BLOSUM62;rBLOCK: 蛋白质家族保守的一段氨基酸，无蛋白质家族保守的一段氨基酸，无gap，一般几个至上百个氨基酸；，一般几个至上百个氨基酸；rProsite家族：至少有一个家族：至少有一个BLOCK存在于该存在于该家族的所有蛋白质序列中；家族的所有蛋白质序列中；rBLOSUM62: 序列的平均相似性为序列的平均相似性为62%的的BLOCK构建的打分矩阵；构建的打分矩阵；第二十三页，编辑于星期六：十四点 五十七分。r提取提取Prosite数据库中数据库中504个家族的个家族的2万多蛋万多蛋白质序列，合并其中相似性白质序列，合并其中相似性62%的序列；的序列；r统计
15、各统计各BLOCK的氨基酸对数量的氨基酸对数量f；r计算氨基酸对的出现频率计算氨基酸对的出现频率q；r计算每种氨基酸的期望频率计算每种氨基酸的期望频率p；r计算氨基酸对出现的期望频率计算氨基酸对出现的期望频率e；r计算计算BLOSUM62矩阵分量矩阵分量rij)/(lg22eqrij第二十四页，编辑于星期六：十四点 五十七分。第二十五页，编辑于星期六：十四点 五十七分。r序列相似性与序列相似性与PAM及及BLOSUM矩阵的大致矩阵的大致对应关系：对应关系：序列相似性 %999080706050403020PAM数值11123385680112159246BLOSUM数值908062-45第二十
16、六页，编辑于星期六：十四点 五十七分。r 不同物种中，许多基因的功能保守，序列相不同物种中，许多基因的功能保守，序列相似性较高，通过多条序列的比较，发现保守似性较高，通过多条序列的比较，发现保守与变异的部分；与变异的部分；r 可构建可构建HMM模型，搜索更多的同源序列；模型，搜索更多的同源序列；r 构建进化的树的必须步骤；构建进化的树的必须步骤；r 比较基因组学研究；比较基因组学研究；r 两类：全局或局部的多序列比对；两类：全局或局部的多序列比对；第二十七页，编辑于星期六：十四点 五十七分。Made by GENEDOC第二十八页，编辑于星期六：十四点 五十七分。GapVDSCYGap0-11
17、-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问题问题！第三十页，编辑于星期六：十四点 五十七分。第三
18、十一页，编辑于星期六：十四点 五十七分。Sequence ASequence BSequence C 搜索有限空间，类似于搜索有限空间，类似于BLAST算法算法第三十二页，编辑于星期六：十四点 五十七分。第三十三页，编辑于星期六：十四点 五十七分。r 最优的多序列比对，其两两序列之间的比对不最优的多序列比对，其两两序列之间的比对不一定最优。一定最优。 最优的多序列比对最优的多序列比对非最优的双序列比对非最优的双序列比对第三十四页，编辑于星期六：十四点 五十七分。rMSA - Multiple Sequence AlignmentrDavid Lipman等，等，1989年初始开发；年初始开发；
19、r应用多维动态规划算法，得到最优的全局应用多维动态规划算法，得到最优的全局比对。比对。r工具资源：工具资源：http:/www.ncbi.nlm.nih.gov/CBBresearch/Schaffer/msa.htmlhttp:/www.psc.edu/general/software/packages/msa/manual/manual.php第三十五页，编辑于星期六：十四点 五十七分。第三十六页，编辑于星期六：十四点 五十七分。r1. 渐进方法：渐进方法：progressive methods代表：代表：ClustalW/X, T-Coffeer2. 迭代方法：迭代方法：iterativ
20、e methods 代表代表: PRRP, DIALIGNr3. 部分有向图算法：部分有向图算法：Partial Order Algorithm (POA)r4. 全局多序列比对的隐马尔科夫模型全局多序列比对的隐马尔科夫模型profile HMMr5. 整合算法：整合算法： MUSCLE第三十七页，编辑于星期六：十四点 五十七分。r(1) ClustalW/Xr(2) T-Coffee第三十八页，编辑于星期六：十四点 五十七分。r1. Clustal: 1988年开发；年开发；r2. ClustalW: 1994年，年，Julie D. Thompson等人改进、发展；等人改进、发展；r3.
21、ClustalX: 1997年，图形化软件；年，图形化软件；第三十九页，编辑于星期六：十四点 五十七分。r1. 将所有序列两两比对，计算距离矩阵；将所有序列两两比对，计算距离矩阵；r2. 构建邻接进化树构建邻接进化树(neighbor-joining tree)/指导树指导树(guide tree)；r3. 将距离将距离最近最近的两条序列用动态规划的算法的两条序列用动态规划的算法进行比对；进行比对；r4. “渐进渐进”的加上其他的序列。的加上其他的序列。第四十页，编辑于星期六：十四点 五十七分。两两比对，构建距离矩阵指导树的构建指导树的构建渐进比对渐进比对第四十一页，编辑于星期六：十四点 五十
22、七分。每条序列的权值每条序列的权值Score:BLOSUM62的分数的分数第四十二页，编辑于星期六：十四点 五十七分。r1. FASTA序列格式，多序列：序列格式，多序列：第四十三页，编辑于星期六：十四点 五十七分。第四十四页，编辑于星期六：十四点 五十七分。第四十五页，编辑于星期六：十四点 五十七分。第四十六页，编辑于星期六：十四点 五十七分。r BioEdit, GeneDoc等软件等软件GeneDocGeneDoc软件，导入软件，导入.aln.aln文件文件第四十七页，编辑于星期六：十四点 五十七分。第四十八页，编辑于星期六：十四点 五十七分。第四十九页，编辑于星期六：十四点 五十七分。
23、第五十页，编辑于星期六：十四点 五十七分。r1. 采用采用Clustal程序计算两两序列之间的全程序计算两两序列之间的全局最优比对结果；局最优比对结果；r2. 采用采用LALIGN程序计算两两序列之间的局程序计算两两序列之间的局部最优比对的结果；部最优比对的结果；r3. 设计加权系统，综合考虑以上两类结果的设计加权系统，综合考虑以上两类结果的因素，构建指导库；因素，构建指导库；r4. 最后，采用渐进式比对算法，得到最终的最后，采用渐进式比对算法，得到最终的结果。结果。第五十一页，编辑于星期六：十四点 五十七分。同时进行全局和局部的双同时进行全局和局部的双序列比对序列比对对以上打分的结果设计权重
24、对以上打分的结果设计权重系统，找到序列中最保守的系统，找到序列中最保守的部分部分渐进方法的比对，基于上述计渐进方法的比对，基于上述计算的算的primary library第五十二页，编辑于星期六：十四点 五十七分。r1. 距离最近的，有两组序列距离最近的，有两组序列AB和和CD，哪组，哪组最先比对？两种方案：最先比对？两种方案：A. 分别、同时比对。但是，是以分别、同时比对。但是，是以AB为准，加入为准，加入CD，然后再加上其他序列，还是，然后再加上其他序列，还是CD为准？结果为准？结果可能出入很大可能出入很大B. 随机挑选一组作为基准随机挑选一组作为基准r2. 当序列差异较大时，上述问题更加
25、明显。当序列差异较大时，上述问题更加明显。第五十三页，编辑于星期六：十四点 五十七分。r1. 三条序列：三条序列：r2.若若Seq1,2先比对先比对，再加入，再加入Seq3：r3. Seq1,3先比对，先比对，再加入再加入Seq2:r4. Seq2,3先比对，再先比对，再加入加入Seq1:Seq1: ARKCVSeq2: ARCVSeq3: AKCVARKCVAR-CVA-KCVARKCVA-RCVA-KCVARKCVAR-CVAK-CV第五十四页，编辑于星期六：十四点 五十七分。r1. 部分解决渐进算法存在的问题部分解决渐进算法存在的问题,主要是主要是ClustalW/X存在的问题；存在的问
26、题；r2. PRRPr3. DIALIGN第五十五页，编辑于星期六：十四点 五十七分。1. 1. 先用先用“渐进渐进”算法进行多算法进行多序列比对序列比对; ;2. 2. 基于多序列比对的结果构基于多序列比对的结果构建进化树；建进化树；3. 3. 重新计算序列之间的距离，重新计算序列之间的距离，再用再用“渐进渐进”算法进行多序列算法进行多序列比对；比对；4. 4. 重复上述步骤，直到结果重复上述步骤，直到结果不再发生改变为止。不再发生改变为止。第五十六页，编辑于星期六：十四点 五十七分。r1. 对所有序列进行两两之间的局部最优化的对所有序列进行两两之间的局部最优化的比对；比对；r2. 找到所有
27、能够匹配的部分找到所有能够匹配的部分M1；将重叠的；将重叠的、前后连续、前后连续(consistency)的匹配部分连接的匹配部分连接起来起来(diagonals)，为，为M2；r3. 将剩下的未比对的序列重新比对，再发现将剩下的未比对的序列重新比对，再发现能够匹配的部分，构成新能够匹配的部分，构成新M1，将，将consistency部分构成部分构成M2；r4. 重复上述步骤，直到结果收敛。重复上述步骤，直到结果收敛。第五十七页，编辑于星期六：十四点 五十七分。第五十八页，编辑于星期六：十四点 五十七分。第五十九页，编辑于星期六：十四点 五十七分。第六十页，编辑于星期六：十四点 五十七分。第六
28、十一页，编辑于星期六：十四点 五十七分。r主要改进：主要改进：1. 所有序列的两两比对，通过所有序列的两两比对，通过profile HMM的的方法进行双序列比对；方法进行双序列比对；2. 将渐进算法与迭代算法整合；将渐进算法与迭代算法整合；3. 目前，性能最优。目前，性能最优。第六十二页，编辑于星期六：十四点 五十七分。r算法分为三个部分，每个部分相对独立；算法分为三个部分，每个部分相对独立；r1. Draft progressive: (1) 对两条序列，计算距离采用对两条序列，计算距离采用k-mer的思想；的思想；(2) 用用UPGMA算法构建引导树；算法构建引导树；(3) 使用渐进算法进
29、行多序列比对；使用渐进算法进行多序列比对；r优点：两条序列之间的距离不采用动态规划优点：两条序列之间的距离不采用动态规划算法进行比对，节省时间。算法进行比对，节省时间。第六十三页，编辑于星期六：十四点 五十七分。r2. Improved progressive: (1)基于基于k-mer得到的树可能会产生次优结果，得到的树可能会产生次优结果，因此，采用因此，采用Kimura距离的方法对距离的方法对k-mer产生的产生的树重新计算距离矩阵；树重新计算距离矩阵；(2)重新用重新用UPGMA构建进化树；构建进化树；(3)使用渐进算法进行多序列比对；使用渐进算法进行多序列比对；第六十四页，编辑于星期六
30、：十四点 五十七分。r3. Refinement: (1)随机从进化树上挑出一条边，删除；随机从进化树上挑出一条边，删除；(2)得到两组树，对每组树，计算得到两组树，对每组树，计算profile；(3)将两组将两组profile进行比对；进行比对；(4)如果最终得分提高，保留结果，否则丢弃。如果最终得分提高，保留结果，否则丢弃。第六十五页，编辑于星期六：十四点 五十七分。第六十六页，编辑于星期六：十四点 五十七分。r http:/ 五十七分。第六十八页，编辑于星期六：十四点 五十七分。r1. BAliBASE：基于蛋白质结构，将同一家：基于蛋白质结构，将同一家族的蛋白质序列进行多序列比较。族的
31、蛋白质序列进行多序列比较。r2. 检验多序列比对工具的性能：是否能够很检验多序列比对工具的性能：是否能够很好的重复好的重复BAliBASE中已明确的比对结果。中已明确的比对结果。第六十九页，编辑于星期六：十四点 五十七分。第七十页，编辑于星期六：十四点 五十七分。r ProbCons：目前综合性能最好；：目前综合性能最好；r T-Coffee：序列相似性高时最准确；：序列相似性高时最准确；r DIALIGN: 序列相似性低时最准确；序列相似性低时最准确；r POA：性能接近：性能接近T-Coffee和和DIALIGN，速，速度最快；度最快；r ClustalW/X: 最经典、被广泛接受的工具；最经典、被广泛接受的工具；r MUSCLE: 目前最流行的多序列比对工具；目前最流行的多序列比对工具；第七十一页，编辑于星期六：十四点 五十七分。第七十二页，编辑于星期六：十四点 五十七分。