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

《第四章序列比对与算法PPT课件》由会员分享，可在线阅读，更多相关《第四章序列比对与算法PPT课件（115页珍藏版）》请在金锄头文库上搜索。

1、第四章 序列比对与算法o第一节 双序列比对o第二节 多序列比对o第三节 常用序列比对软件的使用1n第一节 双序列比对2o1. 序列比对基本概念o2. 空位罚分o3. 双序列比对方法n n点阵序列比较点阵序列比较点阵序列比较点阵序列比较(Dot Matrix Sequence (Dot Matrix Sequence Comparison)Comparison)n n动态规划算法动态规划算法动态规划算法动态规划算法(Dynamic Programming (Dynamic Programming Algorithm)Algorithm)o4. 记分矩阵31. 什么是序列比对？o序列比对序列比对(

2、Sequence Alignment)是通过在序是通过在序列中搜索一系列单个性状或性状模式来比较列中搜索一系列单个性状或性状模式来比较2个（双序列比对）或更多（多重序列比对）个（双序列比对）或更多（多重序列比对）序列的方法。序列的方法。o按比对序列条数分类按比对序列条数分类n n双序列比对：两条序列的比对双序列比对：两条序列的比对双序列比对：两条序列的比对双序列比对：两条序列的比对n n多序列比对：三条或以上序列的比对多序列比对：三条或以上序列的比对多序列比对：三条或以上序列的比对多序列比对：三条或以上序列的比对41. 我们为什么关注序列比对？o相似的序列可能具有相似的功能与结构；相似的序列可

3、能具有相似的功能与结构；o发现一个基因或蛋白哪些区域容易发生突发现一个基因或蛋白哪些区域容易发生突变，哪些位点突变后对功能没有影响；变，哪些位点突变后对功能没有影响；o发现生物进化方面的信息。发现生物进化方面的信息。51. 序列比对两种类型o全局序列比对全局序列比对全局序列比对全局序列比对l l定义：定义：定义：定义：在全局范围内对两条序列进行比对打分在全局范围内对两条序列进行比对打分在全局范围内对两条序列进行比对打分在全局范围内对两条序列进行比对打分的方法。的方法。的方法。的方法。l l适合于非常相似且长度近似相等的序列。适合于非常相似且长度近似相等的序列。适合于非常相似且长度近似相等的序列

4、。适合于非常相似且长度近似相等的序列。o局部序列比对局部序列比对局部序列比对局部序列比对l l定义：定义：定义：定义：一种寻找匹配子序列的序列比对方法。一种寻找匹配子序列的序列比对方法。一种寻找匹配子序列的序列比对方法。一种寻找匹配子序列的序列比对方法。l l适合于一些片段相似而另一些片段相异的序列。适合于一些片段相似而另一些片段相异的序列。适合于一些片段相似而另一些片段相异的序列。适合于一些片段相似而另一些片段相异的序列。61. 序列比对两种类型72. 空位罚分(Gap Penalties)oo空位为了获得两个序列最佳比对，必须使用空位和空空位为了获得两个序列最佳比对，必须使用空位和空空位为

5、了获得两个序列最佳比对，必须使用空位和空空位为了获得两个序列最佳比对，必须使用空位和空位罚分。位罚分。位罚分。位罚分。oo空位罚分分类：空位罚分分类：空位罚分分类：空位罚分分类：n n空位开放罚分空位开放罚分空位开放罚分空位开放罚分(Gap opening penalty)(Gap opening penalty)n n空位扩展罚分空位扩展罚分空位扩展罚分空位扩展罚分(Gap extension penalty)(Gap extension penalty)oo最优的序列比对通常具有以下两下特征：最优的序列比对通常具有以下两下特征：最优的序列比对通常具有以下两下特征：最优的序列比对通常具有以下

6、两下特征：n n尽可能多的匹配尽可能多的匹配尽可能多的匹配尽可能多的匹配n n尽可能少的空位尽可能少的空位尽可能少的空位尽可能少的空位oo插入任意多的空位会产生较高的分数，但找到的并不插入任意多的空位会产生较高的分数，但找到的并不插入任意多的空位会产生较高的分数，但找到的并不插入任意多的空位会产生较高的分数，但找到的并不一定是真正相似序列。一定是真正相似序列。一定是真正相似序列。一定是真正相似序列。81 GTGATAGACAC | 1 GTGCATAGACAC2. 空位罚分允许空位但不罚分不允许有空位 match = 5mismatch = -41 GTG-ATAGACAC | |1 GTGC

7、ATAGACAC1 GTG-ATAGACAC | |1 GTGC-ATAGACAC?Score: -21Score: 5592. 空位罚分公式 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)

8、 = 3.2103. 双序列比对方法o点阵序列比较 (Dot Matrix Sequence Comparison)o动态规划算法 (Dynamic Programming Algorithm)o词或K串方法 (Word or K-tuple Methods)113.1 点阵序列比较o点点阵阵(Dot Matrix)分分析析是是一一种种简简单单的的图形显示序列相似性的方法。图形显示序列相似性的方法。o沿沿X轴轴上上序序列列1中中的的每每一一个个单单元元（核核苷苷酸酸或或氨氨基基酸酸）与与沿沿Y轴轴的的第第二二个个序序列列中中的的每每一一个个单单元元进进行行比比较较，相相同同的的区区域域在在点点

