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

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