pairwise-alignment研究生生物信息学课件03.pptx

《pairwise-alignment研究生生物信息学课件03.pptx》由会员分享，可在线阅读，更多相关《pairwise-alignment研究生生物信息学课件03.pptx（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、什么是序列比对？什么是序列比对？序列比对序列比对(Sequence Alignment)是通过在序是通过在序列中搜索一系列单个性状或性状模式来比较列中搜索一系列单个性状或性状模式来比较2个（双序列比对）或更多（多重序列比对）个（双序列比对）或更多（多重序列比对）序列的方法序列的方法序列比对分类序列比对分类双序列比对：两条序列的比对双序列比对：两条序列的比对多序列比对：三条或以上序列的比对多序列比对：三条或以上序列的比对 牛牛文库文档分享我们为什么关注序列比对我们为什么关注序列比对相似的序列可能具有相同的功能与结构相似的序列可能具有相同的功能与结构发现一个基因或蛋白哪些区域容易发生突变，哪些发现

2、一个基因或蛋白哪些区域容易发生突变，哪些位点突变后对功能没有影响位点突变后对功能没有影响 发现生物进化方面的信息发现生物进化方面的信息同源性同源性(Homologous Genes)：序列来自共同的祖先，：序列来自共同的祖先，或具有共同的进化史，相似的序列往往具有同源性或具有共同的进化史，相似的序列往往具有同源性(如图如图)相似性相似性(Similarity)：两序列根据某种参数相近，但相似：两序列根据某种参数相近，但相似的序列不一定具有同源性。相似性的序列不一定具有同源性。相似性同源性，两基因只有同源性，两基因只有同源与非同源关系同源与非同源关系 牛牛文库文档分享我们为什么关注序列比对（续）

3、我们为什么关注序列比对（续）直系同源直系同源(Orthologs)：具有共同祖先与相似功：具有共同祖先与相似功能的同源基因（无基因复制事件）能的同源基因（无基因复制事件）旁系同源旁系同源(Paralogs)：两个物种：两个物种A和和B的同源基因，的同源基因，分别是共同祖先基因组中由复制事件而产生的不分别是共同祖先基因组中由复制事件而产生的不同拷贝的后代同拷贝的后代趋同进化趋同进化(Convergent evolution):序列中的相似序列中的相似区域可能不具有共同的祖先，而是通过两条进化区域可能不具有共同的祖先，而是通过两条进化路径独立获得相同的功能（路径独立获得相同的功能（如图如图） 牛牛

4、文库文档分享同源序列与祖先序列关系同源序列与祖先序列关系进化距离：一个序列变成另一个序列所需的步骤数。进化距离：一个序列变成另一个序列所需的步骤数。如如A变为变为B的进化距离为：的进化距离为：x+ 牛牛文库文档分享基因进化基因进化AB：物种：物种I与物种与物种II中的中的a1是直系同源，是直系同源，a1与与a2为旁系同源为旁系同源C：趋同进化，物种：趋同进化，物种I与物种与物种II经历不同的进化途径，产生相同的功能经历不同的进化途径，产生相同的功能D：基因转移，称为水平转移基因：基因转移，称为水平转移基因 牛牛文库文档分享序列比对两种类型序列比对两种类型全局序列比对全局序列比对l定义：在全局范

5、围内对两条序列进行比对打分的方法定义：在全局范围内对两条序列进行比对打分的方法l适合于非常相似且长度近似相等的序列适合于非常相似且长度近似相等的序列局部序列比对局部序列比对l定义：一种寻找匹配子序列的序列比对方法定义：一种寻找匹配子序列的序列比对方法 l适合于一些片段相似而另一些片段相异的序列适合于一些片段相似而另一些片段相异的序列 Global Alignment Local L G P S S K Q T G K G S-S R I W D N|L N-I T K S A G K G A I M R L G D A T G K G|A G K G 牛牛文库文档分享记分矩阵与空位罚分记分矩阵