9、阵阵图图中中显显示示为为由由点点组组成成的的对对角角线线，对对角角线线之外零散的点为背景噪音。之外零散的点为背景噪音。12IONIZATIONIONIZATION13点阵分析的应用o自身比对n寻找序列中的正向或反向重复序列n蛋白质的重复结构域(domain)n相同残基重复出现的低复杂区(Low Complexity)nRNA二级结构中的互补区域等o对两条序列的相似性作整体的估计14点阵分析中的插入或删除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

10、T C A T插入空位插入空位15点阵分析的应用人类低脂受体(human low-density lipoprotein receptor)自身比对发现正向重复序列具有连续相似区域的两条DNA序列的简单点阵图正向重复16点阵分析实例oo编编编编码码码码噬噬噬噬菌菌菌菌体体体体 c c（水水水水平平平平轴轴）和和和和噬噬噬噬菌菌菌菌体体体体P22 P22 c c2 2（垂垂垂垂直直直直轴轴轴轴）的的的的氨氨氨氨基基基基酸酸酸酸序序序序列列列列间的点阵分析间的点阵分析间的点阵分析间的点阵分析oo相相相相同同同同的的的的点点点点全全全全部部部部打打打打印印印印，很很很很难难难难找找找找到到到到有有有

11、有用用用用的的的的信信信信息息息息17使用滑动窗口技术降低噪声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 = 318ATACTACAAGACACGTACCGG C G A T G C A T T G A G T A T C A T AWindow size = 5String

12、ency = 3Match = 1 Mismatch = 019ATACTACAAGACACGTACCGG 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 G A T G C A T T G A G T A T C A T AWindow size = 5Stringency = 3Match = 1 Mismatch = 021G C G A T G C A T T G A G T A T C A T AATACT

13、ACAAGACACGTACCGWindow size = 5Stringency = 3Match = 1 Mismatch = 022G C G A T G C A T T G A G T A T C A T AATACTACAAGACACGTACCG23G C G A T G C A T T G A G T A T C A T AATACTACAAGACACGTACCG24使用滑动窗口技术降低噪声（a）对人类（Homo sapiens）与黑猩猩（Pongo pygmaeus）的球蛋白基因序列进行比较的完整点阵图（b）利用滑动窗口对以上的两种球蛋白基因序列进行比较的点阵图，其中窗口大小为10

14、个核苷酸， 相似度阈值为8，即10个核苷酸中有8个相同时就打一个点ab25点阵分析的优缺点o优点优点n n直观性，整体性；直观性，整体性；直观性，整体性；直观性，整体性；n n点阵分析不依赖空位点阵分析不依赖空位点阵分析不依赖空位点阵分析不依赖空位(gap)(gap)参数，可寻找两序列间参数，可寻找两序列间参数，可寻找两序列间参数，可寻找两序列间所有可能的残基匹配；所有可能的残基匹配；所有可能的残基匹配；所有可能的残基匹配；n n不依赖任何先决条件，是一种可用于初步分析的理不依赖任何先决条件，是一种可用于初步分析的理不依赖任何先决条件，是一种可用于初步分析的理不依赖任何先决条件，是一种可用于初

15、步分析的理想工具；想工具；想工具；想工具；n n点阵分析允许随时动态地改变最高和最低界限值，点阵分析允许随时动态地改变最高和最低界限值，点阵分析允许随时动态地改变最高和最低界限值，点阵分析允许随时动态地改变最高和最低界限值，可以用来摸索区分信号和背景标准的严格程度。可以用来摸索区分信号和背景标准的严格程度。可以用来摸索区分信号和背景标准的严格程度。可以用来摸索区分信号和背景标准的严格程度。26点阵分析的优缺点o缺点缺点n不能很好地兼容打分矩阵；不能很好地兼容打分矩阵；n滑动窗口和域值的选择过于经验化；滑动窗口和域值的选择过于经验化；n信噪比低；信噪比低； n不适合进行高通量的数据分析。不适合进

16、行高通量的数据分析。27点阵分析程序oDNA Strider (Macintosh)nhttp:/ oDotter (Unix/Linux, X-Windows)oCOMPARE, DOTPLOT (GCG软件)oPLALIGN (FASTA)oDotletnhttp:/www.isrec.isb-sib.ch/java/dotlet/Dotlet.html283.2 动态规划算法o动动动动态态态态规规规规划划划划算算算算法法法法(Dynamic (Dynamic Programming Programming Algorithm)Algorithm)是是是是一一一一种种种种计计计计算算算算方

17、方方方法法法法，它它它它的的的的主主主主要要要要思思思思路路路路是是是是把把把把一一一一个个个个问问问问题题题题分分分分成成成成若干个小问题来解决。若干个小问题来解决。若干个小问题来解决。若干个小问题来解决。o在在在在生生生生物物物物学学学学中中中中应应应应用用用用的的的的两两两两种种种种动动动动态态态态规规规规划划划划算算算算法法法法：Needleman-Needleman-WunschWunsch算算算算法法法法（全全全全局局局局比比比比对对对对）和和和和Smith-WatermanSmith-Waterman算算算算法法法法（局部比对）。（局部比对）。（局部比对）。（局部比对）。29序列

