第3讲-序列比对

1,序列比对,序列比对基本概念、打分矩阵与算法,2,序列比对的根本任务是：发现序列之间的相似性辨别序列之间的差异目的：相似序列相似的结构，相似的功能判别序列之间的同源性推测序列之间的进化关系,3,主要内容,一、概述1、生物序列之间的关系2、序列比对的概念3、序列比对的意义二、序列比对的得分系统1、核酸的得分矩阵2、蛋白质的得分矩阵3、空位罚分体系三、序列比对的算法,4,1、生物序列之间的关系,序列比对的理论基础是进化学说，如果两个序列之间具有足够的相似性，就推测二者可能有共同的进化祖先，经序列内残基或者序列片段的替换、插入、缺失等遗传编译过程分别演化而来。相似性高并不一定来自同一祖先。,5,原序列：ACGTTAGCGCTAGCTGCTAGCTAG替换：ACGCTAGCGCTAGCTGCTAGCTAG插入：ACGCTAGCGCTAGCTAGCTAGCTAG缺失：ACGCTAGCGCAGCTGCTAGCTG,6,同源性（homology）,同源性：两条序列有一个共同的进化祖先，那么它们是同源的。相似性（similarity）：序列间相似性的量度。同源性是序列同源或者不同源的一种论断，而相似性或者一致性是二个序列相关性的量化，是两个不同的概念。,7,直系同源（orthology）：不同物种内的同源序列。旁系同源（paralogy）：同一物种内的同源序列。,8,人类与模式生物小鼠,因为他们各自的kit基因都存在缺陷,9,基本概念：序列：由一些字母组成的字符串，包括核酸和蛋白质序列。字母表（alphabet），核酸序列（DNA序列）的字母表为ATGC，再加一个gap（-）。gap空位。字符串长度：AT-GGCC的长度为7。子序列【可以非连续】或子串（subsequence）：原序列中任意连续的一段序列，包括0长度和全长的序列。随机序列：每个位置出现ATGC中任何一个字符的概率都是1/4。也就没有什么生物学方面的意义。非随机序列也就是有生物学意义的序列。距离：两序列之间差异程度的一个量化数字，如两个序列完全相同则距离为0。,2、序列比对的概念,10,序列比对(alignment)，是根据特定的计分规则，将两个或多个符号序列按位置比较排列后，得到最具相似性的排列的过程。ACGCTAGCGCTAGCTGCTAGCTAGACGTTAGCGCTAGCTGCTAGCTAGACGCTAGCGCTAGCTGCTAGCTAGACGCTAGCGCAAGCTGCTAGCTG-ACGCTAGCGCAAGCTGCTAGCT-G,11,Query:181catcaactacaactccaaagacacccttacacccactaggatatcaacaaacctacccac240|Sbjct:189catcaactgcaaccccaaagccacccct-cacccactaggatatcaacaaacctacccac247,比对的三种情况,12,序列比对(alignment)，是根据特定的计分规则，将两个或多个符号序列按位置比较排列后，得到最具相似性的排列的过程。计分规则：序列相似性的计算规则规定匹配、不匹配、空位各自的得分如：匹配：1不匹配：0空格：0ACGCTAGCGCTAGCTGCTAGCTAGACGCTAGCGCAAGCTGCTAGCTG-21ACGCTAGCGCTAGCTGCTAGCTAGACGCTAGCGCAAGCTGCTAGCT-G22,13,记分矩阵（scoringmatrix），即记分规则。RawScore和Bitscore：比对得分。记分矩阵不同，可能得到不同的结果。,14,全局比对：序列全长进行比对，寻找一个最佳的配对。局部比对：子序列比对，只需要寻找局部的最佳匹配。比对的统计显著性E值。Algorithm算法。AATCTATAAAGATA,15,序列比对的关键问题：记分矩阵算法,16,3、序列比对的意义,序列比对(alignment)是序列分析的基础，其他一切都建立在序列比对的基础上。根据相似性推导可能的演化过程，确定亲缘关系，构建进化书。最常见的是蛋白质序列之间或者核酸序列之间的两两比对。通过比较两个序列之间的相似区域和保守性位点，寻找二者可能的分子进化关系。将多个序列同时比对，寻找这些有进化关系的序列之间共同的保守区域、位点和profile（概型），从而探索导致它们产生共同功能的序列模式（motif）。把蛋白质序列与核酸序列相比来探索核酸序列可能的表达框架。把蛋白质序列与具有三维结构信息的蛋白质相比，从而获得蛋白质折叠类型的信息。比对还是数据库搜索算法的基础。可以通过查询序列与整个数据库所有序列进行比对，从数据库中获得与其相似序列的已有数据，对于进一步分析其结构和功能会有很大的帮助。,17,确定特定的蛋白质或者核酸序列有哪些直系同源或旁系同源序列。【搜索整个数据库】确定哪些蛋白质和基因在特定的物种中出现。确定一个DNA或蛋白质序列身份。发现新基因。确定一个特定基因或者蛋白质有哪些已经被发现了的变种。研究可能存在多种剪接方式的表达序列标签。寻找对于一个蛋白质的功能和/或结构域起关键作用的氨基酸残基。,18,二、序列比对的得分系统,1、核酸的得分矩阵（WeightMatrices）核酸打分矩阵设DNA序列所用的字母表为=A，C，G，T,Query:181catcaactacaactccaaagacacccttacacccactaggatatcaacaaacctacccac240|Sbjct:189catcaactgcaaccccaaagccacccct-cacccactaggatatcaacaaacctacccac247,比对需要一个量化的分数。,19,1、核酸的得分矩阵（WeightMatrices）,a.等价矩阵,AGTCGAAATCGT,4,20,1、核酸的得分矩阵（WeightMatrices）,b.BLAST矩阵,AGTCGAAATCGT,?,12,21,1、核酸的得分矩阵（WeightMatrices）,c.转换颠换矩阵（transition，transversion）（嘌呤：腺嘌呤A，鸟嘌呤G；嘧啶：胞嘧啶C，胸腺嘧啶T）,AGTCGAAATCGT,?,-2,22,2、蛋白质打分矩阵,（i）等价矩阵（ii）遗传密码矩阵GCM（iii）疏水矩阵（iv）PAM矩阵（PointAcceptedMutation）（v）BLOSUM矩阵（BlocksAminoAcidSubstitutionMatrices）,其中Rij代表打分矩阵元素i、j分别代表字母表第i和第j个字符。,23,遗传密码矩阵,通过计算一个氨基酸残基转变到另外一个氨基酸残基所需的碱基变化的最小数目而得到。,24,疏水矩阵是根据氨基酸残基替换前后疏水性的变化而得到的矩阵。若一次氨基酸替换，疏水性不发生太大的变化，则这种替换得分高，否则替换得分低。,蛋白质疏水矩阵,25,PAM矩阵（PointAcceptedMutation）,基于进化的点突变模型，通过统计相似序列比对中的各种氨基酸替换发生率而得到该矩阵。如果两种特定的氨基酸之间替换发生得比较频繁，那么这一对氨基酸在得分矩阵中的互换得分就比较高。该记分矩阵科学，用得多。,26,矩阵集合-PAM-N如，PAM60矩阵用于比较相距60个PAM单位的序列。,27,c,s,t,p,28,针对不同的进化距离采用不同的PAM矩阵,序列相似度=40%50%60%,|打分矩阵=PAM120PAM80PAM60,PAM25014%-27%,29,BLOSUM62,模块氨基酸替换矩阵,30,相似度越低的序列，在比对的时候，采用PAM矩阵时，后面的数字越大，采用BLOSUM矩阵时，后面的数字越小。,31,3，空位罚分体系,一般有两种罚分方法：1，线性罚分2，仿射罚分（affinepenalty）原理在于一个位置变异的影响小于多个位置同时变异的影响。从生物学角度看，一个位置发生变异是一个突变事件，而多个位置发生变异可能是发生了多个进化（突变）事件。,AGTCGATAGTCGATAGT-TAGTCGAT,AGTCGATAGTCGATA-TCGAT-GTC-AT,32,三、序列比对的算法,点阵法动态规划法词或k串法（BLAST或FASTA中采用）。,33,点阵法,点阵法是最基本的，也是很重要的一种可视化序列比对方法。“矩阵作图法”或“对角线作图”。首先建立一个矩阵，两条序列的长度分别为矩阵的行数和列数，一条序列置于矩阵的顶部，一条序列置于矩阵的左侧。把具有相同字符的单元做标记。,34,对角线上的元素,如果两个序列完全相同，则对角线上每个位置都会出现标记。,35,其它位置的元素,其它位置如果出现连续的相同字符，同样可以在表中体现出来。,点阵图可以很直观的发现两条序列所有可能的匹配，这些匹配可能是某种功能域。也可用于寻找蛋白质或者DNA内部的重复或者反向重复区域,36,反向重复序列,序列1,序列2,37,滑动窗口技术,由于序列可能很长，而字符只有4个（核酸），所以会有很多随机性的没有生物学意义的相似性，这些是比对中的噪声。使用滑动窗口代替一次一个位点的比较是解决噪声问题的有效方法。假设窗口大小为10，相似度阈值为8，则每次比较取10个连续的字符，如相同的字符超过8个，则标记。基于滑动窗口的点矩阵方法可以明显地降低点阵图的噪声，并且明确无误的指示出了两条序列间具有显著相似性的区域。,38,滑动窗口的过滤,不连续的匹配可能是噪声，需要用滑动窗口过滤，滑动窗口有两个参数，一是窗口大小，二是阈值，也就是不匹配的字符个数。例如我们这个例子由于字符个数很少，用（3，0）的参数。,滑动窗口是这样使用的：从（1，1）位置出发，将序列1的13个字符与序列2的13个字符比较，如果都相同，则在（1，1）位置处做标记，一直到完成整个表。例如如上表中的（1，5）位置做了标记，是因为序列1的13个元素和序列2的57个元素是相同的。,39,（a）对人类（Homosapiens）与黑猩猩（Pongopygmaeus）的球蛋白基因序列进行比较的完整点阵图。（b）利用滑动窗口对以上的两种球蛋白基因序列进行比较的点阵图，其中窗口大小为10个核苷酸，相似度阈值为8。,(a)(b),40,点阵图的一个例子,1AAGGTCAGGAACAAAGAAACAGCTGAATACCAAACAGGATATCTGTGGTAAGCGGTTCCT61GCCCCGGCTCAGGGCCAAGAACAGATGAGACAGCTGAGTGATGGGCCAAACAGGATATCT121GTGGTAAGCAGTTCCTGCCCCGGCTCGGGGCCAAGAACAGATGGTCCCCAGATGCGGTCC,/molkit/dnadot/,两条相同序列的比对,41,课堂练习,GGGATCACGTATGCATTAGCATACATCACGCGG,CCGCGTGATGTATGCTAATGCATACGTGATCCC,第二条序列是第一条序列的反向互补序列，通过点阵图分析寻找序列可能的发夹状结构。思考：点阵法为什么可以发现RNA序列的发夹状结构？,发夹结构,42,双序列比对的动态规划算法,进行双序列比对最直接的方法是生成两序列的所有可能的比对，分别计算得分，然后挑选一个得分最高的比对作为最终结果。但可能的比对是序列长度的指数函数。,AATCGT,AGTCGA,AATCGT-,-ATCGTA,AATCGT-,-CGTCGA,43,N-W算法是一种全局比对动态规划算法，于1970年被提出，得到了非常广泛的应用。首先假设我们要对两条序列a和b进行比对，它们的长度分别为M和N，序列a的第i个字符（残基）为ai，序列b的第j个字符为bj。动态规划算法由四部分组成：1）存储子问题的最优化的动态规划矩阵；2）最优化的递归计算方法；3）给出自问题最优解的矩阵填充过程和4）寻找最优化比对路径的回溯方法。,Needleman-Wunsch算法,44,采用简单打分系统,匹配得4分，不匹配得3分，空位得4分，或者用前面讲过的计分矩阵。,为了量化，我们必须对各种配对情况给一个分数。,45,1）用来存储子问题的最优化动态规划矩阵,序列a,矩阵中每一元素的值S（i,j）代表b序列前i个字符与a序列前j个字符的最优比对得分。,序列b,46,假设我们已经得到了：长M-1的a序列和长N-1的b序列的最优比对长M-1的a序列和长N的b序列的最优比对长M的a序列和长N-1的b序列的最优比对那么对于长M的a序列和长N的b序列能否简单的得到最优比对呢？,？,M-1,N-1,3个红色圈的最佳值已知。,2）最优化的递归计算方法,47,长M的a序列和长N的b序列的最佳比对排列只能从三种方式中产生：,在长M-1的a序列和长N-1的b序列的最优比对基础上，a、b两序列各增加一个字符。,在长M-1的a序列和长N的b序列的最优比对基础上，a序列增加一个字符、b两序列增加一个空格。,在长M的a序列和长N-1的b序列的最优比对基础上，a序列增加一个空格、b两序列增加一个字符。,48,两个字符和出现在同一列中,这种情况下比对得分情况是怎么样的呢？,表示两条序列各去掉最后一个字符的最佳得分,表示两个字符配对的分值，见前面的打分系统。,这段比对得分已知,49,这种情况下比对得分情况是怎么样的呢？,与一个空位出现在同一列中,d表示空位罚分值。,与一个空位出现在同一列中的时候,序列a，b的最优比对得分是上述三种情况的最大值。,50,据此，我们可以写出一个概括性的公式,51,？,M-1,N-1,52,3）给出子问题最优解的矩阵填充过程,第一行、第一列初始化，第一行填入-id，第一列填入-jd，d为空位罚分。,53,其他矩阵元素按以下公式计算填入，并记录传递路线：,54,4）矩阵回溯以寻找最优比对路径,一旦整个矩阵填充完毕，就可以得到最优比对得分，即矩阵中最后一个得分，要找出最优比对排列方式，我们还需要对整个矩阵进行回溯。从矩阵的最后一个单元（M,N）开始，根据填充记录的路径，直到回溯到第一个单元（0，0）。斜线，则两条序列各顺序加一字符；横线，则a序列顺序加字符，b序列加空格；竖线，则a序列顺序加空格，b序列顺序加字符。,55,例题讲解,利用Needleman-Wunsch算法对两条DNA序列进行全局比对。aATTCCAAG，bTTCGAGT，得分系统是（4，3，4）,求解这个问题分3步。,（1）给动态规划矩阵赋初值,（2）按照最优分的递归算法填充动态规划矩阵,（3）从最后一个单元格开始，回溯最优化比对路径,56,（1）给动态规划矩阵赋初值,012345678,01234567,57,（2）按照最优分的递归算法填充动态规划矩阵,得分系统是（4，3，4）,58,59,（3）从最后一个单元格开始，回溯最优化比对路径,60,61,作业,找出例题中其它的最佳比对结果（总共4个比对，还有2个）,用动态规划法找出两序列的所有最佳比对，要求写出详细过程。打分矩阵采用（4，3，4，即匹配得4分，不匹配得3分，空位得4分。序列1：AAAG，序列2：ACG,62,总结,动态规划算法是一种高效的给出最优比对的算法。它的基本思想就是将待解决问题分成若干个子问题，先求解子问题，并存储子问题的解而避免重复计算，然后从这些子问题的解得到原问题的解。动态规划算法能保证在给定得分系统下产生最优的比对结果（optimalalignment）。但是这种方法对参数非常敏感，记分系统参数的选择在很大程度上决定着比对的结果。最优比对结果往往不止一个，次优结果也有可能更具有生物学意义，最优只是数学上的概念，而且是跟记分系统参数相关的。,63,Smith-Waterman算法,局部比对的应用范围比全局比对更广。S-W算法与N-W算法的区别在于多了一个去头去尾的操作。去头，在动态规划矩阵的每个单元格的计算增加一条路径。也就是如果当前比对分数小于0，那么之前的比对全部去掉，比对从目前位置重新开始。去尾，回溯的时候不是从最后开始，而是从最大的分数开始，直到遇到0。,64,