6、与空位罚分DNA 计分矩阵计分矩阵蛋白质计分矩阵蛋白质计分矩阵 广泛使用的两种矩阵广泛使用的两种矩阵 PAM BLOSUM空位罚分空位罚分 牛牛文库文档分享DNA 计分矩阵计分矩阵actaccagttcatttgatacttctcaaataccattaccgtgttaactgaaaggacttaaagactSequence 1Sequence 2AGCTA1000G0100C0010T0001匹配:1错配:0分值： 牛牛文库文档分享转换和颠换转换和颠换CTAG嘧啶嘧啶嘌呤嘌呤 表示表示转换转换(transition)，表示表示颠换颠换(transversions)转换比颠换更容易发生转换比颠换

7、更容易发生 牛牛文库文档分享转换和颠换转换和颠换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

8、-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 牛牛文库文档分享PAM(Point Accepted Mutation)矩阵矩阵氨基酸记分系统需要替换的模式来提高灵敏度以检测弱的相氨基酸记分系统需要替换的模式来提高灵敏度以检测弱的相似性似性氨基酸容易被其它生化、物理特性相似的氨基酸替换氨基酸容易被其它生化、物理特性相似的氨基酸替换PAM矩阵给出了进化过程中同源蛋白质从一个氨基酸变到另矩阵给出了进化过程中同源蛋白质从一个氨基酸变到另一个氨基酸