18、比对中某一位点匹配的三种可能性序列比对中某一位点匹配的三种可能性oEg. 匹配=1,非匹配=0, 空位罚分=-1nSequence1: CACGAnSequence2: CGA第一个位点得分剩余序列CC+1ACGAGA-C-1CACGAGAC-1ACGACGA30动态规划算法的数学形式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的

19、分值， s(aibj)是位置i 和j上比对分值，wx是在序列a 中长度为x的间隔罚分，wy是序列b中长度为y的间隔罚分31动态规划算法实例ACTTCGACTAG匹配3错配-1空位-232ACTTCG0ACTAG动态规划算法实例匹配3错配-1空位-233ACTTCG0-2ACTAG动态规划算法实例匹配3错配-1空位-234ACTTCG0-2-4-6-8-10-12ACTAG动态规划算法实例匹配3错配-1空位-235ACTTCG0-2-4-6-8-10-12A-2CTAG动态规划算法实例匹配3错配-1空位-236ACTTCG0-2-4-6-8-10-12A-2C-4T-6A-8G-10动态规划算法

20、实例?S(2,2)-2+(-2)-2+(-2)0+3匹配3错配-1空位-237ACTTCG0-2-4-6-8-10-12A-23C-4T-6A-8G-10动态规划算法实例?S(2,3)-4+(-2) 3+(-2)-2+(-1)匹配3错配-1空位-238动态规划算法实例ACTTCG0-2-4-6-8-10-12A-231C-4T-6A-8G-10匹配3错配-1空位-239动态规划算法实例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空位-240动态规划

21、算法实例ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149A-8-3 2G-10-50匹配3错配-1空位-241ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 27864G-10-505679GGT-CATTCCAA回回 溯溯42ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 27864G-10-505679GGT-CATTCCAA43ACTTCG0-2-4-6-8-10-12A-231-1-3-5-

22、7C-416420-2T-6-149753A-8-3 27864G-10-505679GGTAC-TTCCAA44比对结果1.ACTTCGAC-TAG2.ACTTCGACT-AG3.ACTTCGACTA-G哪一个是最优比对哪一个是最优比对(optimal alignment)呢呢?记分矩阵45记分矩阵与空位罚分oDNA计分矩阵o蛋白质计分矩阵o广泛使用的两种矩阵n PAM n BLOSUMo空位罚分46DNA计分矩阵actaccagttcatttgatacttctcaaataccattaccgtgttaactgaaaggacttaaagactSequence 1Sequence 2AGCTA1

23、000G0100C0010T0001匹配: 1错配: 0分值：547转换和颠换CTAG嘧啶嘌呤 表示转换(transition)，表示颠换(transversions)转换比颠换更容易发生48转换和颠换AGTCA0.99G0.0060.99T0.0020.0020.99C0.0020.0020.0060.99转换速率是颠换3倍时的模型49蛋白质计分矩阵PTHPLASKTQILPEDLASEDLTIPTHPLAGERAIGLARLAEEDFGMSequence 1Sequence 2记分矩阵T:G= -2 T:T = 5Score= 48 CSTPAGND.C 9S-1 4T-1 1 5P-3-

