第四章-序列比对与算法ppt课件

.,1,第四章序列比对与算法,第一节双序列比对第二节多序列比对第三节常用序列比对软件的使用,.,第一节双序列比对,.,3,1.序列比对基本概念2.空位罚分3.双序列比对方法点阵序列比较(DotMatrixSequenceComparison)动态规划算法(DynamicProgrammingAlgorithm)4.记分矩阵,.,4,1.什么是序列比对？,序列比对(SequenceAlignment)是通过在序列中搜索一系列单个性状或性状模式来比较2个（双序列比对）或更多（多重序列比对）序列的方法。按比对序列条数分类双序列比对：两条序列的比对多序列比对：三条或以上序列的比对,.,5,1.我们为什么关注序列比对？,相似的序列可能具有相似的功能与结构；发现一个基因或蛋白哪些区域容易发生突变，哪些位点突变后对功能没有影响；发现生物进化方面的信息。,.,6,1.序列比对两种类型,全局序列比对定义：在全局范围内对两条序列进行比对打分的方法。适合于非常相似且长度近似相等的序列。局部序列比对定义：一种寻找匹配子序列的序列比对方法。适合于一些片段相似而另一些片段相异的序列。,.,7,1.序列比对两种类型,.,8,2.空位罚分(GapPenalties),空位为了获得两个序列最佳比对，必须使用空位和空位罚分。空位罚分分类：空位开放罚分(Gapopeningpenalty)空位扩展罚分(Gapextensionpenalty)最优的序列比对通常具有以下两下特征：尽可能多的匹配尽可能少的空位插入任意多的空位会产生较高的分数，但找到的并不一定是真正相似序列。,.,9,1GTGATAGACAC|1GTGCATAGACAC,2.空位罚分,允许空位但不罚分,不允许有空位,match=5mismatch=-4,1GTG-ATAGACAC|1GTGCATAGACAC,1GTG-ATAGACAC|1GTGC-ATAGACAC,?,Score:-21,Score:55,.,10,2.空位罚分公式,Score=4,参数:匹配=1非匹配=0g=3r=0.1x=3,score：8-3.2=4.8,Wx=g+r(x-1)Wx:空位总记分g:空位开放罚分r:空位扩展罚分x:空位长度,Wx=3+0.1*(3-1)=3.2,.,11,3.双序列比对方法,点阵序列比较(DotMatrixSequenceComparison)动态规划算法(DynamicProgrammingAlgorithm)词或K串方法(WordorK-tupleMethods),.,12,3.1点阵序列比较,点阵(DotMatrix)分析是一种简单的图形显示序列相似性的方法。沿X轴上序列1中的每一个单元（核苷酸或氨基酸）与沿Y轴的第二个序列中的每一个单元进行比较，相同的区域在点阵图中显示为由点组成的对角线，对角线之外零散的点为背景噪音。,.,14,点阵分析的应用,自身比对寻找序列中的正向或反向重复序列蛋白质的重复结构域(domain)相同残基重复出现的低复杂区(LowComplexity)RNA二级结构中的互补区域等对两条序列的相似性作整体的估计,点阵分析中的插入或删除,TACTGTCATTACTGTTCAT,Sequence1,Sequence2,TACTG-TCAT|TACTGTTCAT,插入空位,.,16,点阵分析的应用,人类低脂受体(humanlow-densitylipoproteinreceptor)自身比对发现正向重复序列,具有连续相似区域的两条DNA序列的简单点阵图,正向重复,.,17,点阵分析实例,编码噬菌体c（水平轴）和噬菌体P22c2（垂直轴）的氨基酸序列间的点阵分析相同的点全部打印，很难找到有用的信息,.,18,使用滑动窗口技术降低噪声,TACGGTATGACAGTATC,TACGGTATGACAGTATC,TACGGTATGACAGTATC,TACGGTATGACAGTATC,CTATGACATACGGTATG,Window=3WordSize=3,.,19,ATACTACAAGACACGTACCG,GCGATGCATTGAGTATCATA,Windowsize=5Stringency=3,Match=1Mismatch=0,.,20,ATACTACAAGACACGTACCG,GCGATGCATTGAGTATCATA,Windowsize=5Stringency=3,Match=1Mismatch=0,.,21,ATACTACAAGACACGTACCG,GCGATGCATTGAGTATCATA,Windowsize=5Stringency=3,Match=1Mismatch=0,.,22,GCGATGCATTGAGTATCATA,ATACTACAAGACACGTACCG,Windowsize=5Stringency=3,Match=1Mismatch=0,.,23,GCGATGCATTGAGTATCATA,ATACTACAAGACACGTACCG,.,24,GCGATGCATTGAGTATCATA,ATACTACAAGACACGTACCG,使用滑动窗口技术降低噪声,（a）对人类（Homosapiens）与黑猩猩（Pongopygmaeus）的球蛋白基因序列进行比较的完整点阵图（b）利用滑动窗口对以上的两种球蛋白基因序列进行比较的点阵图，其中窗口大小为10个核苷酸，相似度阈值为8，即10个核苷酸中有8个相同时就打一个点,a,b,.,26,点阵分析的优缺点,优点直观性，整体性；点阵分析不依赖空位(gap)参数，可寻找两序列间所有可能的残基匹配；不依赖任何先决条件，是一种可用于初步分析的理想工具；点阵分析允许随时动态地改变最高和最低界限值，可以用来摸索区分信号和背景标准的严格程度。,.,27,点阵分析的优缺点,缺点不能很好地兼容打分矩阵；滑动窗口和域值的选择过于经验化；信噪比低；不适合进行高通量的数据分析。,.,28,点阵分析程序,DNAStrider(Macintosh),.,29,3.2动态规划算法,动态规划算法(DynamicProgrammingAlgorithm)是一种计算方法，它的主要思路是把一个问题分成若干个小问题来解决。在生物学中应用的两种动态规划算法：Needleman-Wunsch算法（全局比对）和Smith-Waterman算法（局部比对）。,.,30,序列比对中某一位点匹配的三种可能性,Eg.匹配=1,非匹配=0,空位罚分=-1Sequence1:CACGASequence2:CGA,.,31,动态规划算法的数学形式,Sij=maxSi-1,j-1,+s(aibj),maxx1(Si-x,j-wx),maxy1(Si,j-y-wy),Sij=maxSi-1,j-1,+s(aibj),maxx1(Si-1,j-wx),maxy1(Si,j-1-wy),公式一的简化,公式一,公式二,说明：Sij是序列a在位置i和序列b在位置j的分值，s(aibj)是位置i和j上比对分值，wx是在序列a中长度为x的间隔罚分，wy是序列b中长度为y的间隔罚分,.,32,动态规划算法实例,匹配3错配-1空位-2,.,33,动态规划算法实例,匹配3错配-1空位-2,.,34,动态规划算法实例,匹配3错配-1空位-2,.,35,动态规划算法实例,匹配3错配-1空位-2,.,36,动态规划算法实例,匹配3错配-1空位-2,.,37,动态规划算法实例,?,匹配3错配-1空位-2,.,38,动态规划算法实例,?,匹配3错配-1空位-2,.,39,动态规划算法实例,匹配3错配-1空位-2,.,40,动态规划算法实例,匹配3错配-1空位-2,.,41,动态规划算法实例,匹配3错配-1空位-2,回溯,TA,C-,.,45,比对结果,1.ACTTCGAC-TAG2.ACTTCGACT-AG3.ACTTCGACTA-G,哪一个是最优比对(optimalalignment)呢?,记分矩阵,.,46,记分矩阵与空位罚分,DNA计分矩阵蛋白质计分矩阵广泛使用的两种矩阵PAMBLOSUM空位罚分,.,47,DNA计分矩阵,Sequence1Sequence2,AGCTA1000G0100C0010T0001,匹配:1错配:0分值：5,.,48,转换和颠换,表示转换(transition)，表示颠换(transversions)转换比颠换更容易发生,转换和颠换,转换速率是颠换3倍时的模型,蛋白质计分矩阵,PTHPLASKTQILPEDLASEDLTI,PTHPLAGERAIGLARLAEEDFGM,Sequence1Sequence2,记分矩阵,T:G=-2T:T=5Score=48,CSTPAGND.C9S-14T-115P-3-1-17A010-14G-30-2-206N-310-2-205D-30-1-1-2-116.,CSTPAGND.C9S-14T-115P-3-1-17A010-14G-30-2-206N-310-2-205D-30-1-1-2-116.,.,51,PAM(PercentAcceptedMutation)矩阵,氨基酸容易被其它生化、物理特性相似的氨基酸替换。PAM1(1个PAM单位）被定义为每100个残基出现一个被接受的点突变(氨基酸的置换不引起蛋白质功能上的显著变化）。PAMn是PAM1自乘n次。PAM250、PAM120、PAM80和PAM60矩阵可用于相似性分别为20%、40%、50%和60%的序列比对。,ARNDCQEGHILKMFPSTWYVBZA2-200-2001-1-1-2-1-1-3111-6-3021R-260-1-41-1-32-2-330-400-12-4-212N0022-41102-2-31-2-3010-4-2-243D0-124-52311-2-40-3-6-100-7-4-254C-2-4-4-512-5-5-3-3-2-6-5-5-4-30-2-80-2-3-4Q0112-542-13-2-21-1-50-1-1-5-4-235E0-113-52401-2-30-2-5-100-7-4-245G1-301-3-105-2-3-4-2-3-5010-7-5-121H-1221-331-26-2-20-2-20-1-1-30-233I-1-2-2-2-2-2-2-3-252-221-2-10-5-14-1-1L-2-3-3-4-6-2-3-4-226-342-3-3-2-2-12-2-1K-1310-510-20-2-350-5-100-3-4-222M-10-2-3-5-1-2-3-224060-2-2-1-4-22-10F-3-4-3-6-4-5-5-5-212-509-5-3-307-1-3-4P100-1-30-100-2-3-1-2-5610-6-5-111S10100-101-1-1-30-2-3121-2-3-121T1-100-2-100-10-20-1-3013-5-3021W-62-4-7-8-5-7-7-3-5-2-3-40-6-2-5170-6-4-4Y-3-4-2-40-4-4-50-1-1-4-27-5-3-3010-2-2-3V0-2-2-2-2-2-2-1-242-22-1-1-10-6-2400B2145-33423-1-22-1-3122-4-2065Z1234-45513-1-120-4111-4-3056,PAM250,模块替换矩阵BLOSUM以序列片段为基础,它是基于蛋白质模块(Block)数据库而建立起来的在模块比对的每一列中，分别计算两两氨基酸的变化情况,来自所有模块的数值被用来计算BLOSUM矩阵矩阵后面的数字表示构建此矩阵所用的序列的相似程度，如BLOSUM62表示由相似度为62%的序列构建,AACEC,A-C=0A-E=-1C-E=-4A-A=4C-C=9,AACEC,BLOSUM矩阵(BlocksSubstitutionMatrix),.,54,BLOSUM62,.,55,如何选择合适的评分矩阵？,一般来说,在局部相似性搜索上，BLOSUM矩阵较PAM要好当比较距离相近的蛋白时，应选择低的PAM或高的BLOSUM矩阵；当比较距离较远的蛋白时，应选择高的PAM或低的BLOSUM矩阵。对于数据库搜索来说一般选择BLOSUM62矩阵PAM矩阵可用于寻找蛋白质的进化起源，BLOSUM矩阵用于发现蛋白质的保守域,.,56,4.相似性与同源性,同源性(HomologousGenes)：序列来自共同的祖先，相似的序列往往具有同源性。相似性(Similarity)：两序列根据某种参数设定而表现出来的相近性。,.,57,相似性与同源性的区别,相似的序列并不一定同源；相似性是可以被量化的“计分表”，它是匹配的数量除以比对的长度，通常以百分比%表示；同源性一定是指序列来自共同的祖先；同源性是一个定性的概念，不能使用序列间具有百分之多少同源性来定义。,.,58,同源性分类,直系同源(Orthologs)：具有共同祖先与相似功能的同源基因（无基因复制事件）。旁系同源(Paralogs)：两个物种A和B的同源基因，分别是共同祖先基因组中由复制事件而产生的不同拷贝的后代。,.,59,Sothismeans,.,第二节多序列比对(MultipleAlignments),.,寻找蛋白质家族，识别多个序列的保守区域；相似的蛋白质序列往往具有相似的结构与功能；辅助预测新序列的二级或三级结构；可以直观地看到基因的哪些区域对突变敏感；PCR引物设计；,我们为什么做多序列比对?,.,分析多个序列的一致序列；用于进化分析，是用系统发育方法构建进化树的初使步骤；寻找个体之间单核苷酸多态性(SNPs)；通过序列比对发现直系同源(Orthologs)与旁系同源(Paralogs)基因；寻找同源基因(相似的序列往往具有同源性)。,我们为什么做多序列比对?,.,多序列比对与进化研究例子,图中NYLS为树根,.,一个多序列比对例子,VTISCTGSSSNIGAG-NHVKWYQQLPGVTISCTGTSSNIGS-ITVNWYQQLPGLRLSCSSSGFIFSS-YAMYWVRQAPGLSLTCTVSGTSFDD-YYSTWVRQPPGPEVTCVVVDVSHEDPQVKFNWYVDG-ATLVCLISDFYPGA-VTVAWKADS-AALGCLVKDYFPEP-VTVSWNSG-VSLTCLVKGFYPSD-IAVEWWSNG-,.,多序列比对方法,全局序列比对动态规划算法(DynamicProgrammingAlgorithm)分而治之方法(DivideandConquerMethods)SP方法(SumofPairsMethods)累进方法(ProgressiveMethods)迭代方法(IterativeMethods)局部序列比对概形分析(ProfileAnalysis)区块分析(BlockAnalysis)统计学方法(StatisticalMethods）,.,在多序列比对前要考虑的问题,比对的优劣与序列条数正相关每个亚群应分别先比对，然后再整体比对,.,一、全局序列比对,动态规划算法(DynamicProgrammingAlgorithm)分而治之方法(DivideandConquerMethods)SP方法(SumofPairsMethods)累进方法(ProgressiveMethods)迭代方法(IterativeMethods)遗传算法(GeneticAlgorithms),.,序列长度为n的双序列比对n2比对比对数目成指数增长例如：序列长度为n，序列数为N的多序列比对数目是nN对于数目较少且较短的序列来说都不切实际,1.动态规划算法(DynamicProgramming),.,Sequence1,Sequence2,Sequence3,多维的动态规划算法,.,分而治之(DivideandConquer,DCA)方法将MSA（MeasurementSystemAnalysis）的空间复杂度减小DCA在线MSAhttp:/bioweb.pasteur.fr/seqanal/interfaces/dca-simple.html,2.分而治之方法,.,Soineffect,Sequence1,Sequence2,Sequence3,.,3.SP(SumofPairs)方法,为了找到最佳比对，并解决动态规则算法的计算复杂问题，CarrilloB表示天冬氨酸or丙氨酸,.,用CLUSTALX进行Profile比对,.,2.区块分析,与概形分析相似，区块也代表MSA中的保守区；区块无插入与缺失，每一个位置只有匹配与错配；每一条序列中的同一区块具有相同的长度；BLOCKS数据库/。,.,MSA中的统计学方法(StatisticalMethods）,最大期望运算法则(ExpectationMaximizationAlgorithm,EM)吉布斯取样器(GibbsSampler)隐马尔可夫模型(HiddenMarkovModel,HMM)位置特异性记分矩阵(Position-SpecificScoringMatrix,PSSM)序列标语(SequenceLogo),.,最大期望运算法则,用来从未比对的蛋白序列中寻找保守功能域；从DNA序列中找蛋白质结合位点；通过EM算法找到的这些模体(Motif)允许空位的存在。,.,MEME(MultipleEMforMotifElicitation),MEME程序是由加州大学sanDiego分校的超级计算中心所创立。MEME的三种模体(Motif)模型：OOPS每条序列中预期出现一次motif；ZOOPS每条序列出现零次或一次motif；TCM每条序列中出现任意次数的motif。,.,基于Web的MEME软件,在线MEME工具：MEMEDiscovermotifs(highlyconservedregions)ingroupsofrelatedDNAorproteinsequences/meme/website/meme.htmlMASTSearchsequencedatabasesusingmotifs/meme/website/mast.html,.,MEME结果,.,隐马尔可夫