9、的似然率一个氨基酸的似然率(Likelihood)PAM1(1个个PAM单位）被定义为每单位）被定义为每100个残基出现一个被接个残基出现一个被接受的点突变受的点突变(氨基酸的置换不引起蛋白质功能上的显著变化）氨基酸的置换不引起蛋白质功能上的显著变化）PAMn是是PAM1自乘自乘n次次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

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

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

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

13、 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 250C-817WW 牛牛文库文档分享 u模块替换矩阵模块替换矩阵BLOSUM以序列片段为基础以序列片段为基础,它是它是 基于蛋白质模块基于蛋白质模块(Block)数据库而建立起来的数据库而建立起来的 u 在模块比对的每一列中，分别计算在模块比对的每一列中，分别计算 两两氨基酸的变化情况两两氨基酸的变化情况,来自所有来自所有 模块的数值被用来计算模块的数值被用来计算BLOSUM矩阵矩阵u矩阵后面的数

14、字表示构建此矩阵所用的矩阵后面的数字表示构建此矩阵所用的 序列的相似程度，如序列的相似程度，如BLOSUM62表示由表示由 相似度为相似度为62%的序列构建的序列构建AACECA-C =4A-E =2C-E =2A-A =1C-C =1AACECBLOSUM矩阵矩阵(Blocks Substitution Matrix) 牛牛文库文档分享BLOSUM62 牛牛文库文档分享如何选择合适的评分矩阵？如何选择合适的评分矩阵？n 一般来说一般来说,在局部相似性搜索上，在局部相似性搜索上，BLOSUM 矩阵矩阵较较PAM要好要好n当比较距离相近的蛋白时，应选择低的当比较距离相近的蛋白时，应选择低的PAM

15、或高或高的的BLOSUM矩阵；当比较距离较远的蛋白时，应选矩阵；当比较距离较远的蛋白时，应选择高的择高的PAM或低的或低的BLOSUM矩阵矩阵 n 对于数据库搜索来说一般选择对于数据库搜索来说一般选择BLOSUM62矩阵矩阵nPAM矩阵可用于寻找蛋白质的进化起源，矩阵可用于寻找蛋白质的进化起源，BLOSUM矩阵用于发现蛋白质的保守域矩阵用于发现蛋白质的保守域 牛牛文库文档分享空位罚分空位罚分(Gap Penalties)空位为了获得两个序列最佳比对，必须使用空位和空位为了获得两个序列最佳比对，必须使用空位和空位罚分空位罚分空位罚分分为：空位开放罚分空位罚分分为：空位开放罚分(Gap openi

16、ng penalty)和空位扩展罚分和空位扩展罚分(Gap extension penalty)最优的序列比对通常具有以下两下特征：最优的序列比对通常具有以下两下特征：尽可能多的匹配尽可能多的匹配尽可能少的空位尽可能少的空位插入任意多的空位会产生较高的分数，但找到的并插入任意多的空位会产生较高的分数，但找到的并不一定是真正相似序列不一定是真正相似序列 牛牛文库文档分享1 GTGATAGACAC|1 GTGCATAGACAC空位罚分空位罚分允许空位但不罚分允许空位但不罚分 Score:55 不允许有空位不允许有空位 Score:-21匹配匹配=5错配错配=-41 GTG-ATAGACAC|1 G

17、TGCATAGACAC1 GTG-ATAGACAC|1 GTGC-ATAGACAC? 牛牛文库文档分享空位罚分公式空位罚分公式 A T G T T A T A CT A T G T G C G T A T A 总分：总分：4空位参数空位参数:g=3(空位开放罚分空位开放罚分)r=0.1(空位扩展罚分空位扩展罚分)x=3(空位长度空位长度)Wx=-3-(3-1)0.1=-3.2 匹配匹配=1错配错配=0总分：总分：8-3.2=4.8Wx=g+r(x-1)Wx 为总空位记分，为总空位记分，g为空位开为空位开放罚分，放罚分，r为空位扩展罚分，为空位扩展罚分，x为空位长度为空位长度T A T G T

18、G C G T A T A insertion/deletionA T G T-T A T A C 牛牛文库文档分享双序列比对方法双序列比对方法点阵序列比较点阵序列比较(Dot Matrix Sequence Comparison)动态规划算法动态规划算法(Dynamic Programming Algorithm)词或词或K串方法串方法(Word or K-tuple Methods)贝叶斯统计方法贝叶斯统计方法(Bayesian Statistical Methods) 牛牛文库文档分享点阵序列比较点阵序列比较(Dot Matrix Sequence Comparison)点阵分析是一种简

19、单的图形显示序列相似性点阵分析是一种简单的图形显示序列相似性的方法的方法,Gibbs&McIntyre(1970)沿沿X轴上序列轴上序列1中的每一个单元（核苷酸或氨中的每一个单元（核苷酸或氨基酸）与沿基酸）与沿Y轴的第二个序列中的每一个单元轴的第二个序列中的每一个单元进行比较，相同的区域在点阵图中显示为由进行比较，相同的区域在点阵图中显示为由点组成的对角线，对角线之外零散的点为背点组成的对角线，对角线之外零散的点为背景噪音景噪音 牛牛文库文档分享IONIZATIONIONIZATION 牛牛文库文档分享点阵分析中的插入或删除点阵分析中的插入或删除TACTGTCAT T A C T G T T

20、C A TSequence 1Sequence 2T A C T G-T C A T|T A C T G T T C A T插入空位 牛牛文库文档分享点阵分析的应用点阵分析的应用自身比对自身比对寻找序列中的正向或反向重复序列寻找序列中的正向或反向重复序列蛋白质的重复结构域蛋白质的重复结构域(domain)相同残基重复出现的低复杂区相同残基重复出现的低复杂区(Low Complexity)RNA二级结构中的互补区域等二级结构中的互补区域等对两条序列的相似性作整体的估计对两条序列的相似性作整体的估计 牛牛文库文档分享点阵分析的应用自身比对发现自身比对发现正向重复序列正向重复序列具有连续相似区域的两

21、条具有连续相似区域的两条DNADNA序列的简单点阵图序列的简单点阵图正向重复 牛牛文库文档分享点阵分析实例点阵分析实例编码噬菌体编码噬菌体c（水平轴）和（水平轴）和噬菌噬菌体体P22 c2（垂直轴）（垂直轴）的氨基酸序列间的的氨基酸序列间的点阵分析点阵分析相同的点打印全部相同的点打印全部打印，很难找到有打印，很难找到有用的信息用的信息 牛牛文库文档分享使用滑动窗口技术降低噪声使用滑动窗口技术降低噪声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 C

22、T 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= 牛牛文库文档分享使用滑动窗口技术降低噪声使用滑动窗口技术降低噪声（a a）对人类（）对人类（Homo sapiensHomo sapiens）与黑猩猩（）与黑猩猩（Pongo pygmaeusPongo pygmaeus）的）的球蛋白基因序列进行比较的完整点阵图球蛋白基因序列进行比较的完整点阵图（b b）利用滑动窗口对以上的两种球蛋白基因序列进行比较的点阵图，其中窗口大小为）利用滑动窗口对以上的两种球蛋白基因序列进行比较的点

23、阵图，其中窗口大小为1010个核苷酸，个核苷酸，相似度阈值为相似度阈值为8 8，即，即1010个核苷酸中有个核苷酸中有8 8个相同时就打一个点个相同时就打一个点 牛牛文库文档分享点阵分析的优缺点点阵分析的优缺点优点优点直观性，整体性直观性，整体性点阵分析不依赖空位点阵分析不依赖空位(gap)参数，可寻找两序列参数，可寻找两序列间所有可能的残基匹配间所有可能的残基匹配不依赖任何先决条件，是一种可用于初步分析的不依赖任何先决条件，是一种可用于初步分析的理想工具理想工具点阵分析允许随时动态地改变最高和最低界限值，点阵分析允许随时动态地改变最高和最低界限值，可以用来摸索区分信号和背景标准的严格程度可以

24、用来摸索区分信号和背景标准的严格程度 牛牛文库文档分享点阵分析的优缺点点阵分析的优缺点缺点缺点不能很好地兼容距离矩阵不能很好地兼容距离矩阵滑动窗口和预值的选择过于经验化滑动窗口和预值的选择过于经验化信噪比较低信噪比较低 不适合进行高通量的数据分析不适合进行高通量的数据分析 牛牛文库文档分享点阵分析程序点阵分析程序DNA Strider(Macintosh)http:/ Dotter(Unix/Linux,X-Windows)COMPARE,DOTPLOT in GCGPLALIGN(FASTA)Dotlethttp:/www.isrec.isb-sib.ch/java/dotlet/D 牛牛文

25、库文档分享 牛牛文库文档分享动态规划算法动态规划算法动态规划算法动态规划算法(Dynamic Programming Algorithm)是综合运用是综合运用分级决策方法分级决策方法和和最优最优化原理化原理而形成的数学方法。而形成的数学方法。主要思路是把一个复杂问题分成若干个关联的子主要思路是把一个复杂问题分成若干个关联的子问题，找出子问题的最优解，进而得出原来复杂问题，找出子问题的最优解，进而得出原来复杂问题的最优解。问题的最优解。 牛牛文库文档分享动态规划算法动态规划算法在序列比对尤其是双序列比对中非常重要。在序列比对尤其是双序列比对中非常重要。将比对过程分为若干步，每一步增加一个位将比对

26、过程分为若干步，每一步增加一个位置。可提供序列间最优的对位排列。置。可提供序列间最优的对位排列。应用最多的两种动态规划算法：应用最多的两种动态规划算法：Needleman-Wunsch（全局比对）（全局比对）Smith-Waterman（局部比对）（局部比对） 牛牛文库文档分享动态规划算法动态规划算法填充矩阵填充矩阵构建矩阵构建矩阵确定递归计算方法确定递归计算方法矩阵回溯矩阵回溯 牛牛文库文档分享动态规划算法的简单描述动态规划算法的简单描述序序列列b序列序列 牛牛文库文档分享动态规划算法的正式表述动态规划算法的正式表述S Si,ji,j这个位置这个位置的分数为图中的分数为图中箭头所示三个箭头所

27、示三个方向值中最大方向值中最大的一个的一个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-w),maxy 1(Si,j-1-w)公式一的简化公式一公式一公式二公式二说明：说明：Sij是序列是序列a a在位置在位置i i和序列和序列b b在位置在位置j j的分值，的分值，s(as(

28、ai ib bj j)是位置是位置i i和和j j上比对分值，上比对分值，w wx x是在序列是在序列a a 中长度为中长度为x x的空位罚的空位罚分，分，w wy y是序列是序列b b中长度为中长度为y y的空位罚分。的空位罚分。 牛牛文库文档分享Needleman-Wunsch动态规划算法举例动态规划算法举例例例:用动态规划算法比对以下两条序列用动态规划算法比对以下两条序列序列序列a:ACTTCG序列序列b:ACTAG记分规则记分规则:匹配匹配3错配错配-2空位空位- 牛牛文库文档分享Scoring MatrixACTTCGACTAG 牛牛文库文档分享ACTTCG0ACTAGScoring

29、 M 牛牛文库文档分享ACTTCG0-2ACTAGScoring M 牛牛文库文档分享ACTTCG0-2-4-6-8-10-12ACTAGScoring M 牛牛文库文档分享ACTTCG0-2-4-6-8-10-12A-2C-4T-6A-8G-10Scoring M 牛牛文库文档分享ACTTCG0-2-4-6-8-10-12A-23CTAGScoring M 牛牛文库文档分享ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 27755G-10-505558GGT-CATTCCAA回溯回溯Scoring M 牛牛文库文档分享A

30、CTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 27755G-10-505558GGT-CATTCCAAScoring Matrix什么是第三什么是第三种可能？种可能？ 牛牛文库文档分享ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 27755G-10-505558GGTTCCAAScoring MatrixTAC- 牛牛文库文档分享当完成所有矩阵单元的分值计算后，接下来当完成所有矩阵单元的分值计算后，接下来就是从高分值单元开始找出最大分值路径，就是从高

31、分值单元开始找出最大分值路径，也就是找出最佳匹配。这个过程被称为也就是找出最佳匹配。这个过程被称为回溯回溯(backtracking)。由于在计算过程中到达每一个矩阵单元的最由于在计算过程中到达每一个矩阵单元的最优路径都被储存在回溯矩阵中，所以就可以优路径都被储存在回溯矩阵中，所以就可以方便地找出最优路径（红色数字表示最优路方便地找出最优路径（红色数字表示最优路径）。径）。 牛牛文库文档分享Smith-Waterman算法算法 NeedlemanWunsch算法适用于整体水平上相似性程度算法适用于整体水平上相似性程度较高的两个序列。如果两个序列的亲缘关系较远，它们在较高的两个序列。如果两个序列

32、的亲缘关系较远，它们在整体上可能不具有相似性，但在一些较小的区域上却可能整体上可能不具有相似性，但在一些较小的区域上却可能存在局部相似性存在局部相似性 1981年年Smith和和Waterman提出了一种用来寻找并比较这提出了一种用来寻找并比较这些具有局部相似性区域的方法，即常用的些具有局部相似性区域的方法，即常用的Smith-Waterman算法算法 同样是基于矩阵的方法，而且也同样是运用回溯法建立允同样是基于矩阵的方法，而且也同样是运用回溯法建立允许空位插入的比对，不同之处在于许空位插入的比对，不同之处在于Smith-Waterman算法算法要从任何可能导致最大分值的地方才开始计分，矩阵中

33、的要从任何可能导致最大分值的地方才开始计分，矩阵中的每个单元均可以是比对结果序列片段的终点每个单元均可以是比对结果序列片段的终点 牛牛文库文档分享Smith-Waterman算法算法 Smith-Waterman算算法记分矩阵的两个关键点法记分矩阵的两个关键点:1.记分系统必须包括错配记分系统必须包括错配的负分值的负分值2.当记分为负时当记分为负时,此值设此值设为为0,其作用是使任何比对其作用是使任何比对都在那一点终止都在那一点终止 从这一算法的本身可从这一算法的本身可以看出，它属于以看出，它属于局部相似局部相似性比对性比对，而不是整体相似，而不是整体相似性比对。性比对。 牛牛文库文档分享谢谢！ 牛牛文库文档分享