双序列比对课件.ppt

《双序列比对课件.ppt》由会员分享，可在线阅读，更多相关《双序列比对课件.ppt（72页珍藏版）》请在三一办公上搜索。

1、课程主线,序列比对基本概念空位罚分相似性与同源性双序列比对方法点阵序列比较(Dot Matrix Sequence Comparison)动态规划算法(Dynamic Programming Algorithm)记分矩阵,1,什么是序列比对？,序列比对(Sequence Alignment)是通过在序列中搜索一系列单个性状或性状模式来比较2个（双序列比对）或更多（多重序列比对）序列的方法按比对序列条数分类双序列比对：两条序列的比对多序列比对：三条或以上序列的比对,2,我们为什么关注序列比对？,相似的序列可能具有相似的功能与结构发现一个基因或蛋白哪些区域容易发生突变，哪些位点突变后对功能没有影响

2、 发现生物进化方面的信息,3,序列比对两种类型,全局序列比对定义：在全局范围内对两条序列进行比对打分的方法适合于非常相似且长度近似相等的序列局部序列比对定义：一种寻找匹配子序列的序列比对方法 适合于一些片段相似而另一些片段相异的序列,4,序列比对两种类型,5,空位罚分(Gap Penalties),空位为了获得两个序列最佳比对，必须使用空位和空位罚分空位罚分分类：空位开放罚分(Gap opening penalty)空位扩展罚分(Gap extension penalty)最优的序列比对通常具有以下两下特征：尽可能多的匹配尽可能少的空位插入任意多的空位会产生较高的分数，但找到的并不一定是真正相

3、似序列,6,1 GTGATAGACAC|1 GTGCATAGACAC,空位罚分,允许空位但不罚分,不允许有空位,match=5mismatch=-4,1 GTG-ATAGACAC|1 GTGCATAGACAC,1 GTG-ATAGACAC|1 GTGC-ATAGACAC,?,Score:-21,Score:55,7,空位罚分公式,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-(3-1)0.1=-3.2,8,双序列比对方法,点阵序列比较(Dot Mat

4、rix Sequence Comparison)动态规划算法(Dynamic Programming Algorithm)词或K串方法(Word or K-tuple Methods),9,点阵序列比较,点阵(Dot Matrix)分析是一种简单的图形显示序列相似性的方法沿X轴上序列1中的每一个单元（核苷酸或氨基酸）与沿Y轴的第二个序列中的每一个单元进行比较，相同的区域在点阵图中显示为由点组成的对角线，对角线之外零散的点为背景噪音,10,11,12,点阵分析的应用,自身比对寻找序列中的正向或反向重复序列蛋白质的重复结构域(domain)相同残基重复出现的低复杂区(Low Complexity)

5、RNA二级结构中的互补区域等对两条序列的相似性作整体的估计,13,点阵分析中的插入或删除,TACTGTCAT T A C T G T T C A T,Sequence 1,Sequence 2,T A C T G-T C A T|T A C T G T T C A T,插入空位,14,点阵分析的应用,人类低脂受体(human low-density lipoprotein receptor)自身比对发现正向重复序列,具有连续相似区域的两条DNA序列的简单点阵图,正向重复,15,点阵分析实例,编码噬菌体c（水平轴）和噬菌体P22 c2（垂直轴）的氨基酸序列间的点阵分析相同的点打印全部打印，很难找

6、到有用的信息,16,使用滑动窗口技术降低噪声,T A C G G T A T G A C A G T A T C,T A C G G T A T G A C A G T A T C,T A C G G T A T G A C A G T A T C,T A C G G T A T G A C A G T A T C,C T A T G A C A TACGGTATG,Window=3 Word Size=3,17,ATACTACAAGACACGTACCG,G C G A T G C A T T G A G T A T C A T A,Window size=5Stringency=3,Matc

7、h=1 Mismatch=0,18,ATACTACAAGACACGTACCG,G C G A T G C A T T G A G T A T C A T A,Window size=5Stringency=3,Match=1 Mismatch=0,19,ATACTACAAGACACGTACCG,G C G A T G C A T T G A G T A T C A T A,Window size=5Stringency=3,Match=1 Mismatch=0,20,G C G A T G C A T T G A G T A T C A T A,ATACTACAAGACACGTACCG,Win

8、dow size=5Stringency=3,Match=1 Mismatch=0,21,G C G A T G C A T T G A G T A T C A T A,ATACTACAAGACACGTACCG,22,G C G A T G C A T T G A G T A T C A T A,ATACTACAAGACACGTACCG,23,使用滑动窗口技术降低噪声,（a）对人类（Homo sapiens）与黑猩猩（Pongo pygmaeus）的球蛋白基因序列进行比较的完整点阵图（b）利用滑动窗口对以上的两种球蛋白基因序列进行比较的点阵图，其中窗口大小为10个核苷酸，相似度阈值为8，即10

9、个核苷酸中有8个相同时就打一个点,a,b,24,点阵分析的优缺点,优点直观性，整体性点阵分析不依赖空位(gap)参数，可寻找两序列间所有可能的残基匹配不依赖任何先决条件，是一种可用于初步分析的理想工具点阵分析允许随时动态地改变最高和最低界限值，可以用来摸索区分信号和背景标准的严格程度,25,点阵分析的优缺点,缺点不能很好地兼容打分矩阵滑动窗口和预值的选择过于经验化信噪比低 不适合进行高通量的数据分析,26,点阵分析程序,DNA Strider(Macintosh)http:/Dotter(Unix/Linux,X-Windows)COMPARE,DOTPLOT(GCG软件)PLALIGN(FA

10、STA)Dotlethttp:/www.isrec.isb-sib.ch/java/dotlet/Dotlet.html,27,28,动态规划算法,动态规划算法(Dynamic Programming Algorithm)是一种计算方法，它的主要思路是把一个问题分成若干个小问题来解决在生物学中应用的两种动态规划算法：Needleman-Wunsch算法（全局比对）和Smith-Waterman算法（局部比对）,29,序列比对中某一位点匹配的三种可能性,Eg.匹配=1,非匹配=0,空位罚分=-1Sequence1:CACGASequence2:CGA,30,动态规划算法的正式表述,Si,j这个位

