双序列比对的方法ppt课件

双序列比对郭志云:bioinfswjtu.eduo 序列比对根本概念o 空位罚分o 类似性与同源性o 双序列比对方法o 点阵序列比较(Dot Matrix Sequence Comparison)o 动态规划算法(Dynamic Programming Algorithm)o 记分矩阵o 序列比对(Sequence Alignment)是经过在序列中搜索一系列单个性状或性状方式来比较2个双序列比对或更多多重序列比对序列的方法o 按比对序列条数分类o 双序列比对：两条序列的比对o 多序列比对：三条或以上序列的比对o 类似的序列能够具有类似的功能与构造o 发现一个基因或蛋白哪些区域容易发生突变，哪些位点突变后对功能没有影响 o 发现生物进化方面的信息o 全局序列比对全局序列比对o 定义：在全局范围内对两条序列进展比对打分的定义：在全局范围内对两条序列进展比对打分的方法方法o 适宜于非常类似且长度近似相等的序列适宜于非常类似且长度近似相等的序列o 部分序列比对部分序列比对o 定义：一种寻觅匹配子序列的序列比对方法定义：一种寻觅匹配子序列的序列比对方法 o 适宜于一些片段类似而另一些片段相异的序列适宜于一些片段类似而另一些片段相异的序列o 空位为了获得两个序列最正确比对，必需运用空位和空位罚分o 空位罚分分类：o 空位开放罚分(Gap opening penalty)o 空位扩展罚分(Gap extension penalty)o 最优的序列比对通常具有以下两下特征：o 尽能够多的匹配o 尽能够少的空位o 插入恣意多的空位会产生较高的分数，但找到的并不一定是真正类似序列1 GTGATAGACAC|1 GTGCATAGACAC允许空位但不罚分不允许有空位 match=5mismatch=-41 GTG-ATAGACAC|1 GTGCATAGACAC1 GTG-ATAGACAC|1 GTGC-ATAGACAC?Score:-21Score:55 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-(3-1)0.1=-3.2o 点阵序列比较(Dot Matrix Sequence Comparison)o 动态规划算法(Dynamic Programming Algorithm)o 词或K串方法(Word or K-tuple Methods)o点阵(Dot Matrix)分析是一种简单的图形显示序列类似性的方法o沿X轴上序列1中的每一个单元核苷酸或氨基酸与沿Y轴的第二个序列中的每一个单元进展比较，一样的区域在点阵图中显示为由点组成的对角线，对角线之外零散的点为背景噪音IONIZATIONIONIZATIONIONIZATNOIIONIZATNOIo本身比对o寻觅序列中的正向或反向反复序列o蛋白质的反复构造域(domain)o一样残基反复出现的低复杂区(Low Complexity)oRNA二级构造中的互补区域等o对两条序列的类似性作整体的估计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插入空位插入空位人类低脂受体(human low-density lipoprotein receptor)本身比对发现正向反复序列具有延续类似区域的两条DNA序列的简单点阵图正向反复o 编码噬菌体c程度轴和噬菌体P22 c2垂直轴的氨基酸序列间的点阵分析o 一样的点打印全部打印，很难找到有用的信息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=3ATACTACAAGACACGTACCGG C G A T G C A T T G A G T A T C A T AWindow size=5Stringency=3Match=1 Mismatch=0ATACTACAAGACACGTACCGG C G A T G C A T T G A G T A T C A T AWindow size=5Stringency=3Match=1 Mismatch=0ATACTACAAGACACGTACCGG C G A T G C A T T G A G T A T C A T AWindow size=5Stringency=3Match=1 Mismatch=0G C G A T G C A T T G A G T A T C A T AATACTACAAGACACGTACCGWindow size=5Stringency=3Match=1 Mismatch=0G C G A T G C A T T G A G T A T C A T AATACTACAAGACACGTACCGG C G A T G C A T T G A G T A T C A T AATACTACAAGACACGTACCGa对人类Homo sapiens与黑猩猩Pongo pygmaeus的球蛋白基因序列进展比较的完好点阵图b利用滑动窗口对以上的两种球蛋白基因序列进展比较的点阵图，其中窗口大小为10个核苷酸，类似度阈值为8，即10个核苷酸中有8个一样时就打一个点abo优点o直观性，整体性o点阵分析不依赖空位(gap)参数，可寻觅两序列间一切能够的残基匹配o不依赖任何先决条件，是一种可用于初步分析的理想工具o点阵分析允许随时动态地改动最高和最低界限值，可以用来探求区分信号和背景规范的严厉程度o 缺陷o 不能很好地兼容打分矩阵o 滑动窗口和预值的选择过于阅历化o 信噪比低 o 不适宜进展高通量的数据分析o DNA Strider(Macintosh)o cellbiol/soft.htm o Dotter(Unix/Linux,X-Windows)o COMPARE,DOTPLOT(GCG软件)o PLALIGN(FASTA)o Dotleto isrec.isb-sib.ch/java/dotlet/Dotlet.htmlo动态规划算法(Dynamic Programming Algorithm)是一种计算方法，它的主要思绪是把一个问题分成假设干个小问题来处理o在生物学中运用的两种动态规划算法：Needleman-Wunsch算法全局比对和Smith-Waterman算法部分比对o Eg.匹配=1,非匹配=0,空位罚分=-1o Sequence1:CACGAo Sequence2:CGA第一个位点得分剩余序列CC+1ACGAGA-C-1CACGAGAC-1ACGACGASi,j这个位置的分数为图中箭头所示三个方向值中最大的一个i-xi-1j-1i-yji Si-x,j -wx Si 1,j-1 +s(ai,bj)Si,j-y-wy Si,j 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的间隔罚分ACTTCGACTAG匹配3错配-1空位-2ACTTCG0ACTAG匹配3错配-1空位-2ACTTCG0-2ACTAG匹配3错配-1空位-2ACTTCG0-2-4-6-8-10-12ACTAG匹配3错配-1空位-2ACTTCG0-2-4-6-8-10-12A-2CTAG匹配3错配-1空位-2ACTTCG0-2-4-6-8-10-12A-2C-4T-6A-8G-10?S(2,2)-2+(-2)-2+(-2)0+3匹配3错配-1空位-2ACTTCG0-2-4-6-8-10-12A-23C-4T-6A-8G-10?S(2,3)-4+(-2)3+(-2)-2+(-1)匹配3错配-1空位-2ACTTCG0-2-4-6-8-10-12A-231C-4T-6A-8G-10匹配3错配-1空位-2ACTTCG0-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空位-2ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149A-8-3 2G-10-50匹配3错配-1空位-2ACTTCG0-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-3-5-7C-416420-2T-6-149753A-8-3 27864G-10-505679GGT-CATTCCAAACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 27864G-10-505679GGTAC-TTCCAA1.ACTTCGAC-TAG2.ACTTCGACT-AG3.ACTTCGACTA-G哪一个是最优比对哪一个是最优比对(optimal alignment)呢呢?记分矩阵Seq1:MPRCLCQRJNCBASeq2:PBRCKCRNJCJA匹配匹配=1，错配，错配=0，空，空位罚分位罚分=0Seq1:MPRCLCQRJNCBASeq2:PBRCKCRNJCJA求出阴影部分所能到达的最大值填入当前位置，并记下到达这一位置的途径Seq1:MPRCLCQRJNCBASeq2:PBRCKCRNJCJA5 MPRCLCQRJNCBA PBRCKCRNJCJAResult：F(i-1,j-1)+s(ai,bj),F(i,j)=max F(i,j-1)-wy,F(i-1,j)-wx.0动态规划算法Smith-Waterman 算法算法AACCTATAGCT000000000000G000000000100C000110000021G000000000101A011000101000T000001021001A011000203210T000001132212A011000224321匹配匹配=1非匹配非匹配=-1空位空位=-1AACCTATAGCT000000000000G000000000100C000110000021G000000000101A011000101000T000001021001A011000203210T000001132212A011000224321A A C C T A T A G C T-G C G A T A T A-匹配匹配=1非匹配非匹配=-1空位空位=-1o Genetics Computer Group(GCG)程序 GAP(Needleman-Wunsch algorithm)and BESTFIT(Smith-Waterman algorithm)o 最类似的比对表示为:,较类似的表示为.无相关的表示为空格,carboxy-terminaloDNA计分矩阵o蛋白质计分矩阵o广泛运用的两种矩阵o PAM o BLOSUMo空位罚分oDNA Scoring MatricesoAmino Acid Substitution MatricesoPAM(Point Accepted Mutation)oBLOSUM(Blocks Substitution Matrix)actaccagttcatttgatacttctcaaataccattaccgtgttaactgaaaggacttaaagactSequence 1Sequence 2AGCTA1000G0100C0010T0001匹配:1错配:0分值：5CTAG嘧啶嘌呤 表示转换(transition)，表示颠换(transversions)转换比颠换更容易发生AGTCA0.99G0.0060.99T0.0020.0020.99C0.0020.0020.0060.99转换速率是颠换3倍时的模型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 .o 氨基酸容易被其它生化、物理特性类似的氨基酸交换o PAM1(1个PAM单位被定义为每100个残基出现一个被接受的点突变(氨基酸的置换不引起蛋白质功能上的显著变化o PAMn是PAM1自乘n次o PAM250、PAM120、PAM80和PAM60矩阵可用于类似性分别为20%、40%、50%和60%的序列比对 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 u模块交换矩阵BLOSUM以序列片段为根底,它是 基于蛋白质模块(Block)数据库而建立起来的 u 在模块比对的每一列中，分别计算u 两两氨基酸的变化情况,来自一切u 模块的数值被用来计算BLOSUM矩阵u矩阵后面的数字表示构建此矩阵所用的u 序列的类似程度，如BLOSUM62表示由u 类似度为62%的序列构建AACECA-C =0A-E =-1C-E =-4A-A =4C-C =9AACECn 普通来说,在部分类似性搜索上，BLOSUM 矩阵较PAM要好n当比较间隔相近的蛋白时，应选择低的PAM或高的BLOSUM矩阵；当比较间隔较远的蛋白时，应选择高的PAM或低的BLOSUM矩阵 n 对于数据库搜索来说普通选择BLOSUM62矩阵nPAM矩阵可用于寻觅蛋白质的进化来源，BLOSUM矩阵用于发现蛋白质的保守域n同源性(Homologous Genes)：序列来自共同的祖先，类似的序列往往具有同源性n类似性(Similarity)：两序列根据某种参数设定而表现出来的相近性o 类似的序列并不一定同源o 类似性是可以被量化的“计分表，它是匹配的数量除以比对的长度，通常以百分比%表示o 同源性一定是指序列来自共同的祖先o 同源性是一个定性的概念，不能运用序列间具有百分之多少同源性来定义n 直系同源(Orthologs)：具有共同祖先与类似功能的同源基因无基因复制事件n 旁系同源(Paralogs)：两个物种A和B的同源基因，分别是共同祖先基因组中由复制事件而产生的不同拷贝的后代谢谢！