《序列比对》PPT课件.ppt

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

1、第五章 序列比对,2023/7/14,BIOINFORMATICS,1,本章提要：介绍了序列相似性的概念，列举了描述DNA和蛋白质序列相似性的计分矩阵。介绍了序列比较的基本操作“比对”的概念，以双序列比对为例详细学习了序列整体比对的Needleman-Wunsch算法，序列局部比对的Smith-Waterman算法。介绍了多序列比对的概念，简要介绍了几种多序列比对的算法，学习了一个常用的多序列比对软件ClustalW的使用和用途。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,2,序列比较是生物信息学中最基本、最重要的操作，通过序列比较可以发现生物序列中的功能、结构和进

2、化的信息。序列比较的根本任务是：通过比较生物分子序列，发现它们的相似性，找出序列之间共同的区域，同时辨别序列之间的差异。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,3,在分子生物学中，DNA或蛋白质的相似性是多方面的，可能是核酸或氨基酸序列的相似，可能是结构的相似，也可能是功能的相似。研究序列相似性的目的之一是，通过相似的序列得到相似的结构或相似的功能。通过比较未知序列与已知序列（尤其是功能和结构已知的序列）之间的相似性，可以很容易地预测未知序列的功能。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,4,这种方法在大多数情况下是成功的，当然，

3、也存在着这样的情况，即两条序列几乎没有相似之处，但分子却折叠成相同的空间形状，并具有相同的功能。这里先不考虑空间结构或功能的相似性，仅研究序列的相似性。研究序列相似性的另一个目的是通过序列的相似性，判别序列之间的同源性，推测序列之间的进化关系。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,5,序列比较可以分为4种情况：(1)、假设有两条长度相近的、来自同一个字母表的序列，它们之间非常相似，仅仅有一些细微的差别，例如字符的插入、字符的删除和字符替换，要求找出这两条序列的差别。这种操作实际应用比较多，例如，有两个实验室同时测定某个基因的DNA序列，其结果可能不一样，需要通

4、过序列比较来比较实验结果。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,6,(2)、假设有两条序列，要求判断是否有一条序列的前缀与另一条序列的后缀相似，如果是，则分别取出前缀和后缀。该操作常用于大规模DNA测序中序列片段的组装。(3)、假设有两条序列，要求判断其中的一条序列是否是另一条序列的子序列。这种操作常用于搜索特定的序列模式。(4)、假设有两条序列，要求判断这两条序列中是否有非常相似的子序列。这种操作可用于分析保守序列。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,7,当然，进行序列比较时，往往还需要说明是采取全局比较，还是采取局部比较

5、。全局比较是比较两条完整的序列，而局部比较是找出最大相似的子序列。本章着重介绍通用的序列比较方法。了解序列比较的原理对于正确、合理、灵活地使用相关生物信息学资源和软件有重要的指导意义。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,8,5.1序列的相似性,5.1.1 几个基本概念,序列的相似性可以是定量的数值，也可以是定性的描述。相似度是一个数值，反映两条序列的相似程度。关于两条序列之间的关系，有许多名词，如相同、相似、同源、同功、直系同源、并系同源等。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,9,在很多时候，往往通过一个简单序列相似性的比

6、较就可以对未知序列进行初步的功能预测，为后续实验确定初步的研究方向。本节将主要讲述如何采用生物信息学技术对核酸序列进行较为全面的分析。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,10,在进行序列比较时经常使用“同源”(homology)和“相似”(similarity)这两个概念，这是两个经常容易被混淆的不同概念。两条序列同源是指它们具有共同的祖先。在这个意义上，无所谓同源的程度，两条序列要么同源，要么不同源。而相似则是有程度的差别，如两条序列的相似程度达到30或60。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,11,一般来说，相似性很高

7、的两条序列往往具有同源关系；但也有例外，即两条序列的相似性很高，但它们可能并不是同源序列，这两条序列的相似性可能是由随机因素所产生的，这在进化上称为“趋同”（convergence)，这样一对序列可称为同功序列。直系同源(orthologous)序列是来自于不同种属的同源序列，而并系同源(paralogous)序列则是来自于同一种属的序列，它是由进化过程中的序列复制而产生的。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,12,5.1.2 点标方法分析两序列间的相似性,点标（dot plot）是两序列对位排列中最基本也是最直观的方法。设序列A和B的长度不同，但很接近。我