11、置的分数为图中箭头所示三个方向值中最大的一个,31,动态规划算法的数学形式,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,动态规划算法实例,匹配3错配-1空位-2,33,动态规划算法实例,匹配3错配-1空位

12、-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,42,回 溯,43,44,TA,C-,45,比对结果,1.ACTTCGAC-TAG2.ACTTCGACT-AG3.ACTTCGACTA-G,哪一个是最优比对(optimal alignment)呢?,记

13、分矩阵,46,Needleman-Wunsch算法,Seq1:MPRCLCQRJNCBASeq2:PBRCKCRNJCJA,匹配=1，错配=0，空位罚分=0,47,Needleman-Wunsch算法,Seq1:MPRCLCQRJNCBASeq2:PBRCKCRNJCJA,求出阴影部分所能达到的最大值填入当前位置，并记下到达这一位置的路径,48,Needleman-Wunsch算法,Seq1:MPRCLCQRJNCBASeq2:PBRCKCRNJCJA,5,49,Needleman-Wunsch算法,MPRCLCQRJNCBA PBRCKCRNJCJA,Result：,50,F(i-1,j-1

14、)+s(ai,bj),F(i,j)=max F(i,j-1)-wy,F(i-1,j)-wx.,0,动态规划算法,Smith-Waterman 算法,Smith-Waterman算法,51,Smith-Waterman 算法,匹配=1非匹配=-1空位=-1,52,Smith-Waterman 算法,A A C C T A T A G C T-G C G A T A T A-,匹配=1非匹配=-1空位=-1,53,Genetics Computer Group(GCG)程序 GAP(Needleman-Wunsch algorithm)and BESTFIT(Smith-Waterman algo

15、rithm)最相似的比对表示为:,较相似的表示为.无相关的表示为空格,carboxy-terminal,54,记分矩阵与空位罚分,DNA计分矩阵蛋白质计分矩阵广泛使用的两种矩阵 PAM BLOSUM空位罚分,55,记分矩阵(SCORING MATRICES),DNA Scoring MatricesAmino Acid Substitution MatricesPAM(Point Accepted Mutation)BLOSUM(Blocks Substitution Matrix),56,DNA计分矩阵,Sequence 1Sequence 2,AGCTA1000G0100C0010T000

16、1,匹配:1错配:0分值：5,57,转换和颠换,表示转换(transition)，表示颠换(transversions)转换比颠换更容易发生,58,转换和颠换,转换速率是颠换3倍时的模型,59,蛋白质计分矩阵,PTHPLASKTQILPEDLASEDLTI,PTHPLAGERAIGLARLAEEDFGM,Sequence 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.

17、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.,60,PAM(Percent Accepted Mutation)矩阵,氨基酸容易被其它生化、物理特性相似的氨基酸替换PAM1(1个PAM单位）被定义为每100个残基出现一个被接受的点突变(氨基酸的置换不引起蛋白质功能上的显著变化）PAMn是PAM1自乘n次PAM250、PAM120、PAM80和PAM60矩阵可用于相似性分别为20%、40%、50%和60%的序列比对,61,A R N D C Q E G H I L K M F P

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

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

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

21、-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 250,62,模块替换矩阵BLOSUM以序列片段为基础,它是 基于蛋白质模块(Block)数据库而建立起来的 在模块比对的每一列中，分别计算 两两氨基酸的变化情况,来自所有 模块的数值被用来计算BLOSUM矩阵矩阵后面的数字表示构建此矩阵所用的 序列的相似程度，如BLOSUM62表示由 相似度为62%的序列构建,AACEC,A-C=

22、0A-E=-1C-E=-4A-A=4C-C=9,AACEC,BLOSUM矩阵(Blocks Substitution Matrix),63,BLOSUM62,64,如何选择合适的评分矩阵？,一般来说,在局部相似性搜索上，BLOSUM 矩阵较PAM要好当比较距离相近的蛋白时，应选择低的PAM或高的BLOSUM矩阵；当比较距离较远的蛋白时，应选择高的PAM或低的BLOSUM矩阵 对于数据库搜索来说一般选择BLOSUM62矩阵PAM矩阵可用于寻找蛋白质的进化起源，BLOSUM矩阵用于发现蛋白质的保守域,65,相似性与同源性,同源性(Homologous Genes)：序列来自共同的祖先，相似的序列往

23、往具有同源性相似性(Similarity)：两序列根据某种参数设定而表现出来的相近性,66,相似性与同源性的区别,相似的序列并不一定同源相似性是可以被量化的“计分表”，它是匹配的数量除以比对的长度，通常以百分比%表示同源性一定是指序列来自共同的祖先同源性是一个定性的概念，不能使用序列间具有百分之多少同源性来定义,67,同源性分类,直系同源(Orthologs)：具有共同祖先与相似功能的同源基因（无基因复制事件）旁系同源(Paralogs)：两个物种A和B的同源基因，分别是共同祖先基因组中由复制事件而产生的不同拷贝的后代,68,So this means,69,精品课件！,精品课件！,谢谢！,72,