双序列比对课件

课程主线序列比对基本概念空位罚分相似性与同源性双序列比对方法点阵序列比较(DotMatrixSequenceComparison)动态规划算法(DynamicProgrammingAlgorithm)记分矩阵1课程主线序列比对基本概念11什么是序列比对？

序列比对(SequenceAlignment)是通过在序列中搜索一系列单个性状或性状模式来比较2个（双序列比对）或更多（多重序列比对）序列的方法按比对序列条数分类双序列比对：两条序列的比对多序列比对：三条或以上序列的比对2什么是序列比对？

序列比对(SequenceAlignme2我们为什么关注序列比对？相似的序列可能具有相似的功能与结构发现一个基因或蛋白哪些区域容易发生突变，哪些位点突变后对功能没有影响发现生物进化方面的信息3我们为什么关注序列比对？相似的序列可能具有相似的功能与结构33序列比对两种类型全局序列比对定义：在全局范围内对两条序列进行比对打分的方法适合于非常相似且长度近似相等的序列局部序列比对定义：一种寻找匹配子序列的序列比对方法适合于一些片段相似而另一些片段相异的序列4序列比对两种类型全局序列比对44序列比对两种类型5序列比对两种类型55空位罚分(GapPenalties)空位为了获得两个序列最佳比对，必须使用空位和空位罚分空位罚分分类：空位开放罚分(Gapopeningpenalty)空位扩展罚分(Gapextensionpenalty)最优的序列比对通常具有以下两下特征：尽可能多的匹配尽可能少的空位插入任意多的空位会产生较高的分数，但找到的并不一定是真正相似序列6空位罚分(GapPenalties)空位为了获得两个序列最61GTGATAGACAC|||1GTGCATAGACAC

空位罚分允许空位但不罚分

不允许有空位

match=5mismatch=-41GTG-ATAGACAC|||||||||||1GTGCATAGACAC

1GTG--ATAGACAC|||||||||||1GTGC-ATAGACAC

?Score:-21Score:5571GTGATAGACAC空位罚分允许空位但不罚分 不允许有7空位罚分公式

ATGTTATACTATGTGCGTATA

Score=4参数:匹配=1非匹配=0g=3 r=0.1 x=3

score：8-3.2=4.8

Wx=g+r(x-1)Wx: 空位总记分g: 空位开放罚分r: 空位扩展罚分x: 空位长度TATGTGCGTATA

insertion/deletionATGT---TATACWx=-3-(3-1)0.1=-3.28空位罚分公式ATGTTATACTAT8双序列比对方法点阵序列比较(DotMatrixSequenceComparison)动态规划算法(DynamicProgrammingAlgorithm)词或K串方法(WordorK-tupleMethods)9双序列比对方法点阵序列比较(DotMatrixSequ9点阵序列比较点阵(DotMatrix)分析是一种简单的图形显示序列相似性的方法沿X轴上序列1中的每一个单元（核苷酸或氨基酸）与沿Y轴的第二个序列中的每一个单元进行比较，相同的区域在点阵图中显示为由点组成的对角线，对角线之外零散的点为背景噪音10点阵序列比较点阵(DotMatrix)分析是一种简单的图形10111111121212点阵分析的应用自身比对寻找序列中的正向或反向重复序列蛋白质的重复结构域(domain)相同残基重复出现的低复杂区(LowComplexity)RNA二级结构中的互补区域等对两条序列的相似性作整体的估计13点阵分析的应用自身比对1313点阵分析中的插入或删除TACTGTCAT

TACTGTTCATSequence1Sequence2TACTG

-

TCAT|||||||||TACTGTTCAT插入空位14点阵分析中的插入或删除TSequence1Sequence14点阵分析的应用人类低脂受体(humanlow-densitylipoproteinreceptor)自身比对发现正向重复序列具有连续相似区域的两条DNA序列的简单点阵图正向重复15点阵分析的应用人类低脂受体(humanlow-densit15点阵分析实例编码噬菌体λcⅠ（水平轴）和噬菌体P22c2（垂直轴）的氨基酸序列间的点阵分析相同的点打印全部打印，很难找到有用的信息16点阵分析实例编码噬菌体λcⅠ（水平轴）和噬菌体P22c2（16使用滑动窗口技术降低噪声TACGGTATGACAGTATCTACGGTATG

ACAGTATCTACGGTATG

ACAGTATCTACGGTATG

ACAGTATCC

T

A

T

G

A

C

A

T A C G G T A T GWindow=3WordSize=317使用滑动窗口技术降低噪声TACGGTATGT17ATACTACAAGACACGTACCGGCGATGCATTGAGTATCATAWindowsize=5Stringency=3Match=1Mismatch=018ATACTACAAGACACGTACCGGCG18ATACTACAAGACACGTACCGGCGATGCATTGAGTATCATAWindowsize=5Stringency=3Match=1Mismatch=019ATACTACAAGACACGTACCGGCG19ATACTACAAGACACGTACCGGCGATGCATTGAGTATCATAWindowsize=5Stringency=3Match=1Mismatch=020ATACTACAAGACACGTACCGGCG20GCGATGCATTGAGTATCATAATACTACAAGACACGTACCGWindowsize=5Stringency=3Match=1Mismatch=021GCGATGC21GCGATGCATTGAGTATCATAATACTACAAGACACGTACCG22GCGATGC22GCGATGCATTGAGTATCATAATACTACAAGACACGTACCG23GCGATGC23使用滑动窗口技术降低噪声（a）对人类（Homosapiens）与黑猩猩（Pongopygmaeus）的β球蛋白基因序列进行比较的完整点阵图（b）利用滑动窗口对以上的两种球蛋白基因序列进行比较的点阵图，其中窗口大小为10个核苷酸，相似度阈值为8，即10个核苷酸中有8个相同时就打一个点ab24使用滑动窗口技术降低噪声（a）对人类（Homosapien24点阵分析的优缺点优点直观性，整体性点阵分析不依赖空位(gap)参数，可寻找两序列间所有可能的残基匹配不依赖任何先决条件，是一种可用于初步分析的理想工具点阵分析允许随时动态地改变最高和最低界限值，可以用来摸索区分信号和背景标准的严格程度25点阵分析的优缺点优点2525点阵分析的优缺点缺点不能很好地兼容打分矩阵滑动窗口和预值的选择过于经验化信噪比低不适合进行高通量的数据分析26点阵分析的优缺点缺点2626点阵分析程序DNAStrider(Macintosh)/soft.htm

Dotter(Unix/Linux,X-Windows)COMPARE,DOTPLOT(GCG软件)PLALIGN(FASTA)Dotlethttp://www.isrec.isb-sib.ch/java/dotlet/Dotlet.html27点阵分析程序DNAStrider(Macintosh)227282828动态规划算法动态规划算法(DynamicProgrammingAlgorithm)是一种计算方法，它的主要思路是把一个问题分成若干个小问题来解决在生物学中应用的两种动态规划算法：Needleman-Wunsch算法（全局比对）和Smith-Waterman算法（局部比对）29动态规划算法动态规划算法(DynamicProgrammi29序列比对中某一位点匹配的三种可能性Eg.匹配=1,非匹配=0,空位罚分=-1Sequence1:CACGASequence2:CGA30序列比对中某一位点匹配的三种可能性Eg.匹配=1,非匹配=30动态规划算法的正式表述Si,j这个位置的分数为图中箭头所示三个方向值中最大的一个i-xi-1j-1i-yjiSi-x,j-wx

Si–1,j-1+s(ai,bj)Si,j-y-wy

Si,j31动态规划算法的正式表述Si,j这个位置的分数为图中箭头所示三31动态规划算法的数学形式Sij=max{Si-1,j-1,+s(aibj),

max

x≥1(Si-x,j-wx),

max

y≥1(Si,j-y-wy)

}Sij=max{Si-1,j-1,+s(aibj),

max

x≥1(Si-1,j-wx),max

y≥1(Si,j-1-wy)

}公式一的简化公式一公式二说明：Sij是序列a在位置i和序列b在位置j的分值，s(aibj)是位置i和j上比对分值，wx是在序列a中长度为x的间隔罚分，wy是序列b中长度为y的间隔罚分32动态规划算法的数学形式Sij=max{Si-1,j-1,+s32动态规划算法实例匹配＝3错配＝-1空位＝-233动态规划算法实例匹配＝33333动态规划算法实例匹配＝3错配＝-1空位＝-234动态规划算法实例匹配＝33434动态规划算法实例匹配＝3错配＝-1空位＝-235动态规划算法实例匹配＝33535动态规划算法实例匹配＝3错配＝-1空位＝-236动态规划算法实例匹配＝33636动态规划算法实例匹配＝3错配＝-1空位＝-237动态规划算法实例匹配＝33737动态规划算法实例?S(2,2)-2+(-2)-2+(-2)0+3匹配＝3错配＝-1空位＝-238动态规划算法实例?S(2,2)-2+(-2)-2+(-2)038动态规划算法实例?S(2,3)-4+(-2)3+(-2)-2+(-1)匹配＝3错配＝-1空位＝-239动态规划算法实例?S(2,3)-4+(-2)3+(-2)-39动态规划算法实例匹配＝3错配＝-1空位＝-240动态规划算法实例匹配＝34040动态规划算法实例S(4,4)4+(-2)4+(-2)6+3匹配＝3错配＝-1空位＝-241动态规划算法实例S(4,4)4+(-2)4+(-2)641动态规划算法实例匹配＝3错配＝-1空位＝-242动态规划算法实例匹配＝34242GGT-CATTCCAA回溯43GTCTCA回溯4343GGT-CATTCCAA44GTCTCA4444GGTAC-TTCCAA45GTCTCA4545比对结果1. ACTTCG AC-TAG2. ACTTCG ACT-AG3. ACTTCG ACTA-G哪一个是最优比对(optimalalignment)呢?记分矩阵46比对结果1. ACTTCG哪一个是最优比对(optimal46Needleman-Wunsch算法Seq1:MPRCLCQRJNCBASeq2:PBRCKCRNJCJA匹配=1，错配=0，空位罚分=047Needleman-Wunsch算法Seq1:MPRCLC47Needleman-Wunsch算法Seq1:MPRCLCQRJNCBASeq2:PBRCKCRNJCJA求出阴影部分所能达到的最大值填入当前位置，并记下到达这一位置的路径48Needleman-Wunsch算法Seq1:MPRCLC48Needleman-Wunsch算法Seq1:MPRCLCQRJNCBASeq2:PBRCKCRNJCJA549Needleman-Wunsch算法Seq1:MPRCLC49Needleman-Wunsch算法

MP–RCLCQR–JNCBA

–PBRCKC–RNJ–CJAResult：50Needleman-Wunsch算法Result：5050

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算法Smith-Waterman算法51 F(i-1,j-1)+s(ai,bj),051Smith-Waterman算法匹配=1非匹配=-1空位=-152Smith-Waterman算法匹配=15252Smith-Waterman算法AAC–CTATAGCT-GCGATATA---匹配=1非匹配=-1空位=-153Smith-Waterman算法AAC–CTA53GeneticsComputerGroup(GCG)程序GAP(Needleman-Wunschalgorithm)andBESTFIT(Smith-Watermanalgorithm)最相似的比对表示为‘:’,较相似的表示为‘.’无相关的表示为空格,‘’carboxy-terminal54GeneticsComputerGroup(GCG)54记分矩阵与空位罚分DNA计分矩阵蛋白质计分矩阵广泛使用的两种矩阵

PAMBLOSUM空位罚分55记分矩阵与空位罚分DNA计分矩阵5555记分矩阵(SCORINGMATRICES)DNAScoringMatricesAminoAcidSubstitutionMatricesPAM(PointAcceptedMutation)BLOSUM(BlocksSubstitutionMatrix)56记分矩阵(SCORINGMATRICES)DNAScor56DNA计分矩阵actaccagttcatttgatacttctcaaataccattaccgtgttaactgaaaggacttaaagactSequence1Sequence2

A G C TA

1 0 0 0G 0 1 0 0C 0 0 1 0T 0 0 0 1匹配:1错配:0分值：557DNA计分矩阵actaccagttcatttgatacttc57转换和颠换CTAG嘧啶嘌呤表示转换(transition)，表示颠换(transversions)转换比颠换更容易发生58转换和颠换CTAG嘧啶嘌呤表示转换(tran58转换和颠换转换速率是颠换3倍时的模型59转换和颠换转换速率是颠换3倍时的模型5959蛋白质计分矩阵PTHPLASKTQILPEDLASEDLTIPTHPLAGERAIGLARLAEEDFGMSequence1Sequence2记分矩阵T:G =-2T:T =5Score =48 C S T P A G N D

. .C 9 S -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.. C S T P A G N D

. .C 9 S -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蛋白质计分矩阵PTHPLASKTQILPEDLASEDLTI60PAM(PercentAcceptedMutation)矩阵氨基酸容易被其它生化、物理特性相似的氨基酸替换PAM1(1个PAM单位）被定义为每100个残基出现一个被接受的点突变(氨基酸的置换不引起蛋白质功能上的显著变化）PAMn是PAM1自乘n次PAM250、PAM120、PAM80和PAM60矩阵可用于相似性分别为20%、40%、50%和60%的序列比对61PAM(PercentAcceptedMutation61

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