8、们可以用二维坐标来标定每个位点上的对位情况。如图5-1所示，序列A为X轴，序列B为Y轴。如AiBj,，坐标(i,j)处赋值为“*”，其余赋值为“空白”。逐个比较所有的字符对，最终形成点阵列。,图5-1 序列比对的点阵图方式,2023/7/14,BIOINFORMATICS,数理与生物工程学院,14,显然，如果两条序列完全相同，则在点矩阵主对角线的位置都有标记；如果两条序列存在相同的子串，则对于每一个相同的子串对，有一条与对角线平行的由标记点所组成的斜线，如图5.2中的斜线代表相同的子串“ATCC；而对于两条互为反向的序列，则在反对角线方向上有标记点组成的斜线，如图5.3所示。,图5-2 相同子

9、串点阵图,图5-3 反向序列点阵图,图5-4 多个相同连续子串序列的点阵图,2023/7/14,BIOINFORMATICS,数理与生物工程学院,18,除非已经知道待比较的序列非常相似，一般先用点矩阵方法比较，因为这种方法可以通过观察阵列的对角线迅速发现可能的序列比对。两条序列中有很多匹配的字符对，因而在点矩阵中会形成很多点标记。当对比较长的序列进行比较时，这样的点阵图很快会变得非常复杂和模糊。使用滑动窗口代替一次一个位点的比较是解决这个问题的有效方法。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,19,假设窗口大小为10，相似度阈值为8。首先，将X轴序列的第110个

10、字符与Y轴序列的第110个字符进行比较。如果在第一次比较中，这10个字符中有8个或者8个以上相同，那么就在点阵空间(1，1)的位置画上点标记。然后窗口沿X轴向右移动一个字符的位置，比较X轴序列的第2 11个字符与Y轴序列的第110个字符。不断重复这个过程，直到X轴上所有长度为10的子串都与Y轴第110个字符组成的子串比较过为止。然后，将Y轴的窗口向上移动一个字符的位置，重复以上过程，直到两条序列中所有长度为10的子串都被两两比较过为止。基于滑动窗口的点矩阵方法可以明显地降低点阵图的噪声，并且可以明确地指出两条序列间具有显著相似性的区域。,2023/7/14,BIOINFORMATICS,数理与

11、生物工程学院,20,以上讨论了如何利用单元矩阵来构建点阵图。更加复杂的点阵图可基于不同的计分规则而构建。这些计分规则规定了不同残基之间相似性程度的分值。例如，可以根据不同残基之间在进化关系、空间结构、理化性质等方面的相似性来规定它们之间的相似性分数值。在这种情况下，由于点阵图不只是简单的稀疏矩阵，那些非主对角线点的信号和噪声同时得到放大，所以噪声过滤就变得十分重要。常用的方法是引入滑动窗口作为平滑函数提高点阵图的信噪比。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,21,5.1.3 描述相似性的记分矩阵,如果序列比较仅仅取决于序列间严格一致的区域，那么我们可以将其转化

12、为一种极为简单的程序。然而，大多数序列对位排列不是仅仅限制在子序列的范围内，而是涉及全长序列的比较。有时，也不能简单理解为如何减少间隔的数目，而要同时考虑对位排列后序列的生物学意义。例如，某些氨基酸有时应放在非严格一致的位置。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,22,记分矩阵方法(scoring matrix)被广泛应用于评价序列对位排列的质量。通常使用得分()、无分(0)或罚分(-)来进行综合评价。考虑未匹配和间隔的罚分以及权重不均衡等因素，记分矩阵就更加复杂。人们已提出各种各样的记分矩阵来进行不同目的序列对位排列。,2023/7/14,BIOINFORM

13、ATICS,数理与生物工程学院,23,不同类型的字符替换，其代价或得分是不一样的，特别是对于蛋白质序列。某些氨基酸可以很容易地相互取代而不用改变它们的理化性质。例如，考虑这样两条蛋白质序列，其中一条在某一位置上是丙氨酸，如果该位点被替换成另一个较小且疏水的氨基酸，比如缬氨酸，那么对蛋白质功能的影响可能较小；如果被替换成较大且带电的残基，比如赖氨酸，那么对蛋白质功能的影响可能就要比前者大。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,24,直观地讲，比较保守的替换比起较随机替换更可能维持蛋白质的功能，且更不容易被淘汰。因此，在为比对打分时，我们可能更倾向对丙氨酸与缬氨酸