24、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 .50PAM( Percent Accepted Mutation)矩阵oo氨基酸容易被其它生化、物理特性相似的氨基酸替换。氨基酸容易被其它生化、物理特性相似的氨基酸替换。氨基酸容易被其它生化、物理特性相似的氨基酸替换。氨基酸容易被其它生化、物理特性相似的氨基酸替换。ooPAM1(1PAM1

25、(1个个个个PAMPAM单位）被定义为每单位）被定义为每单位）被定义为每单位）被定义为每100100个残基出现一个个残基出现一个个残基出现一个个残基出现一个被接受的点突变被接受的点突变被接受的点突变被接受的点突变( (氨基酸的置换不引起蛋白质功能上的显著氨基酸的置换不引起蛋白质功能上的显著氨基酸的置换不引起蛋白质功能上的显著氨基酸的置换不引起蛋白质功能上的显著变化）。变化）。变化）。变化）。ooPAMnPAMn是是是是PAM1PAM1自乘自乘自乘自乘n n次。次。次。次。ooPAM250PAM250、PAM120PAM120、PAM80PAM80和和和和PAM60PAM60矩阵可用于相矩阵可用

26、于相矩阵可用于相矩阵可用于相似性分别为似性分别为似性分别为似性分别为20%20%、40%40%、50%50%和和和和60%60%的序列比对。的序列比对。的序列比对。的序列比对。51 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

27、 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

28、 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

29、-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

30、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 25052 u模块替换矩阵BLOSUM以序列片段为基础,它是 基于蛋白质模块(Block)数据库而建立起来的 u 在模块比对的每一列中，分别计算 两两氨基酸的变化

31、情况,来自所有 模块的数值被用来计算BLOSUM矩阵u矩阵后面的数字表示构建此矩阵所用的 序列的相似程度，如BLOSUM62表示由 相似度为62%的序列构建AACECA - C = 0A - E = -1C - E = -4A - A = 4C - C = 9AACECBLOSUM矩阵 (Blocks Substitution Matrix)53BLOSUM62 54如何选择合适的评分矩阵？n n 一般来说一般来说一般来说一般来说, ,在局部相似性搜索上，在局部相似性搜索上，在局部相似性搜索上，在局部相似性搜索上， BLOSUM BLOSUM 矩阵较矩阵较矩阵较矩阵较PAMPAM要好要好要好要

32、好n n当比较距离相近的蛋白时，应选择低的当比较距离相近的蛋白时，应选择低的当比较距离相近的蛋白时，应选择低的当比较距离相近的蛋白时，应选择低的PAMPAM或高的或高的或高的或高的BLOSUMBLOSUM矩阵；当比较距离较远的蛋白时，应选择高的矩阵；当比较距离较远的蛋白时，应选择高的矩阵；当比较距离较远的蛋白时，应选择高的矩阵；当比较距离较远的蛋白时，应选择高的PAMPAM或低的或低的或低的或低的BLOSUMBLOSUM矩阵。矩阵。矩阵。矩阵。 n n 对于数据库搜索来说一般选择对于数据库搜索来说一般选择对于数据库搜索来说一般选择对于数据库搜索来说一般选择BLOSUM62BLOSUM62矩阵矩

33、阵矩阵矩阵n nPAMPAM矩阵可用于寻找蛋白质的进化起源，矩阵可用于寻找蛋白质的进化起源，矩阵可用于寻找蛋白质的进化起源，矩阵可用于寻找蛋白质的进化起源，BLOSUMBLOSUM矩阵用于矩阵用于矩阵用于矩阵用于发现蛋白质的保守域发现蛋白质的保守域发现蛋白质的保守域发现蛋白质的保守域554. 相似性与同源性n同同源源性性(Homologous Genes) ：序序列列来来自自共共同同的的祖祖先先，相相似似的的序序列列往往往往具具有有同同源源性。性。n相相似似性性(Similarity)：两两序序列列根根据据某某种种参参数设定而表现出来的相近性。数设定而表现出来的相近性。56相似性与同源性的区别

34、o相似的序列并不一定同源；相似的序列并不一定同源；o相相似似性性是是可可以以被被量量化化的的“计计分分表表”，它它是是匹匹配配的的数数量量除除以以比比对对的的长长度度，通通常常以以百百分分比比%表示；表示；o同源性一定是指同源性一定是指序列来自共同的祖先；序列来自共同的祖先；o同同源源性性是是一一个个定定性性的的概概念念，不不能能使使用用序序列列间具有百分之多少同源性来定义。间具有百分之多少同源性来定义。57同源性分类n直直直直系系系系同同同同源源源源(Orthologs)(Orthologs)：具具具具有有有有共共共共同同同同祖祖祖祖先先先先与与与与相似功能的同源基因（无基因复制事件）。相似

35、功能的同源基因（无基因复制事件）。相似功能的同源基因（无基因复制事件）。相似功能的同源基因（无基因复制事件）。n旁旁旁旁系系系系同同同同源源源源(Paralogs)(Paralogs)：两两两两个个个个物物物物种种种种AA和和和和BB的的的的同同同同源源源源基基基基因因因因，分分分分别别别别是是是是共共共共同同同同祖祖祖祖先先先先基基基基因因因因组组组组中中中中由由由由复复复复制制制制事件而产生的不同拷贝的后代。事件而产生的不同拷贝的后代。事件而产生的不同拷贝的后代。事件而产生的不同拷贝的后代。58So this means 59 第二节 多序列比对 (Multiple Alignments)

36、60o寻找蛋白质家族，识别多个序列的保守区域；o相似的蛋白质序列往往具有相似的结构与功能；o辅助预测新序列的二级或三级结构；o可以直观地看到基因的哪些区域对突变敏感；oPCR引物设计；我们为什么做多序列比对?o分析多个序列的一致序列；o用于进化分析，是用系统发育方法构建进化树的初使步骤； o寻找个体之间单核苷酸多态性(SNPs)；o通过序列比对发现直系同源(Orthologs)与旁系同源(Paralogs)基因；o寻找同源基因(相似的序列往往具有同源性)。我们为什么做多序列比对?多序列比对与进化研究例子图中NYLS为树根一个多序列比对例子VTISCTGSSSNIGAG-NHVKWYQQLPGV

37、TISCTGTSSNIGS-ITVNWYQQLPGLRLSCSSSGFIFSS-YAMYWVRQAPGLSLTCTVSGTSFDD-YYSTWVRQPPGPEVTCVVVDVSHEDPQVKFNWYVDG-ATLVCLISDFYPGA-VTVAWKADS-AALGCLVKDYFPEP-VTVSWNSG-VSLTCLVKGFYPSD-IAVEWWSNG-多序列比对方法全局序列比对全局序列比对动态规划算法 (Dynamic Programming Algorithm)分而治之方法 (Divide and Conquer Methods)SP方法 (Sum of Pairs Methods) 累进方

38、法 (Progressive Methods)迭代方法 (Iterative Methods)局部序列比对局部序列比对概形分析 (Profile Analysis)区块分析 (Block Analysis)统计学方法统计学方法 (Statistical Methods）在多序列比对前要考虑的问题o比对的优劣与序列条数正相关比对的优劣与序列条数正相关比对的优劣与序列条数正相关比对的优劣与序列条数正相关o每个亚群应分别先比对，然后再整体比对每个亚群应分别先比对，然后再整体比对每个亚群应分别先比对，然后再整体比对每个亚群应分别先比对，然后再整体比对一、全局序列比对动态规划算法 (Dynamic Pr

39、ogramming Algorithm)分而治之方法 (Divide and Conquer Methods)SP方法 (Sum of Pairs Methods) 累进方法 (Progressive Methods)迭代方法 (Iterative Methods)遗传算法 (Genetic Algorithms)o序列长度为序列长度为 n 的双序列比对的双序列比对nn2 比对比对o比对数目成指数增长比对数目成指数增长n例如：序列长度为例如：序列长度为n，序列数为，序列数为N 的多序列比对数目的多序列比对数目是是nNo对于数目较少且较短的序列来说都不切实际对于数目较少且较短的序列来说都不切实际

40、1.动态规划算法(Dynamic Programming)Sequence 1Sequence 2Sequence 3多维的动态规划算法分而治之分而治之 (Divide and Conquer, DCA)方法方法将MSA（Measurement System Analysis）的空间复杂度减小DCA在线MSAhttp:/bioweb.pasteur.fr/seqanal/interfaces/dca-simple.html2. 分而治之方法So in effect Sequence 1Sequence 2Sequence 33. SP(Sum of Pairs)方法oo为了找到最佳比对，并解决

41、动态规则算法的计算复为了找到最佳比对，并解决动态规则算法的计算复为了找到最佳比对，并解决动态规则算法的计算复为了找到最佳比对，并解决动态规则算法的计算复杂问题，杂问题，杂问题，杂问题，Carrillo & Lipman (1988)Carrillo & Lipman (1988)发明了发明了发明了发明了SP (Sum SP (Sum of Pairs)of Pairs)方法方法方法方法ooSPSP方法通过对一个随机数据矩阵中氨基酸对的所方法通过对一个随机数据矩阵中氨基酸对的所方法通过对一个随机数据矩阵中氨基酸对的所方法通过对一个随机数据矩阵中氨基酸对的所有可能组合的记分求和来获得矩阵记分有可能

42、组合的记分求和来获得矩阵记分有可能组合的记分求和来获得矩阵记分有可能组合的记分求和来获得矩阵记分4. 累进算法(Progressive Methods)o针对基于动态规划算法的MSA程序比对序列数目有限， Feng & Doolittle(1987)发明了累进算法oCLUSTAL 和 PILEUP 是目前常用的基于累进算法的比对软件oCLUSTAL 是免费软件,目前应用非常广泛 http:/www-igbmc.u-strasbg.fr/BioInfo/ClustalX/Top.html1 对所有序列做双序列比对，构建距离矩阵计算相似性分数值2 基于双序列距离矩阵，构建一个进化树 Scer Ce

43、le 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累进算法原理一般累进比对方法132513131325254droot果仁糖累进方法(Praline progressive strategy)13213131325254d4累进算法的一些问

44、题o比对的准确性高度依赖于开始选择的双序列比对o序列关系越远发生的错误可能越高o选择合适的打分矩阵和罚分准则较困难ClLUSTALW/X简介ooClLUSTALClLUSTAL最初初由最初初由最初初由最初初由HigginsHiggins等于等于等于等于19881988年创立并不断完善年创立并不断完善年创立并不断完善年创立并不断完善 oo用来多序列比对、概形用来多序列比对、概形用来多序列比对、概形用来多序列比对、概形(Profile)(Profile)分析和创建进化树分析和创建进化树分析和创建进化树分析和创建进化树ooClLUSTALClLUSTAL分为分为分为分为ClLUSTALWClLUST

45、ALW和和和和CLUSTALXCLUSTALX两种类型两种类型两种类型两种类型ooClLUSTALClLUSTAL有用于有用于有用于有用于WINDOWSWINDOWS和和和和UNIX/LINUXUNIX/LINUX的各种版本的各种版本的各种版本的各种版本CLUSTAL方法oo进行所有序列间的双序列比对进行所有序列间的双序列比对进行所有序列间的双序列比对进行所有序列间的双序列比对oo基于双序列比对分数产生一个相邻连接进化树基于双序列比对分数产生一个相邻连接进化树基于双序列比对分数产生一个相邻连接进化树基于双序列比对分数产生一个相邻连接进化树(neighbor-join tree)(neighbo

46、r-join tree)oo根据进化树提供的序列间关系按顺序对序列进行比对根据进化树提供的序列间关系按顺序对序列进行比对根据进化树提供的序列间关系按顺序对序列进行比对根据进化树提供的序列间关系按顺序对序列进行比对oo比对可以用以下两种方法：比对可以用以下两种方法：比对可以用以下两种方法：比对可以用以下两种方法：n n- slow/accurate - slow/accurate n n- fast/approximate- fast/approximate* CLUSTAL W (1.8) Multiple Sequence Alignments * 1.Sequence Input From

47、 Disc2. Multiple Alignments 3. Profile / Structure Alignments 4. Phylogenetic trees S. Execute a system command H. HELP X. EXIT (leave program) Your choice:1CLUSTAL WSequences should all be in 1 file. 7 formats accepted: NBRF/PIR, EMBL/SwissProt, Pearson (Fasta), GDE, Clustal, GCG/MSF, RSF. Enter th

48、e 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 W* CLUSTAL W (1.8) Multiple Sequence Alignments * 1.Se

49、quence 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 WClustal W* * MULTIPLE ALIGNMENT MENU * * 1. Do complete multiple alignment now (Slow/Accurate) 2. Produce guide tr

50、ee file only 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 o

51、r press RETURN to go back to main menuYour choice: 1 Enter 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 Sequenc

52、es (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 file created: anti.dnd Start of Multiple Alignment

53、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 file created anti.aln Mac Vector界面的Clustal WClustal X介绍ClustalX介绍ClustalX介绍Cl

54、ustalX介绍ClustalX介绍ExampleMultiple sequence alignment of 7 neuroglobins using clustalxPILEUPooP PILEUPILEUP是是是是GCG(Genetics Computer Group)GCG(Genetics Computer Group)软件包中软件包中软件包中软件包中的的的的MSAMSA分析工具；分析工具；分析工具；分析工具；oo与与与与CLUSTALCLUSTAL一样使用累进式整体比对方法一样使用累进式整体比对方法一样使用累进式整体比对方法一样使用累进式整体比对方法(Progressive Glo

55、bal Alignment)(Progressive Global Alignment)；ooPILEUPPILEUP开始的双序列比对使用开始的双序列比对使用开始的双序列比对使用开始的双序列比对使用Needleman-WunschNeedleman-Wunsch动动动动态规划算法，所以是全局序列比对，善于比较相似度态规划算法，所以是全局序列比对，善于比较相似度态规划算法，所以是全局序列比对，善于比较相似度态规划算法，所以是全局序列比对，善于比较相似度较高的序列。较高的序列。较高的序列。较高的序列。Output of Pileup 401 OATNFA1 TTCAG. .ACACTCAGG TC

56、ATCTTCTC 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 TCATCTT

57、CTC GAAC RABTNFM CCCAGATGGT CACCCTCAGA TCAGCTTCTC GGGC RNTNFAA CCCAGACCCT CACACTCAGA TCATCTTCTC AAAAOutput of PileupClUSTAL和PILEUP存在的问题o最终的比对结果取决于最初的双序列比对，最终的比对结果取决于最初的双序列比对，最终的比对结果取决于最初的双序列比对，最终的比对结果取决于最初的双序列比对，起初的序列相似度越高比对越准确；起初的序列相似度越高比对越准确；起初的序列相似度越高比对越准确；起初的序列相似度越高比对越准确；o如果比对序列间长度差异较大则会生成异常如果比对

58、序列间长度差异较大则会生成异常如果比对序列间长度差异较大则会生成异常如果比对序列间长度差异较大则会生成异常的引导树的引导树的引导树的引导树( (guide guide trees)trees)从而严重影响多序列比从而严重影响多序列比从而严重影响多序列比从而严重影响多序列比对；对；对；对；o所选的记分与罚分标准并不一定适合一组序所选的记分与罚分标准并不一定适合一组序所选的记分与罚分标准并不一定适合一组序所选的记分与罚分标准并不一定适合一组序列中的所有序列。列中的所有序列。列中的所有序列。列中的所有序列。o对累进比对方法的改进对累进比对方法的改进o迭代方法策略迭代方法策略n在比对过程中不断重新比对

59、各亚组序列在比对过程中不断重新比对各亚组序列n把亚组序列再排成包括所有序列在内的整把亚组序列再排成包括所有序列在内的整体比对体比对n获得最优的总比对分数（由成对比对分数获得最优的总比对分数（由成对比对分数相加而成）相加而成）5. 迭代方法 (Iterative Methods)二、局部序列比对局部比对局部比对(Local Alignment)方法能够确定方法能够确定序列中高度保守的区域。序列中高度保守的区域。u概形分析概形分析概形分析概形分析 (Profile Analysis)u区块分析区块分析区块分析区块分析 (Block Analysis)1. 概形分析 (Profile Analysi

60、s)oo通通通通过过过过对对对对一一一一组组组组序序序序列列列列进进进进行行行行整整整整体体体体MSAMSA分分分分析析析析，把把把把其其其其中中中中高高高高度度度度保保保保守守守守的的的的区区区区域提出分成小的域提出分成小的域提出分成小的域提出分成小的MSAMSA。oo这些小的这些小的这些小的这些小的MSAMSA根据其序列与结构的比对得到一个记分矩阵。根据其序列与结构的比对得到一个记分矩阵。根据其序列与结构的比对得到一个记分矩阵。根据其序列与结构的比对得到一个记分矩阵。oo根根根根据据据据这这这这个个个个矩矩矩矩阵阵阵阵列列列列出出出出每每每每个个个个位位位位置置置置上上上上的的的的残残残残

61、基基基基分分分分数数数数，称称称称为为为为位位位位置置置置特特特特异异异异记分表记分表记分表记分表(Position Specific Scoring Table)(Position Specific Scoring Table)或概形或概形或概形或概形(Profile)(Profile)。oo概概概概形形形形(Profile)(Profile)类类类类似似似似于于于于一一一一个个个个小小小小的的的的MSAMSA，包包包包括括括括匹匹匹匹配配配配、错错错错配配配配、插插插插入入入入和缺失。和缺失。和缺失。和缺失。概形分析 (Profile Analysis)oo优势：优势：优势：优势：n n用

62、来寻找一个可能与之匹配的目标序列；用来寻找一个可能与之匹配的目标序列；用来寻找一个可能与之匹配的目标序列；用来寻找一个可能与之匹配的目标序列；n n用用用用来来来来在在在在一一一一个个个个数数数数据据据据库库库库中中中中搜搜搜搜索索索索一一一一个个个个可可可可能能能能的的的的新新新新的的的的蛋蛋蛋蛋白白白白 (pfsearch)(pfsearch)；n n通通通通过过过过搜搜搜搜索索索索一一一一个个个个profileprofile数数数数据据据据库库库库来来来来找找找找到到到到提提提提交交交交的的的的序序序序列列列列属属属属于哪一家族于哪一家族于哪一家族于哪一家族(pfscan)(pfscan

63、)；n n比对两个比对两个比对两个比对两个MSAMSA(profile to profile)(profile to profile)。oo缺点：缺点：缺点：缺点：n n所所所所产产产产生生生生的的的的概概概概形形形形仅仅仅仅仅仅仅仅代代代代表表表表MSAMSA本本本本身身身身的的的的序序序序列列列列族族族族变变变变异异异异，如如如如果果果果MSAMSA中中中中的的的的几几几几个个个个序序序序列列列列相相相相似似似似，则则则则衍衍衍衍生生生生的的的的概概概概形形形形将将将将偏偏偏偏向于这些序列向于这些序列向于这些序列向于这些序列。 不同物种HSP70蛋白的profile图左左左左边边边边第第第

64、第一一一一列列列列为为为为一一一一致致致致序序序序列列列列(consensus (consensus sequence),sequence),其其其其余余余余的的的的行行行行的的的的数数数数值值值值表表表表示示示示一一一一致致致致序序序序列列列列中中中中每每每每一一一一个个个个氨氨氨氨基基基基酸酸酸酸出出出出现现现现的的的的频频频频率率率率的的的的对对对对数数数数与与与与随随随随机机机机频频频频率率率率对对对对数数数数的的的的比比比比值值值值，如如如如出出出出现现现现空空空空位位位位，则则则则必必必必须须须须减减减减去去去去空空空空位位位位行行行行在在在在相相相相应应应应位位位位置置置置上上上

65、上的的的的数数数数值值值值。如如如如用用用用其其其其寻寻寻寻找找找找一一一一个个个个长长长长度度度度为为为为100aa100aa的的的的序序序序列列列列，则则则则检检检检查查查查的的的的串串串串为为为为110,211,110,211,，最最最最高高高高记记记记分分分分区区区区段段段段将将将将是是是是概概概概形形形形最最最最相相相相似似似似部部部部分分分分。图图图图中中中中Z Z表表表表示示示示谷谷谷谷氨酸氨酸氨酸氨酸 or or 谷氨酰胺谷氨酰胺谷氨酰胺谷氨酰胺 ; B; B表示天冬氨酸表示天冬氨酸表示天冬氨酸表示天冬氨酸 or or 丙氨酸丙氨酸丙氨酸丙氨酸 用CLUSTALX进行Profi

66、le比对2. 区块分析o与概形分析相似，区块也代表与概形分析相似，区块也代表与概形分析相似，区块也代表与概形分析相似，区块也代表MSAMSAMSAMSA中的保守区；中的保守区；中的保守区；中的保守区；o区块无插入与缺失，每一个位置只有匹配与错区块无插入与缺失，每一个位置只有匹配与错区块无插入与缺失，每一个位置只有匹配与错区块无插入与缺失，每一个位置只有匹配与错配；配；配；配；o每一条序列中的同一区块具有相同的长度；每一条序列中的同一区块具有相同的长度；每一条序列中的同一区块具有相同的长度；每一条序列中的同一区块具有相同的长度；oBLOCKS BLOCKS 数据库数据库数据库数据库http:/b

67、locks.fhcrc.org/http:/blocks.fhcrc.org/。MSA中的统计学方法(Statistical Methods）o最大期望运算法则(Expectation Maximization Algorithm,EM)o吉布斯取样器(Gibbs Sampler)o隐马尔可夫模型(Hidden Markov Model,HMM)o位置特异性记分矩阵(Position-Specific Scoring Matrix, PSSM)o序列标语(Sequence Logo)最大期望运算法则o用来从未比对的蛋白序列中寻找保守功能域；用来从未比对的蛋白序列中寻找保守功能域；用来从未比对的

68、蛋白序列中寻找保守功能域；用来从未比对的蛋白序列中寻找保守功能域；o从从从从DNADNA序列中找蛋白质结合位点；序列中找蛋白质结合位点；序列中找蛋白质结合位点；序列中找蛋白质结合位点；o通过通过通过通过EMEM算法找到的这些模体算法找到的这些模体算法找到的这些模体算法找到的这些模体(Motif)(Motif)允许空位的允许空位的允许空位的允许空位的存在。存在。存在。存在。MEME (Multiple EM for Motif Elicitation)oMEME程序是由加州大学san Diego 分校的超级计算中心所创立。oMEME的三种模体(Motif)模型：nOOPS每条序列中预期出现一次m

69、otif；nZOOPS每条序列出现零次或一次motif；nTCM每条序列中出现任意次数的motif。基于Web的MEME软件o在线MEME工具：nMEMEoDiscover motifs (highly conserved regions) in groups of related DNA or protein sequences ohttp:/meme.sdsc.edu/meme/website/meme.html nMASToSearch sequence databases using motifsohttp:/meme.sdsc.edu/meme/website/mast.html M

70、EME结果隐马尔可夫模型(HMM)oo定义：定义：定义：定义：一种统计模型，它考虑有关匹配、错配和间隔一种统计模型，它考虑有关匹配、错配和间隔一种统计模型，它考虑有关匹配、错配和间隔一种统计模型，它考虑有关匹配、错配和间隔的所有可能的组合来生成一组序列排列的所有可能的组合来生成一组序列排列的所有可能的组合来生成一组序列排列的所有可能的组合来生成一组序列排列ooHMMHMM用来序列分析、产生概形用来序列分析、产生概形用来序列分析、产生概形用来序列分析、产生概形HMMHMM、分析序列组、分析序列组、分析序列组、分析序列组成和模式并通过预测开放阅读框成和模式并通过预测开放阅读框成和模式并通过预测开放

71、阅读框成和模式并通过预测开放阅读框(Open Reading (Open Reading Frame, ORFFrame, ORF）来定位基因及预测蛋白质结构）来定位基因及预测蛋白质结构）来定位基因及预测蛋白质结构）来定位基因及预测蛋白质结构oo原理原理原理原理：先产生一个序列家族模型，并用先验信息初始：先产生一个序列家族模型，并用先验信息初始：先产生一个序列家族模型，并用先验信息初始：先产生一个序列家族模型，并用先验信息初始化，然后用一组序列化，然后用一组序列化，然后用一组序列化，然后用一组序列( (序列条数序列条数序列条数序列条数 20) 20) 来训练来训练来训练来训练HMMHMM模模模

72、模型。训练过程中包括的序列越多，分析的精确性越型。训练过程中包括的序列越多，分析的精确性越型。训练过程中包括的序列越多，分析的精确性越型。训练过程中包括的序列越多，分析的精确性越高高高高隐马尔可夫模型(HMM)o优点：植根于概率论，无须序列的顺序信息，无需插入/缺失和罚分，可以用到很多先验信息。o缺点：需要至少20条序列，有时需要更多才能了解进化历史。o分析工具：HMMER(http:/hmmer.wustl.edu/)oPfam: (protein domain alignments and profile HMMs) http:/www.sanger.ac.uk/Software/Pfam

73、/ HMM示意图NKYLT是通过BEG-M1-I1-M2-M3-M4-END计算这条路径的概率位置特异性记分矩阵o对对对对于于于于序序序序列列列列保保保保守守守守区区区区进进进进行行行行MSAMSA分分分分析析析析可可可可以以以以产产产产生生生生位位位位置置置置特特特特 异异异异 记记记记 分分分分 矩矩矩矩 阵阵阵阵 (Position-specific (Position-specific scoring scoring matrix, PSSM)matrix, PSSM)。o与与与与ProfileProfile相相相相似似似似，都都都都是是是是用用用用一一一一个个个个数数数数值值值值表表

74、表表示示示示每每每每一一一一个个个个氨氨氨氨基基基基酸酸酸酸或或或或核核核核苷苷苷苷酸酸酸酸在在在在每每每每一一一一位位位位置置置置上上上上出出出出现现现现的的的的频频频频率率率率，不不不不同同同同的的的的是是是是PSSMPSSM使使使使用用用用频频频频率率率率的的的的对对对对数数数数值值值值(log(log2 2) )为为为为其其其其数数数数值。值。值。值。n n用用用用PSSMPSSM来搜寻一条序列，以找到此序列具有来搜寻一条序列，以找到此序列具有来搜寻一条序列，以找到此序列具有来搜寻一条序列，以找到此序列具有PSSMPSSM所所所所代表的序列模体代表的序列模体代表的序列模体代表的序列模体

75、(motif) (motif) 的可能位置；的可能位置；的可能位置；的可能位置；n n用来搜索整个数据库以寻找额外的具有相同模体用来搜索整个数据库以寻找额外的具有相同模体用来搜索整个数据库以寻找额外的具有相同模体用来搜索整个数据库以寻找额外的具有相同模体(motif)(motif)的序列；的序列；的序列；的序列；n n寻找蛋白质家族所共有的序列模式、转录因子结合位寻找蛋白质家族所共有的序列模式、转录因子结合位寻找蛋白质家族所共有的序列模式、转录因子结合位寻找蛋白质家族所共有的序列模式、转录因子结合位点和内含子与外显子交界区共有的序列模式。点和内含子与外显子交界区共有的序列模式。点和内含子与外显子交界区共有的序列模式。点和内含子与外显子交界区共有的序列模式。PSSM用途序列标语(Sequence Logos)oo序列标语是一种用图形来表示模体序列标语是一种用图形来表示模体序列标语是一种用图形来表示模体序列标语是一种用图形来表示模体(motif)(motif)中每一列残基中每一列残基中每一列残基中每一列残基的信息的信息的信息的信息。oo在线序列在线序列在线序列在线序列LOGOLOGO：http:/weblogo.berkeley.eduhttp:/weblogo.berkeley.eduX轴表示模式的位置，Y轴上字母高度代表该字母在此位置上出现的频率CINEMA