序列比对与算法和软件使用课件

序列比对与算法和软件使用序列比对与算法和软件使用2o第一节 双序列比对o第二节 多序列比对o第三节 常用序列比对软件的使用2第一节 双序列比对n第一节 双序列比对第一节 双序列比对4o1.序列比对基本概念o2.空位罚分o3.双序列比对方法n n点阵序列比较点阵序列比较点阵序列比较点阵序列比较(Dot Matrix Sequence(Dot Matrix Sequence Comparison)Comparison)n n动态规划算法动态规划算法动态规划算法动态规划算法(Dynamic Programming(Dynamic Programming Algorithm)Algorithm)o4.记分矩阵41.序列比对基本概念51.什么是序列比对？o序列比对序列比对(Sequence Alignment)是通过在序是通过在序列中搜索一系列单个性状或性状模式来比较列中搜索一系列单个性状或性状模式来比较2个（双序列比对）或更多（多重序列比对）个（双序列比对）或更多（多重序列比对）序列的方法。序列的方法。o按比对序列条数分类按比对序列条数分类n n双序列比对：两条序列的比对双序列比对：两条序列的比对双序列比对：两条序列的比对双序列比对：两条序列的比对n n多序列比对：三条或以上序列的比对多序列比对：三条或以上序列的比对多序列比对：三条或以上序列的比对多序列比对：三条或以上序列的比对51.什么是序列比对？序列比对(Sequence Ali61.我们为什么关注序列比对？o相似的序列可能具有相似的功能与结构；相似的序列可能具有相似的功能与结构；o发现一个基因或蛋白哪些区域容易发生突发现一个基因或蛋白哪些区域容易发生突变，哪些位点突变后对功能没有影响；变，哪些位点突变后对功能没有影响；o发现生物进化方面的信息。发现生物进化方面的信息。61.我们为什么关注序列比对？相似的序列可能具有相似的功能71.序列比对两种类型o全局序列比对全局序列比对全局序列比对全局序列比对n n定义：定义：定义：定义：在全局范围内对两条序列进行比对打分在全局范围内对两条序列进行比对打分在全局范围内对两条序列进行比对打分在全局范围内对两条序列进行比对打分的方法。的方法。的方法。的方法。n n适合于非常相似且长度近似相等的序列。适合于非常相似且长度近似相等的序列。适合于非常相似且长度近似相等的序列。适合于非常相似且长度近似相等的序列。o局部序列比对局部序列比对局部序列比对局部序列比对n n定义：定义：定义：定义：一种寻找匹配子序列的序列比对方法。一种寻找匹配子序列的序列比对方法。一种寻找匹配子序列的序列比对方法。一种寻找匹配子序列的序列比对方法。n n适合于一些片段相似而另一些片段相异的序列。适合于一些片段相似而另一些片段相异的序列。适合于一些片段相似而另一些片段相异的序列。适合于一些片段相似而另一些片段相异的序列。71.序列比对两种类型全局序列比对81.序列比对两种类型81.序列比对两种类型92.空位罚分(Gap Penalties)oo空位为了获得两个序列最佳比对，必须使用空位和空空位为了获得两个序列最佳比对，必须使用空位和空空位为了获得两个序列最佳比对，必须使用空位和空空位为了获得两个序列最佳比对，必须使用空位和空位罚分。位罚分。位罚分。位罚分。oo空位罚分分类：空位罚分分类：空位罚分分类：空位罚分分类：n n空位开放罚分空位开放罚分空位开放罚分空位开放罚分(Gap opening penalty)(Gap opening penalty)n n空位扩展罚分空位扩展罚分空位扩展罚分空位扩展罚分(Gap extension penalty)(Gap extension penalty)oo最优的序列比对通常具有以下两下特征：最优的序列比对通常具有以下两下特征：最优的序列比对通常具有以下两下特征：最优的序列比对通常具有以下两下特征：n n尽可能多的匹配尽可能多的匹配尽可能多的匹配尽可能多的匹配n n尽可能少的空位尽可能少的空位尽可能少的空位尽可能少的空位oo插入任意多的空位会产生较高的分数，但找到的并不插入任意多的空位会产生较高的分数，但找到的并不插入任意多的空位会产生较高的分数，但找到的并不插入任意多的空位会产生较高的分数，但找到的并不一定是真正相似序列。一定是真正相似序列。一定是真正相似序列。一定是真正相似序列。92.空位罚分(Gap Penalties)空位为了获得两101 GTGATAGACAC|1 GTGCATAGACAC2.空位罚分允许空位但不罚分不允许有空位 match=5mismatch=-41 GTG-ATAGACAC|1 GTGCATAGACAC1 GTG-ATAGACAC|1 GTGC-ATAGACAC?Score:-21Score:55101 GTGATAGACAC2.空位罚分允许空位但不罚分112.空位罚分公式 A T G T T A T A CT A T G T G C G T A T A Score=4参数:匹配匹配=1非匹配非匹配=0g=3r=0.1x=3score：8-3.2=4.8Wx=g+r(x-1)Wx:空位总记分g:空位开放罚分r:空位扩展罚分x:空位长度T A T G T G C G T A T A insertion/deletionA T G T-T A T A CWx=3+0.1*(3-1)=3.2112.空位罚分公式 A T G T T A T A C123.双序列比对方法o点阵序列比较(Dot Matrix Sequence Comparison)o动态规划算法(Dynamic Programming Algorithm)o词或K串方法(Word or K-tuple Methods)123.双序列比对方法点阵序列比较(Dot Matrix133.1 点阵序列比较o点点阵阵(Dot Matrix)分分析析是是一一种种简简单单的的图形显示序列相似性的方法。图形显示序列相似性的方法。o沿沿X轴轴上上序序列列1中中的的每每一一个个单单元元（核核苷苷酸酸或或氨氨基基酸酸）与与沿沿Y轴轴的的第第二二个个序序列列中中的的每每一一个个单单元元进进行行比比较较，相相同同的的区区域域在在点点阵阵图图中中显显示示为为由由点点组组成成的的对对角角线线，对对角角线线之外零散的点为背景噪音。之外零散的点为背景噪音。133.1 点阵序列比较点阵(Dot Matrix)分析是一IONIZATIONIONIZATIONIONIZATIONIONIZATION15点阵分析的应用o自身比对n寻找序列中的正向或反向重复序列n蛋白质的重复结构域(domain)n相同残基重复出现的低复杂区(Low Complexity)nRNA二级结构中的互补区域等o对两条序列的相似性作整体的估计15点阵分析的应用自身比对点阵分析中的插入或删除TACTGTCAT T A C T G T T C A TSequence 1Sequence 2T A C T G-T C A T|T A C T G T T C A T插入空位插入空位点阵分析中的插入或删除TSequence 1Sequence17点阵分析的应用人类低脂受体(human low-density lipoprotein receptor)自身比对发现正向重复序列具有连续相似区域的两条DNA序列的简单点阵图正向重复17点阵分析的应用人类低脂受体(human low-dens18点阵分析实例oo编编编编码码码码噬噬噬噬菌菌菌菌体体体体 c c（水水水水平平平平轴轴轴轴）和和和和噬噬噬噬菌菌菌菌体体体体P22 P22 c c2 2（垂垂垂垂直直直直轴轴轴轴）的的的的氨氨氨氨基基基基酸酸酸酸序序序序列列列列间的点阵分析间的点阵分析间的点阵分析间的点阵分析oo相相相相同同同同的的的的点点点点全全全全部部部部打打打打印印印印，很很很很难难难难找找找找到到到到有有有有用用用用的的的的信信信信息息息息18点阵分析实例编码噬菌体c（水平轴）和噬菌体P22 c19使用滑动窗口技术降低噪声T A C G G T A T G A C A G T A T CT A C G G T A T G A C A G T A T CT A C G G T A T G A C A G T A T CT A C G G T A T G A C A G T A T CC T A T G A C A T A C G G T A T GWindow=3 Word Size=319使用滑动窗口技术降低噪声T A C G G T A T 20ATACTACAAGACACGTACCGG C G A T G C A T T G A G T A T C A T AWindow size=5Stringency=3Match=1 Mismatch=020ATACTACAAGACACGTACCGG C 21ATACTACAAGACACGTACCGG C G A T G C A T T G A G T A T C A T AWindow size=5Stringency=3Match=1 Mismatch=021ATACTACAAGACACGTACCGG C 22ATACTACAAGACACGTACCGG C G A T G C A T T G A G T A T C A T AWindow size=5Stringency=3Match=1 Mismatch=022ATACTACAAGACACGTACCGG C 23G C G A T G C A T T G A G T A T C A T AATACTACAAGACACGTACCGWindow size=5Stringency=3Match=1 Mismatch=023G C G A T G C 24G C G A T G C A T T G A G T A T C A T AATACTACAAGACACGTACCG24G C G A T G C 25G C G A T G C A T T G A G T A T C A T AATACTACAAGACACGTACCG25G C G A T G C 使用滑动窗口技术降低噪声（a）对人类（Homo sapiens）与黑猩猩（Pongo pygmaeus）的球蛋白基因序列进行比较的完整点阵图（b）利用滑动窗口对以上的两种球蛋白基因序列进行比较的点阵图，其中窗口大小为10个核苷酸，相似度阈值为8，即10个核苷酸中有8个相同时就打一个点ab使用滑动窗口技术降低噪声（a）对人类（Homo sapien27点阵分析的优缺点o优点优点n n直观性，整体性；直观性，整体性；直观性，整体性；直观性，整体性；n n点阵分析不依赖空位点阵分析不依赖空位点阵分析不依赖空位点阵分析不依赖空位(gap)(gap)参数，可寻找两序列间参数，可寻找两序列间参数，可寻找两序列间参数，可寻找两序列间所有可能的残基匹配；所有可能的残基匹配；所有可能的残基匹配；所有可能的残基匹配；n n不依赖任何先决条件，是一种可用于初步分析的理不依赖任何先决条件，是一种可用于初步分析的理不依赖任何先决条件，是一种可用于初步分析的理不依赖任何先决条件，是一种可用于初步分析的理想工具；想工具；想工具；想工具；n n点阵分析允许随时动态地改变最高和最低界限值，点阵分析允许随时动态地改变最高和最低界限值，点阵分析允许随时动态地改变最高和最低界限值，点阵分析允许随时动态地改变最高和最低界限值，可以用来摸索区分信号和背景标准的严格程度。可以用来摸索区分信号和背景标准的严格程度。可以用来摸索区分信号和背景标准的严格程度。可以用来摸索区分信号和背景标准的严格程度。27点阵分析的优缺点优点28点阵分析的优缺点o缺点缺点n不能很好地兼容打分矩阵；不能很好地兼容打分矩阵；n滑动窗口和域值的选择过于经验化；滑动窗口和域值的选择过于经验化；n信噪比低；信噪比低；n不适合进行高通量的数据分析。不适合进行高通量的数据分析。28点阵分析的优缺点缺点29点阵分析程序oDNA Strider(Macintosh)nhttp:/oDotter(Unix/Linux,X-Windows)oCOMPARE,DOTPLOT(GCG软件)oPLALIGN(FASTA)oDotlet29点阵分析程序DNA Strider(Macintosh303.2 动态规划算法o动动动动态态态态规规规规划划划划算算算算法法法法(Dynamic(Dynamic Programming Programming Algorithm)Algorithm)是是是是一一一一种种种种计计计计算算算算方方方方法法法法，它它它它的的的的主主主主要要要要思思思思路路路路是是是是把把把把一一一一个个个个问问问问题题题题分分分分成成成成若干个小问题来解决。若干个小问题来解决。若干个小问题来解决。若干个小问题来解决。o在在在在生生生生物物物物学学学学中中中中应应应应用用用用的的的的两两两两种种种种动动动动态态态态规规规规划划划划算算算算法法法法：Needleman-Needleman-WunschWunsch算算算算法法法法（全全全全局局局局比比比比对对对对）和和和和Smith-WatermanSmith-Waterman算算算算法法法法（局部比对）。（局部比对）。（局部比对）。（局部比对）。303.2 动态规划算法动态规划算法(Dynamic Pro31序列比对中某一位点匹配的三种可能性序列比对中某一位点匹配的三种可能性oEg.匹配=1,非匹配=0,空位罚分=-1nSequence1:CACGAnSequence2:CGA第一个位点得分剩余序列CC+1ACGAGA-C-1CACGAGAC-1ACGACGA31序列比对中某一位点匹配的三种可能性Eg.匹配=1,非匹32动态规划算法的数学形式Sij=maxSi-1,j-1,+s(aibj),maxx1(Si-x,j-wx),maxy 1(Si,j-y-wy)Sij=maxSi-1,j-1,+s(aibj),maxx1(Si-1,j-wx),maxy 1(Si,j-1-wy)公式一的简化公式一公式二说明：Sij是序列a在位置i和序列b在位置j的分值，s(aibj)是位置i 和j上比对分值，wx是在序列a 中长度为x的间隔罚分，wy是序列b中长度为y的间隔罚分32动态规划算法的数学形式Sij=maxSi-1,j-1,33动态规划算法实例ACTTCGACTAG匹配3错配-1空位-233动态规划算法实例ACTTCGACTAG匹配334ACTTCG0ACTAG动态规划算法实例匹配3错配-1空位-234ACTTCG0ACTAG动态规划算法实例匹配335ACTTCG0-2ACTAG动态规划算法实例匹配3错配-1空位-235ACTTCG0-2ACTAG动态规划算法实例匹配336ACTTCG0-2-4-6-8-10-12ACTAG动态规划算法实例匹配3错配-1空位-236ACTTCG0-2-4-6-8-10-12ACTAG 动态37ACTTCG0-2-4-6-8-10-12A-2CTAG动态规划算法实例匹配3错配-1空位-237ACTTCG0-2-4-6-8-10-12A-2CTAG38ACTTCG0-2-4-6-8-10-12A-2C-4T-6A-8G-10动态规划算法实例?S(2,2)-2+(-2)-2+(-2)0+3匹配3错配-1空位-238ACTTCG0-2-4-6-8-10-12A-2C-4T39ACTTCG0-2-4-6-8-10-12A-23C-4T-6A-8G-10动态规划算法实例?S(2,3)-4+(-2)3+(-2)-2+(-1)匹配3错配-1空位-239ACTTCG0-2-4-6-8-10-12A-23C-440动态规划算法实例ACTTCG0-2-4-6-8-10-12A-231C-4T-6A-8G-10匹配3错配-1空位-240动态规划算法实例ACTTCG0-2-4-6-8-10-141动态规划算法实例ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-14?A-8-3 2G-10-50S(4,4)4+(-2)4+(-2)6+3匹配3错配-1空位-241动态规划算法实例ACTTCG0-2-4-6-8-10-142动态规划算法实例ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149A-8-3 2G-10-50匹配3错配-1空位-242动态规划算法实例ACTTCG0-2-4-6-8-10-1ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 27864G-10-505679GGT-CATTCCAA回回 溯溯ACTTCG0-2-4-6-8-10-12A-231-1-3ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 27864G-10-505679GGT-CATTCCAAACTTCG0-2-4-6-8-10-12A-231-1-3ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 27864G-10-505679GGTAC-TTCCAAACTTCG0-2-4-6-8-10-12A-231-1-346比对结果1.ACTTCGAC-TAG2.ACTTCGACT-AG3.ACTTCGACTA-G哪一个是最优比对哪一个是最优比对(optimal alignment)呢呢?记分矩阵46比对结果1.ACTTCG哪一个是最优比对(optim47记分矩阵与空位罚分oDNA计分矩阵o蛋白质计分矩阵o广泛使用的两种矩阵n PAM n BLOSUMo空位罚分47记分矩阵与空位罚分DNA计分矩阵48DNA计分矩阵actaccagttcatttgatacttctcaaataccattaccgtgttaactgaaaggacttaaagactSequence 1Sequence 2AGCTA1000G0100C0010T0001匹配:1错配:0分值：548DNA计分矩阵actaccagttcatttgatact49转换和颠换CTAG嘧啶嘌呤o 表示转换(transition)，表示颠换(transversions)o转换比颠换更容易发生49转换和颠换CTAG嘧啶嘌呤 表示转换(tr转换和颠换AGTCA0.99G0.0060.99T0.0020.0020.99C0.0020.0020.0060.99转换速率是颠换3倍时的模型转换和颠换AGTCA0.99G0.0060.99T0.002蛋白质计分矩阵PTHPLASKTQILPEDLASEDLTIPTHPLAGERAIGLARLAEEDFGMSequence 1Sequence 2记分矩阵T:G=-2 T:T=5Score=48 CSTPAGND.C 9S-1 4T-1 1 5P-3-1-1 7A 0 1 0-1 4G-3 0-2-2 0 6N-3 1 0-2-2 0 5D-3 0-1-1-2-1 1 6 .CSTPAGND.C 9S-1 4T-1 1 5P-3-1-1 7A 0 1 0-1 4G-3 0-2-2 0 6N-3 1 0-2-2 0 5D-3 0-1-1-2-1 1 6 .蛋白质计分矩阵PTHPLASKTQILPEDLASEDLTI52PAM(Percent Accepted Mutation)矩阵oo氨基酸容易被其它生化、物理特性相似的氨基酸替换。氨基酸容易被其它生化、物理特性相似的氨基酸替换。氨基酸容易被其它生化、物理特性相似的氨基酸替换。氨基酸容易被其它生化、物理特性相似的氨基酸替换。ooPAM1(1PAM1(1个个个个PAMPAM单位）被定义为每单位）被定义为每单位）被定义为每单位）被定义为每100100个残基出现一个个残基出现一个个残基出现一个个残基出现一个被接受的点突变被接受的点突变被接受的点突变被接受的点突变(氨基酸的置换不引起蛋白质功能上的显著氨基酸的置换不引起蛋白质功能上的显著氨基酸的置换不引起蛋白质功能上的显著氨基酸的置换不引起蛋白质功能上的显著变化）。变化）。变化）。变化）。ooPAMnPAMn是是是是PAM1PAM1自乘自乘自乘自乘n n次。次。次。次。ooPAM250PAM250、PAM120PAM120、PAM80PAM80和和和和PAM60PAM60矩阵可用于相矩阵可用于相矩阵可用于相矩阵可用于相似性分别为似性分别为似性分别为似性分别为20%20%、40%40%、50%50%和和和和60%60%的序列比对。的序列比对。的序列比对。的序列比对。52PAM(Percent Accepted Mutati A R N D C Q E G H I L K M F P S T W Y V B ZA 2-2 0 0-2 0 0 1-1-1-2-1-1-3 1 1 1-6-3 0 2 1 R -2 6 0-1-4 1-1-3 2-2-3 3 0-4 0 0-1 2-4-2 1 2 N 0 0 2 2-4 1 1 0 2-2-3 1-2-3 0 1 0-4-2-2 4 3 D 0-1 2 4-5 2 3 1 1-2-4 0-3-6-1 0 0-7-4-2 5 4 C -2-4-4-5 12-5-5-3-3-2-6-5-5-4-3 0-2-8 0-2-3-4 Q 0 1 1 2-5 4 2-1 3-2-2 1-1-5 0-1-1-5-4-2 3 5 E 0-1 1 3-5 2 4 0 1-2-3 0-2-5-1 0 0-7-4-2 4 5 G 1-3 0 1-3-1 0 5-2-3-4-2-3-5 0 1 0-7-5-1 2 1 H -1 2 2 1-3 3 1-2 6-2-2 0-2-2 0-1-1-3 0-2 3 3 I -1-2-2-2-2-2-2-3-2 5 2-2 2 1-2-1 0-5-1 4-1-1 L -2-3-3-4-6-2-3-4-2 2 6-3 4 2-3-3-2-2-1 2-2-1 K -1 3 1 0-5 1 0-2 0-2-3 5 0-5-1 0 0-3-4-2 2 2 M -1 0-2-3-5-1-2-3-2 2 4 0 6 0-2-2-1-4-2 2-1 0 F -3-4-3-6-4-5-5-5-2 1 2-5 0 9-5-3-3 0 7-1-3-4 P 1 0 0-1-3 0-1 0 0-2-3-1-2-5 6 1 0-6-5-1 1 1 S 1 0 1 0 0-1 0 1-1-1-3 0-2-3 1 2 1-2-3-1 2 1 T 1-1 0 0-2-1 0 0-1 0-2 0-1-3 0 1 3-5-3 0 2 1 W -6 2-4-7-8-5-7-7-3-5-2-3-4 0-6-2-5 17 0-6-4-4 Y -3-4-2-4 0-4-4-5 0-1-1-4-2 7-5-3-3 0 10-2-2-3 V 0-2-2-2-2-2-2-1-2 4 2-2 2-1-1-1 0-6-2 4 0 0 B 2 1 4 5-3 3 4 2 3-1-2 2-1-3 1 2 2-4-2 0 6 5 Z 1 2 3 4-4 5 5 1 3-1-1 2 0-4 1 1 1-4-3 0 5 6 PAM 250PAM 250 o模块替换矩阵BLOSUM以序列片段为基础,它是 基于蛋白质模块(Block)数据库而建立起来的 o 在模块比对的每一列中，分别计算 两两氨基酸的变化情况,来自所有 模块的数值被用来计算BLOSUM矩阵o矩阵后面的数字表示构建此矩阵所用的 序列的相似程度，如BLOSUM62表示由 相似度为62%的序列构建AACECA-C =0A-E =-1C-E =-4A-A =4C-C =9AACECBLOSUM矩阵(Blocks Substitution Matrix)模块替换矩阵BLOSUM以序列片段为基础,它是 基于55BLOSUM62 55BLOSUM62 56如何选择合适的评分矩阵？oo 一般来说一般来说一般来说一般来说,在局部相似性搜索上，在局部相似性搜索上，在局部相似性搜索上，在局部相似性搜索上，BLOSUM BLOSUM 矩阵较矩阵较矩阵较矩阵较PAMPAM要好要好要好要好oo当比较距离相近的蛋白时，应选择低的当比较距离相近的蛋白时，应选择低的当比较距离相近的蛋白时，应选择低的当比较距离相近的蛋白时，应选择低的PAMPAM或高的或高的或高的或高的BLOSUMBLOSUM矩阵；当比较距离较远的蛋白时，应选择高的矩阵；当比较距离较远的蛋白时，应选择高的矩阵；当比较距离较远的蛋白时，应选择高的矩阵；当比较距离较远的蛋白时，应选择高的PAMPAM或低的或低的或低的或低的BLOSUMBLOSUM矩阵。矩阵。矩阵。矩阵。oo 对于数据库搜索来说一般选择对于数据库搜索来说一般选择对于数据库搜索来说一般选择对于数据库搜索来说一般选择BLOSUM62BLOSUM62矩阵矩阵矩阵矩阵ooPAMPAM矩阵可用于寻找蛋白质的进化起源，矩阵可用于寻找蛋白质的进化起源，矩阵可用于寻找蛋白质的进化起源，矩阵可用于寻找蛋白质的进化起源，BLOSUMBLOSUM矩阵用于矩阵用于矩阵用于矩阵用于发现蛋白质的保守域发现蛋白质的保守域发现蛋白质的保守域发现蛋白质的保守域56如何选择合适的评分矩阵？一般来说,在局部相似性搜索上，574.相似性与同源性n同同源源性性(Homologous Genes)：序序列列来来自自共共同同的的祖祖先先，相相似似的的序序列列往往往往具具有有同同源源性。性。n相相似似性性(Similarity)：两两序序列列根根据据某某种种参参数设定而表现出来的相近性。数设定而表现出来的相近性。574.相似性与同源性同源性(Homologous Gen58相似性与同源性的区别o相似的序列并不一定同源；相似的序列并不一定同源；o相相似似性性是是可可以以被被量量化化的的“计计分分表表”，它它是是匹匹配配的的数数量量除除以以比比对对的的长长度度，通通常常以以百百分分比比%表示；表示；o同源性一定是指同源性一定是指序列来自共同的祖先；序列来自共同的祖先；o同同源源性性是是一一个个定定性性的的概概念念，不不能能使使用用序序列列间具有百分之多少同源性来定义。间具有百分之多少同源性来定义。58相似性与同源性的区别相似的序列并不一定同源；59同源性分类n直直直直系系系系同同同同源源源源(Orthologs)(Orthologs)：具具具具有有有有共共共共同同同同祖祖祖祖先先先先与与与与相似功能的同源基因（无基因复制事件）。相似功能的同源基因（无基因复制事件）。相似功能的同源基因（无基因复制事件）。相似功能的同源基因（无基因复制事件）。n旁旁旁旁系系系系同同同同源源源源(Paralogs)(Paralogs)：两两两两个个个个物物物物种种种种AA和和和和BB的的的的同同同同源源源源基基基基因因因因，分分分分别别别别是是是是共共共共同同同同祖祖祖祖先先先先基基基基因因因因组组组组中中中中由由由由复复复复制制制制事件而产生的不同拷贝的后代。事件而产生的不同拷贝的后代。事件而产生的不同拷贝的后代。事件而产生的不同拷贝的后代。59同源性分类直系同源(Orthologs)：具有共同祖先与60So this means 60So this means 第二节 多序列比对 (Multiple Alignments)第二节 多序列比对 (Multiple o寻找蛋白质家族，识别多个序列的保守区域；o相似的蛋白质序列往往具有相似的结构与功能；o辅助预测新序列的二级或三级结构；o可以直观地看到基因的哪些区域对突变敏感；oPCR引物设计；我们为什么做多序列比对?寻找蛋白质家族，识别多个序列的保守区域；我们为什么做多序列比o分析多个序列的一致序列；o用于进化分析，是用系统发育方法构建进化树的初使步骤；o寻找个体之间单核苷酸多态性(SNPs)；o通过序列比对发现直系同源(Orthologs)与旁系同源(Paralogs)基因；o寻找同源基因(相似的序列往往具有同源性)。我们为什么做多序列比对?分析多个序列的一致序列；我们为什么做多序列比对?多序列比对与进化研究例子图中NYLS为树根多序列比对与进化研究例子图中NYLS为树根一个多序列比对例子VTISCTGSSSNIGAG-NHVKWYQQLPGVTISCTGTSSNIGS-ITVNWYQQLPGLRLSCSSSGFIFSS-YAMYWVRQAPGLSLTCTVSGTSFDD-YYSTWVRQPPGPEVTCVVVDVSHEDPQVKFNWYVDG-ATLVCLISDFYPGA-VTVAWKADS-AALGCLVKDYFPEP-VTVSWNSG-VSLTCLVKGFYPSD-IAVEWWSNG-一个多序列比对例子VTISCTGSSSNIGAG-NHVKW多序列比对方法全局序列比对全局序列比对动态规划算法 (Dynamic Programming Algorithm)分而治之方法 (Divide and Conquer Methods)SP方法 (Sum of Pairs Methods)累进方法 (Progressive Methods)迭代方法 (Iterative Methods)局部序列比对局部序列比对概形分析 (Pro)区块分析 (Block Analysis)统计学方法统计学方法 (Statistical Methods）多序列比对方法全局序列比对在多序列比对前要考虑的问题o比对的优劣与序列条数正相关比对的优劣与序列条数正相关比对的优劣与序列条数正相关比对的优劣与序列条数正相关o每个亚群应分别先比对，然后再整体比对每个亚群应分别先比对，然后再整体比对每个亚群应分别先比对，然后再整体比对每个亚群应分别先比对，然后再整体比对在多序列比对前要考虑的问题比对的优劣与序列条数正相关一、全局序列比对动态规划算法(Dynamic Programming Algorithm)分而治之方法(Divide and Conquer Methods)SP方法(Sum of Pairs Methods)累进方法(Progressive Methods)迭代方法(Iterative Methods)遗传算法(Genetic Algorithms)一、全局序列比对动态规划算法(Dynamic Progro序列长度为序列长度为 n 的双序列比对的双序列比对nn2 比对比对o比对数目成指数增长比对数目成指数增长n例如：序列长度为例如：序列长度为n，序列数为，序列数为N 的多序列比对数目的多序列比对数目是是nNo对于数目较少且较短的序列来说都不切实际对于数目较少且较短的序列来说都不切实际1.动态规划算法(Dynamic Programming)1.动态规划算法(Dynamic Programming)Sequence 1Sequence 2Sequence 3多维的动态规划算法Sequence 1Sequence 2Sequence 3分而治之分而治之(Divide and Conquer,DCA)方法方法将MSA（Measurement System Analysis）的空间复杂度减小DCA在线MSA2.分而治之方法分而治之(Divide and Conquer,DCA)So in effect Sequence 1Sequence 2Sequence 3So in effect Sequence 1Sequen3.SP(Sum of Pairs)方法oo为了找到最佳比对，并解决动态规则算法的计算复为了找到最佳比对，并解决动态规则算法的计算复为了找到最佳比对，并解决动态规则算法的计算复为了找到最佳比对，并解决动态规则算法的计算复杂问题，杂问题，杂问题，杂问题，Carrillo&Lipman(1988)Carrillo&Lipman(1988)发明了发明了发明了发明了SP(Sum SP(Sum of Pairs)of Pairs)方法方法方法方法ooSPSP方法通过对一个随机数据矩阵中氨基酸对的所方法通过对一个随机数据矩阵中氨基酸对的所方法通过对一个随机数据矩阵中氨基酸对的所方法通过对一个随机数据矩阵中氨基酸对的所有可能组合的记分求和来获得矩阵记分有可能组合的记分求和来获得矩阵记分有可能组合的记分求和来获得矩阵记分有可能组合的记分求和来获得矩阵记分3.SP(Sum of Pairs)方法为了找到最佳比对，4.累进算法(Progressive Methods)o针对基于动态规划算法的MSA程序比对序列数目有限，Feng&Doolittle(1987)发明了累进算法oCLUSTAL 和 PILEUP 是目前常用的基于累进算法的比对软件oCLUSTAL 是免费软件,目前应用非常广泛 igbmc.u-strasbg.fr/BioInfo/ClustalX/Top.html4.累进算法(Progressive Methods)针对1 对所有序列做双序列比对，构建距离矩阵计算相似性分数值2 基于双序列距离矩阵，构建一个进化树 Scer Cele Dmel MouseHuman3 依据进化树进行渐进比对 依据进化树，开始对关系较 近的序列进行两两比对 逐渐加入关系较远的序列进行比对 构建多序列比对Multiple alignmentScerevisiae 1Celegans 2 0.640Drosophia 3 0.634 0.327Human 4 0.630 0.408 0.420Mouse 5 0.619 0.405 0.469 0.289累进算法原理1 对所有序列做双序列比对，构建距离矩阵计算相似性分数值2 一般累进比对方法132513131325254droot一般累进比对方法132513131325254droot果仁糖累进方法(Praline progressive strategy)13213131325254d4果仁糖累进方法(Praline progressive s累进算法的一些问题o比对的准确性高度依赖于开始选择的双序列比对o序列关系越远发生的错误可能越高o选择合适的打分矩阵和罚分准则较困难累进算法的一些问题比对的准确性高度依赖于开始选择的双序列比对ClLUSTALW/X简介ooClLUSTALClLUSTAL最初初由最初初由最初初由最初初由HigginsHiggins等于等于等于等于19881988年创立并不断完善年创立并不断完善年创立并不断完善年创立并不断完善 oo用来多序列比对、概形用来多序列比对、概形用来多序列比对、概形用来多序列比对、概形(Profile)(Profile)分析和创建进化树分析和创建进化树分析和创建进化树分析和创建进化树ooClLUSTALClLUSTAL分为分为分为分为ClLUSTALWClLUSTALW和和和和CLUSTALXCLUSTALX两种类型两种类型两种类型两种类型ooClLUSTALClLUSTAL有用于有用于有用于有用于WINDOWSWINDOWS和和和和UNIX/LINUXUNIX/LINUX的各种版本的各种版本的各种版本的各种版本ClLUSTALW/X简介ClLUSTAL最初初由HiggiCLUSTAL方法oo进行所有序列间的双序列比对进行所有序列间的双序列比对进行所有序列间的双序列比对进行所有序列间的双序列比对oo基于双序列比对分数产生一个相邻连接进化树基于双序列比对分数产生一个相邻连接进化树基于双序列比对分数产生一个相邻连接进化树基于双序列比对分数产生一个相邻连接进化树(neighbor-join tree)(neighbor-join tree)oo根据进化树提供的序列间关系按顺序对序列进行比对根据进化树提供的序列间关系按顺序对序列进行比对根据进化树提供的序列间关系按顺序对序列进行比对根据进化树提供的序列间关系按顺序对序列进行比对oo比对可以用以下两种方法：比对可以用以下两种方法：比对可以用以下两种方法：比对可以用以下两种方法：n n-slow/accurate-slow/accurate n n-fast/approximate-fast/approximateCLUSTAL方法进行所有序列间的双序列比对*CLUSTAL W(1.8)Multiple Sequence Alignments*1.Sequence Input From Disc2.Multiple Alignments 3.Profile/Structure Alignments 4.Phylogenetic trees S.Execute a system command H.HELP X.EXIT(leave program)Your choice:1CLUSTAL W*CLUSTAL W(1.8)MultiSequences should all be in 1 file.7 formats accepted:NBRF/PIR,EMBL/SwissProt,Pearson(Fasta),GDE,Clustal,GCG/MSF,RSF.Enter the name of the sequence file:anti.fasta Sequence format is Pearson Sequences assumed to be PROTEIN Sequence 1:ANP4_PSEAM85 aa Sequence 2:ANP_LIMFE97 aa Sequence 3:ANPA_PSEAM82 aa Sequence 4:ANPX_PSEAM91 aa Sequence 5:ANPY_PSEAM91 aa CLUSTAL WSequences should all be in 1 f*CLUSTAL W(1.8)Multiple Sequence Alignments*1.Sequence Input From Disc 2.Multiple Alignments 3.Profile/Structure Alignments 4.Phylogenetic trees S.Execute a system command H.HELP X.EXIT(leave program)Your choice:2 CLUSTAL W*CLUSTAL W(1.8)MultiClustal W*MULTIPLE ALIGNMENT MENU*1.Do complete multiple alignment now(Slow/Accurate)2.Produce guide tree 3.Do alignment using old guide tree file 4.Toggle Slow/Fast pairwise alignments=SLOW 5.Pairwise alignment parameters 6.Multiple alignment parameters 7.Reset gaps between alignments?=OFF 8.Toggle screen display =ON 9.Output format options S.Execute a system command H.HELP or press RETURN to go back to main menuYour choice:1 Clustal WEnter a name for the CLUSTAL output file anti.aln:Enter name for new GUIDE TREE file anti.dnd:Start of Pairwise alignments Aligning.Sequences(1:2)Aligned.Score:62 Sequences(1:3)Aligned.Score:59 Sequences(1:4)Aligned.Score:84 Sequences(1:5)Aligned.Score:83 Sequences(2:3)Aligned.Score:68 Sequences(2:4)Aligned.Score:80 Sequences(2:5)Aligned.Score:79 Sequences(3:4)Aligned.Score:81 Sequences(3:5)Aligned.Score:80 Sequences(4:5)Aligned.Score:98 Guide tree:anti.dnd Start of Multiple Alignment There are 4 groups Aligning.Group 1:Sequences:2 Score:1476 Group 2:Sequences:3 Score:1499 Group 3:Sequences:4 Score:1190 Group 4:Sequences:5 Score:1404 Alignment Score 3470 Consensus length=102 CLUSTAL-Alignment anti.aln Enter a name for the CLUSTAL oMac Vector界面的Clustal WMac Vector界面的Clustal WClustal X介绍Clustal X介绍ClustalX介绍ClustalX介绍ClustalX介绍ClustalX介绍ClustalX介绍ClustalX介绍ClustalX介绍ClustalX介绍ExampleMultiple sequence alignment of 7 neuroglobins using clustalxExampleMultiple sequence alignPILEUPooP PILEUPILEUP是是是是GCG(Genetics Computer Group)GCG(Genetics Computer Group)软件包中软件包中软件包中软件包中的的的的MSAMSA分析工具；分析工具；分析工具；分析工具；oo与与与与CLUSTALCLUSTAL一样使用累进式整体比对方法一样使用累进式整体比对方法一样使用累进式整体比对方法一样使用累进式整体比对方法(Progressive Global Alignment)(Progressive Global Alignment)；ooPILEUPPILEUP开始的双序列比对使用开始的双序列比对使用开始的双序列比对使用开始的双序列比对使用Needleman-WunschNeedleman-Wunsch动动动动态规划算法，所以是全局序列比对，善于比较相似度态规划算法，所以是全局序列比对，善于比较相似度态规划算法，所以是全局序列比对，善于比较相似度态规划算法，所以是全局序列比对，善于比较相似度较高的序列。较高的序列。较高的序列。较高的序列。PILEUPPILEUP是GCG(Genetics CompOutput of Pileup 401 OATNFA1 TTCAG.ACACTCAGG TCATCTTCTC AAGC OATNFAR TTCAG.ACACTCAGG TCATCTTCTC AAGC BSPTNFA TTCAA.ACACTCAGG TCCTCTTCTC AAGC CEU14683 TTCAG.ACCCTCAGG TCATCTTCTC AAGC HSTNFR CCCAG.GCAGTCAGA TCATCTTCTC GAACSYNTNFTRP CCCAG.GCAGTCAGA TCATCTTCTC GAAC CATTNFAA CCCAG.ACACTCAGA TCATCTTCTC GAAC CFTNFA TCCAG.ACAGTCAAA TCATCTTCTC GAAC RABTNFM CCCAGATGGT CACCCTCAGA TCAGCTTCTC GGGC RNTNFAA CCCAGACCCT CACACTCAGA TCATCTTCTC AAAAOutput of Pileup 401 Output of PileupOutput of PileupClUSTAL和PILEUP存在的问题o最终的比对结果取决于最初的双序列比对，最终的比对结果取决于最初的双序列比对，最终的比对结果取决于最初的双序列比对，最终的比对结果取决于最初的双序列比对，起初的序列相似度越高比对越准确；起初的序列相似度越高比对越准确；起初的序列相似度越高比对越准确；起初的序列相似度越高比对越准确；o如果比对序列间长度差异较大则会生成异常如果比对序列间长度差异较大则会生成异常如果比对序列间长度差异较大则会生成异常如果比对序列间长度差异较大则会生成异常的引导树的引导树的引导树的引导树(guide guide trees)trees)从而严重影响多序列比从而严重影响多序列比从而严重影响多序列比从而严重影响多序列比对；对；对；对；o所选的记分与罚分标准并不一定适合一组序所选的记分与罚分标准并不一定适合一组序所选的记分与罚分标准并不一定适合一组序所选的记分与罚分标准并不一定适合一组序列中的所有序列。列中的所有序列。列中的所有序列。列中的所有序列。ClUSTAL和PILEUP存在的问题最终的比对结果取决于最o对累进比对方法的改进对累进比对方法的改进o迭代方法策略迭代方法策略n在比对过程中不断重新比对各亚组序列在比对过程中不断重新比对各亚组序列n把亚组序列再排成包括所有序列在内的整把亚组序列再排成包括所有序列在内的整体比对体比对n获得最优的总比对分数（由成对比对分数获得最优的总比对分数（由成对比对分数相加而成）相加而成）5.迭代方法(Iterative Methods)对累进比对方法的改进5.迭代方法(Iterative M二、局部序列比对局部比对局部比对(Local Alignment)方法能够确定方法能够确定序列中高度保守的区域。序列中高度保守的区域。u概形分析概形分析概形分析概形分析 (Pro)u区块分析区块分析区块分析区块分析 (Block Analysis)二、局部序列比对局部比对(Local Alignment)方1.概形分析(Pro)oo通通通通过过过过对对对对一一一一组组组组序序序序列列列列进进进进行行行行整整整整体体体体MSAMSA分分分分析析析析，把把把把其其其其中中中中高高高高度度度度保保保保守守守守的的的的区区区区域提出分成小的域提出分成小的域提出分成小的域提出分成小的MSAMSA。oo这些小的这些小的这些小的这些小的MSAMSA根据其序列与结构的比对得到一个记分矩阵。根据其序列与结构的比对得到一个记分矩阵。根据其序列与结构的比对得到一个记分矩阵。根据其序列与结构的比对得到一个记分矩阵。oo根根根根据据据据这这这这个个个个矩矩矩矩阵阵阵阵列列列列出出出出每每每每个个个个位位位位置置置置上上上上的的的的残残残残基基基基分分分分数数数数，称称称称为为为为位位位位置置置置特特特特异异异异记分表记分表记分表记分表(Position Specific Scoring Table)(Position Specific Scoring Table)或概形或概形或概形或概形(Profile)(Profile)。oo概概概概形形形形(Profile)(Profile)类类类类似似似似于于于于一一一一个个个个小小小小的的的的MSAMSA，包包包包括括括括匹匹匹匹配配配配、错错错错配配配配、插插插插入入入入和缺失。和缺失。和缺失。和缺失。1.概形分析(Pro)通过对一组序列进行整体MSA分析，概形分析(Pro)oo优势：优势：优势：优势：n n用来寻找一个可能与之匹配的目标序列；用来寻找一个可能与之匹配的目标序列；用来寻找一个可能与之匹配的目标序列；用来寻找一个可能与之匹配的目标序列；n n用用用用来来来来在在在在一一一一个个个个数数数数据据据据库库库库中中中中搜搜搜搜索索索索一一一一个个个个可可可可能能能能的的的的新新新新的