14、的比对位点给予一定的奖励，而对于丙氨酸与那些大而带电氨基酸（比如赖氨酸）的比对位点则相反。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,25,理化性质相近的氨基酸残基之间替换的代价显然应该比理化性质相差甚远的氨基酸残基替换得分高，或者代价小。同样，保守的氨基酸替换得分应该高于非保守的氨基酸替换。这样的打分方法在比对非常相近的序列以及差异极大的序列时，会得出不同的分值。这就是提出得分矩阵(或者称为取代矩阵）的原由。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,26,在得分矩阵中，详细地列出各种字符替换的得分，从而使得计算序列之间的相似度更为合理

15、。在比较蛋白质时，我们可以用得分矩阵来增强序列比对的敏感性。得分矩阵是序列比较的基础，选择不同的得分矩阵将得到不同的比较结果，而了解得分矩阵的理论依据将有助于在实际应用中选择合适的得分矩阵。以下介绍一些常用的得分矩阵或代价矩阵。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,27,5.1.3.1 核酸得分矩阵,设核酸序列所用的字母表为A=A,C,G,T。(1)等价矩阵 等价矩阵(见表5-1)是最简单的一种得分矩阵，其中，相同核苷酸匹配的得分为“1”，而不同核苷酸的替换得分为“0”（没有得分）。,2023/7/14,BIOINFORMATICS,28,表5-1 等价矩阵,

16、2023/7/14,BIOINFORMATICS,29,(2)BLAST矩阵 BLAST是目前最流行的核酸序列比较程序，表5-2是其得分矩阵。这也是一个非常简单的矩阵，如果被比较的两个核苷酸相同，则得分为“5”，反之得分为“-4”。,表5-2 BLAST矩阵,2023/7/14,BIOINFORMATICS,数理与生物工程学院,30,（3）转换颠换矩阵 核酸的碱基按照环结构分为两类，一类是嘌呤（腺嘌呤A，鸟嘌呤G），它们有两个环；另一类是嘧啶（胞嘧啶C，胸腺嘧啶T），它们的碱基只有一个环。如果DNA碱基的变化（碱基替换）保持环数不变，则称为转换(transition)，如AG,CT；如果环数发

17、生变化，则称为颠换(transversion)，如AC,AT等。在进化过程中，转换发生的频率远比颠换高，而表5-3所示的矩阵正好反映了这种情况，其中转换的得分为“-1”，而颠换的得分为“-5”。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,31,表5-3 转移矩阵,2023/7/14,BIOINFORMATICS,32,蛋白质得分矩阵,表5-4给出了20种氨基酸的英文缩写：,表5-4 20种氨基酸的英文缩写,2023/7/14,BIOINFORMATICS,数理与生物工程学院,33,（1)等价矩阵,其中，Rij代表得分矩阵元素，i、j分别代表字母表第i个和第j个字符。

18、,2023/7/14,BIOINFORMATICS,数理与生物工程学院,34,(2)遗传密码矩阵GCM GCM矩阵通过计算一个氨基酸残基转变到另一个氨基酸残基所需的密码子变化数目而得到，矩阵元素的值对应于代价。如果变化一个碱基，就可以使一个氨基酸的密码子改变为另一个氨基酸的密码子，则这两个氨基酸的替换代价为1；,2023/7/14,BIOINFORMATICS,数理与生物工程学院,35,如果需要两个碱基的改变，则替换代价为2；以此类推（见表5-5)。注意Met到Tyr的转变是仅有的密码子三个位置都发生变化的转换。在表5-5中，Glx代表Gly、Gln或Glu，而Asx则代表Asn或Asp，X代

19、表任意氨基酸。GCM矩阵常用于进化距离的计算，其优点是计算结果可以直接用于绘制进化树，但是它在蛋白质序列比对尤其是相似程度很低的序列比对中很少被使用。,表5-5 遗传密码矩阵GCM,2023/7/14,BIOINFORMATICS,数理与生物工程学院,37,(3)疏水矩阵 该矩阵（见表5-6）是根据氨基酸残基替换前后疏水性的变化而得到得分矩阵。若一次氨基酸替换疏水特性不发生太大的变化，则这种替换得分高，否则替换得分低。,表5-6 蛋白质疏水矩阵,2023/7/14,BIOINFORMATICS,数理与生物工程学院,39,(4)PAM矩阵 为了得到得分矩阵，更常用的方法是统计自然界中各种氨基酸残

20、基的相互替换率。如果两种特定的氨基酸之间替换发生得比较频繁，那么这一对氨基酸在得分矩阵中的互换得分就比较高。PAM矩阵就是这样一种得分矩阵。PAM矩阵是第一个广泛使用的最优矩阵，它是基于进化原理的，建立在进化的点接受突变模型PAM(point accepted mutation)基础上，通过统计相似序列比对中的各种氨基酸替换发生率而得到该矩阵。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,40,Dayhoff和她的同事们研究了71个相关蛋白质家族的1572个突变，发现蛋白质家族中氨基酸的替换并不是随机的。由此断言一些氨基酸的替换比其他替换更容易发生，其主要原因是这些替

21、换不会对蛋白质的结构和功能产生太大的影响。如果氨基酸的替换是随机的，那么，每一种可能的取代频率仅仅取决于不同氨基酸出现的背景频率。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,41,然而，在相关蛋白质中，存在取代频率大大地倾向于那些不影响蛋白质功能的取代。换句话说，这些点突变已经被进化所接受。这意味着，在进化历程上，相关的蛋白质在某些位置上可以出现不同的氨基酸。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,42,一个PAM就是一个进化的变异单位，即1的氨基酸改变。但是，这并不意味着经过100次PAM后，每个氨基酸都发生变化，因为其中一些位置可

22、能会经过多次改变，甚至可能变回到原先的氨基酸。因此，另外一些氨基酸可能不发生改变。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,43,PAM有一系列的替换矩阵，每个矩阵用于比较具有特定进化距离的两条序列。例如，PAM-120矩阵用于比较相距120个PAM单位的序列。一个PAM-N矩阵元素（,j)的值反映两条相距N个PAM单位的序列中第i种氨基酸替换第j种氨基酸的概率。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,44,从理论上讲，PAM-0是一个单位矩阵，主对角线上的元素值为1，其他矩阵元素的值为0。其他PAM-N矩阵可以通过统计计算而得到。

23、首先针对那些确信是相距一个PAM单位的序列进行统计分析，得到PAM-1矩阵。PAM-1矩阵对角线上的元素值接近于1，而其他矩阵元素值接近于0。例如，可以按下述方法构建PAM-1矩阵。首先，构建一个序列间相似度很高（通常大于85）的比对。接着，计算每个氨基酸j的相对突变率mj。相对突变率就是某种氨基酸被其他任意氨基酸替换的次数。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,45,比如，丙氨酸的相对突变率是通过计算丙氨酸与非丙氨酸残基比对的次数来得到。然后，针对每个氨基酸对i和j，计算氨基酸j被氨基酸i替换的次数。最后，将以上替换次数除以对应的相对替换率，利用每个氨基酸出

24、现的频度对其进行标准化，并将以上计算结果取常用对数，于是得到了PAM-1矩阵中的元素PAM-1(i,j)。这种矩阵被称作对数几率矩阵（log odds matrix），因为其中的元素是根据每个氨基酸替换率的对数值来得到的。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,46,将PAM-1自乘N次，可以得到矩阵PAM-N。虽然Dayhoff等人只发表了PAM-250，但潜在的突变数据可以外推至其他PAM值，产生一组矩阵。可以根据待比较序列的长度以及序列间的先验相似程度来选用特定的PAM矩阵，以发现最适合的序列比对。一般，在比较差异极大的序列时，通常在较高的PAM值处得到最

25、佳结果，比如在PAM-200到PAM-250之间，而较低值的PAM矩阵一般用于高度相似的序列。实践中用得最多的且比较折中的矩阵是PAM-250。,表5-7 Dayhoff PAM 250记分矩阵,2023/7/14,BIOINFORMATICS,数理与生物工程学院,48,(5)BLOSUM矩阵 不少情况下Dayhoff PAM记分矩阵可能失效，因为其置换速率是通过至少具有85一致性的序列对位排列所获得的。那些进化距离较远的矩阵是推算出来而不是直接计算得到的，其准确率受到一定限制，这就需要使用新的记分矩阵。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,49,BLOSUM

26、矩阵是由Henikoff首先提出的另一种氨基酸替换矩阵，它也是通过统计相似蛋白质序列的替换率而得到的。PAM矩阵是从蛋白质序列的全局比对结果推导出来的，而BLOSUM矩阵则是从蛋白质序列块（短序列）比对而推导出来的。但在评估氨基酸替换频率时，应用了不同的策略。基本数据来源于BLOCKS数据库，其中包括了局部多重比对（包含较远的相关序列，与在PAM中使用较近的相关序列相反）。虽然在这种情况下没有用进化模型，但它的优点在于可以通过直接观察而不是通过外推获得数据。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,50,同PAM模型一样，也有一系列的BLOSUM矩阵，可以根据亲缘

27、关系的不同来选择不同的BLOSUM矩阵进行序列比较。然而BLOSUM矩阵阶数的意义与PAM矩阵正好相反。低阶PAM矩阵适合用来比较亲缘较近的序列，而低阶BLOSUM矩阵更多是用来比较亲缘较远的序列。一般来说，BLOSUM-62矩阵适于用来比较大约具有62相似度的序列，而BLOSUM-80矩阵更适合于相似度为80左右的序列。,表5-8 BLOSUM-62矩阵,2023/7/14,BIOINFORMATICS,数理与生物工程学院,52,相似性记分矩阵的构建，是基于远距离进化过程中观察到的残基替换率，并用不同的记分值表征不同残基之间的相似度。,2023/7/14,BIOINFORMATICS,数理与

28、生物工程学院,53,5.1.3.3 不同记分方法比较,在实际工作中，不同对位排列的优劣可以用总分(即对核苷酸或氨基酸序列进行对位排列所获得的分数之和)来综合反映。不同的记分方法(模型)的特点可简单归纳如下。1.基于“一致性”的记分 在这种记分方法中，仅统计序列位点间的一致性。匹配的位点记正分(通常为1)，非匹配的位点记0分。优点：简单明了，适用于高度相似性序列。缺点：没有考虑非匹配位点间的不等价问题；在对相似性较低的序列进行对位排列时，效果尤差。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,54,2.基于“化学相似性”的记分方式 该方法是对一致性记分方法的局部改进。例

29、如，Mclachlan和Feng 等结合氨基酸的性质(如极性、电荷、大小和结构特征)，对不同氨基酸进行了加权。优点：考虑了氨基酸和蛋白质的结构与性质。例如，一个氨基酸从极性到非极性的改变对蛋白质的结构与功能的影响，可能比具有相似性质的氨基酸间的突变要显著一些。缺点：并非所有蛋白质的结构与功能的改变都可以用简单的记分描述。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,55,3.基于“遗传密码”的记分 该方法考虑到当一个氨基酸转换成另一个氨基酸时，在基因组水平上碱基变化的最小数目。优点：具有分子生物学基础。缺点：考虑随机因素较少。例如，碱基变化数目并非总是与氨基酸序列间的

30、相似性相对应。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,56,4.基于“观察突变”的记分 该方法考虑了对位排列序列中所实际观察到的突变频率。Dayhoff矩阵和BLOSUM矩阵就属于这类方法。优点：以自然界中真实事件为基础。与其他记分方法相比，真实的突变频率更有助于解释序列间的进化关系。缺点：突变频率是从已对位排列的序列中获得的，而初始的对位排列必须人工进行，较为复杂且容易发生错误。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,57,5.2 双序列对位排列,序列对位排列的基本概念,在序列检索和分析中，经常涉及到两条序列对位排列(seque

31、nce alignment)的问题，即通过字符匹配和替换，或者插入间隔(gap)和删除字符的方法使不同长度的序列对齐，达到长度一致。优化的对位排列应使间隔的数目最小，同时序列间相似性区域最大。序列的比对是一种关于序列相似性的定性描述，它反映在什么部位两条序列相似，在什么部位两条序列存在差别。最优比对揭示两条序列的最大相似程度，指出序列之间的根本差异。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,58,例如，对序列XCGATCAG(长度为7)和序列YCGTCAG(长度为6)，只需插入一个间隔即可。对位排列后的两个序列为：X：CGATCAG Y：CG TCAG 下面就不同

32、类型的编辑操作定义函数w，它表示“代价(cost)”或“权重(weight)”。对字母表A中的任意字符a、b，定义：,(5-1),2023/7/14,BIOINFORMATICS,数理与生物工程学院,59,这是一种简单的代价定义，在实际应用中还需使用更复杂的代价模型。一方面，可以改变各编辑操作的代价值，例如，在蛋白质序列比较时，用理化性质相近的氨基酸进行替换的代价应该比完全不同的氨基酸替换代价小；另一方面，也可以使用得分（score）函数来评价编辑操作。下面给出一种基本的得分函数：,(5-2),2023/7/14,BIOINFORMATICS,数理与生物工程学院,60,在进行序列比对时，可根据

33、实际情况选用代价函数或得分函数，即选用式（5-1)或式（5-2）。下面给出在进行序列比对时常用的概念。(1)、两条序列s和t的比对的得分（或代价）等于将s转化为t所用的所有编辑操作的得分（或代价）总和；(2)、s和t的最优比对是所有可能的比对中得分最高（或代价最小）的一个比对；,2023/7/14,BIOINFORMATICS,数理与生物工程学院,61,(3）、s和t的真实距离应该是在得分函数p值（或代价函数w值）最优时的距离。使用前面代价函数w的定义，可以得到下列比对的代价。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,62,而使用得分函数p的定义，可以得到下列比对

34、的得分。,进行序列比对的目的是寻找一个得分最高（或代价最小）的比对。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,63,序列对位排列中，有时要用到子序列(sub-sequence)的概念。例如，序列A含200个碱基，序列B含500个碱基。如果整个序列A与序列B的一部分完全一致，则称A为B的子序列。图5-5(a)示出了对A和B进行对位排列的简单方法。如果A有两个区域分别与B一致，则需要将A分为两部分图5-5(b)，两端和中间分别插入间隔即可。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,64,图5-5 子序列与比对排列,显然，随着所比较的序列数

35、目和长度的增加，序列比对排列的工作将变得愈来愈困难。因而，有关的数学方法和计算机程序已成为比对排列所不可缺少的手段。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,65,5.2.2 局部相似性和整体相似性,从上面的介绍中可以看出，序列比对基于某个数学模型，模型的参数可以加以调节。不同模型所反映的生物学性质不同。例如，可以根据分子结构、功能和进化等方面的相关性来进行构建。必须指出，比对结果没有正确和错误之分，其区别是由于模型所反映的生物学性质不同。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,66,总体来说，比对模型可以分为两类：一类是考察两个序

36、列之间的整体相似性，称全局性比对；另一类则着眼于序列中的某些特殊片段，比较这些片段之间的相似性，即局部性比对。搞清这两类相似性和这两种不同比对方法之间的区别，对于正确选择使用哪种比对方法十分重要。应该指出，在实际应用中，用整体比对方法企图找出只有局部相似性的两个序列之间的关系，显然是徒劳的；而用局部比对得到的局部相似性结果不能说明这两个序列的三维结构或折叠方式是否相同。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,67,目前常用的BLAST和FastA等数据库搜索程序均采用局部相似性比对方法，具有较快的运行速度，采用某些优化算法可进一步提高速度。局部相似性搜索主要用于

37、找出序列中的功能位点，如酶的催化位点等。它们通常只有一个或几个残基，具有较高的保守性，并且不受序列中其他部分的插入和突变的影响。从这个意义上说，局部相似性搜索比整体相似性比对更加灵敏，也更具有生物学意义。需要特别指出，那些具有一定相似性的序列片段不一定具有相同的三维结构。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,68,5.2.3 整体比对算法,在对上述基本概念有所了解后，我们开始讨论整体比对的Needleman和Wunsch算法。从本质上讲，这一算法和已经广为使用的点阵图方法类似。整体比对方法中，两条蛋白质序列具有最多匹配残基定义为最佳匹配，其中允许进行必要的插入

38、或缺失。为控制无限制的空位插入，我们引入罚分(penalty)概念。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,69,与点阵图类似，整体比对基于一个二维矩阵，并通过某种算法找出最佳匹配路径。矩阵的最基本形式是：将两序列中匹配残基所对应单元的值置为1，不匹配的值置为0。然后对矩阵中每个单元进行连续求和，即把能够到达该位置的所有单元中最大值与该位置的值相加。若令当前位置为第i行、第j列，那么能够达到它的单元为(I)第i+1行中的第j个单元之后的所有单元(ii)第j+1列中的第i个单元之后的所有单元。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,

39、70,对矩阵的所有单元都重复这一操作，直到全部结束为止。这样，可以构建一条最大匹配路径，它由N末端具有最大值的单元格开始，按照取最大值的原则一直到C末端，即从序列的起始开始到最后一个残基为止。不在主对角线上的单元格表示需要在此插入空位。在允许空位插入的情况下，可以借此来寻求最大比对。假如不允许空位插入，则只能找一条分值较低的路径。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,71,例5-1 对两个核酸序列ACACACTA和AGCACACA进行全局比对;将两序列中匹配残基所对应单元的值置为1，不匹配的值置为0。,2023/7/14,BIOINFORMATICS,数理与生

40、物工程学院,72,对矩阵中每个单元进行连续求和，即把能够到达该位置的所有单元中最大值与该位置的值相加。对矩阵的所有单元都重复这一操作，直到全部结束为止。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,73,完成所有矩阵单元的分值计算后，接下来就是从最高分值单元开始找出最大分值路径，也就是找出最佳匹配。根据上述求和过程的特性，最大分值单元一定是在序列的N一端，也就是矩阵左上角。从这一起始单元回溯，找出具有最大分值的路径，即最佳路径。所谓回溯，就是由算法结束时的单元开始，反向查找到达到该单元所经过的路径。最终比对结果如图,2023/7/14,BIOINFORMATICS,数

41、理与生物工程学院,74,矩阵起始单元的最大匹配值7，实际上就是最佳匹配路径中相同匹配残基的数目。,例5-2 对两条短序列“ADLGAVFALCDRYFQ”和“ADLGRTQNCDRYYQ”进行全局比对。根据算法，首先构建一个二维矩阵，用来表示两个序列的匹配状况。第一个序列沿水平方向，即x轴；第二个序列沿垂直方向，即y轴。,对矩阵中每个单元进行连续求和，即把能够到达该位置的所有单元中最大值与该位置的值相加。对矩阵的所有单元都重复这一操作，直到全部结束为止。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,77,完成所有矩阵单元的分值计算后，接下来就是从最高分值单元开始找出最

42、大分值路径，也就是找出最佳匹配。根据上述求和过程的特性，最大分值单元一定是在序列的N一端，也就是矩阵左上角。从这一起始单元回溯，找出具有最大分值的路径，即最佳路径。所谓回溯，就是由算法结束时的单元开始，反向查找到达到该单元所经过的路径。本例中，最佳路径中间有一个间隔，可以通过在y轴方向序列中残基N和C之间插入一个空位实现。最终比对结果如下图所示。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,78,可见，对用1和0表示匹配和非匹配的初始分数矩阵，上述连续求和得到的最大单元分值，即本例中矩阵起始单元的最大匹配值9，实际上就是最佳匹配路径中相同匹配残基的数目。,2023/7

43、/14,BIOINFORMATICS,数理与生物工程学院,79,Needleman和Wunsch算法考虑了两个序列中所有残基的贡献。其最佳路径的回溯一定从N-端开始，而每个单元的分值计算则是从C端开始。因此，这种方法称整体性序列比对，其结果反映了两个序列中所有残基的整体相似性。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,80,5.2.4 局部比对算法,Needleman-Wunsch算法适用于整体水平上相似性程度较高的两个序列。如果两个序列的亲缘关系较远，它们在整体上可能不具有相似性，但在一些较小的区域上却可能存在局部相似性。1981年，Smith和Waterman

44、提出了一种用来寻找并比较这些具有局部相似性区域的方法，即常用的Smith-Waterman算法。与Needleman-Wunsch算法类似，它也是一种基于矩阵的方法，而且也同样是运用回溯法(backtracking)建立允许空位插入的比对。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,81,多年来，Smith-Waterman算法一直是序列局部比对算法的基础，许多其他算法都是基于这一算法开发和改进的。它也经常作为比较不同比对方法的标准。Smith-Waterman算法在识别局部相似性时，确实具有很高的灵敏度，但使用时要注意，它只是寻找序列中一些小的、具有局部相似性的片

45、段，而不是序列的整体相似性。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,82,Smith-Waterman算法一个重要特性是矩阵中每个单元均可以是比对结果序列片段的终点，该片段的相似性程度由该单元中的分数值表示。下面以例5-3为例将该算法的具体过程描述如下：,2023/7/14,BIOINFORMATICS,数理与生物工程学院,83,例5-3 对例5-2的两个序列进行局部比对。首先，矩阵最上面一行和最左边一列前面插入一个边界行和边界列，图中用字符“X”表示，称为第0行和第0列。该边界行和边界列所有单元的分值均为0.0。可以把这些单元理解为序列片段的起始端，其长度为0

46、。它们的相似性分数值自然也为0。至于用小数还是整数表示，没有实质性区别。,2023/7/14,BIOINFORMATICS,84,2023/7/14,BIOINFORMATICS,数理与生物工程学院,85,接下来计算矩阵中每个单元的计分值。与Needleman-Wunsch算法不同，Smith-Waterman算法在计算矩阵单元分值时，从左往右、从上到下，并沿对角线从左上角到右下角，而不是从下到上、从右到左。当前单元对角线方向前一格的分值与当前单元相似性数值之和，相似性数值匹配时为1.0，不匹配时为-0.333。,2023/7/14,BIOINFORMATICS,86,2023/7/14,BI

47、OINFORMATICS,数理与生物工程学院,87,接下来进行递推，用两个函数分别计算由二条路径到达该单元的分值并找出其中的最大值，若此分值小于0，则用0替代。这两个函数分别计算：(I)当前行前面各分值与相应空位罚分值之差，并取最大值；所用求空位罚分值的函数为W1.0+0.333 k，k表示连续的第k个空位。(II)当前列前面各分值与相应的空位罚分值之差，并取最大值。如果出现负值就用0代替，表示没有相似性比对可以延续到当前位置。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,89,一旦矩阵中所有单元的分值计算完毕，就可以找出具有最高分值的单元，也就是代表两个序列间高分匹

48、配的终点。到达这个单元的其他矩阵元素可以通过回溯方法确定。然后根据回溯路径求得一个片段的比对。如果需要，还可以找出在上述回溯范围以外其他具有较高分值的矩阵单元，再进行回溯，即找出多个具有较高分值的相似性片段。本例中发现有两个区域ADLG和CDRY具有局部相似性。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,90,5.2.5 序列比对的主要用途,1.用于系统发育分析(phylogenetic analysis)通过序列比对，可以寻找序列间的同源性(相似性)，这种同源相似性是序列间进化关系的一种反映，所构建的数据矩阵成为系统发育分析的基础。2.结构预测(structure

49、 prediction)将新序列与已知结构的蛋白质序列进行比对，可以通过序列同源性来粗略地推测其结构的相似性。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,91,3.序列基序鉴定(sequence motif identification)局部排列可以鉴定蛋白质和核苷酸序列中潜在的序列和功能基序。4.功能预测（function prediction)蛋白质序列间的高度相似性通常意味着同源序列间的功能相似性。5.数据库搜索(database search),2023/7/14,BIOINFORMATICS,数理与生物工程学院,92,这是序列比对很重要的一个应用。上章介绍

50、的BLAST(basic local alignment search tool)就是一个例子。值得一提的是，手工比对因费时费力，已基本上被计算机软件所取代。然而，某些软件自动排列结果可能会出现一些偏差，特别是某些序列涉及复杂的生物学背景，在这种情况下，手工校正不失为一种重要的补充途径。如果使用了手工排列，一般应在文章或报告中加以说明。,2023/7/14,BIOINFORMATICS,数理与生物工程学院,93,5.3 序列多重比对,5.3.1 多序列比对的意义,与序列两两比对不一样，序列多重比对的目标是发现多条序列的共性。如果说序列两两比对主要用于建立两条序列的同源关系和推测它们的结构、功能