第四章双序列比对 41引言 本章介绍序列比对时常用的几个概念,包括同一性( identity)、相似性( similarity)同 源性( homology)等。这些概念,在蛋白质和核酸序列比对时经常使用。双序列比对( pairwise alignement)是指通过一定的算法对两个DNA或蛋白质序列进行比对分析,从而找出两者 之间最大相似性匹配。双序列比对是序列分析常用方法之一,是多序列比对和数据库搜索的 基础。双序列比对基于一定的算法,而这些算法是基于序列本身的属性而不是关于该序列的 注释信息。双序列比对基本上可以分为两类,一类是基于序列的局部相似性,而另一类则基 于序列的全局相似性。两者之间无论是生物学基础,还是所用的算法,都有很大区别。 42数据库检索和数据库搜索 数据库检索( database query)和数据库搜索( database search)是分子生物信息学中两 个不同的概念,有时常被混淆,有必要把这两个术语作简单说明。所谓数据库检索,是指对 序列、结构以及各种二次数据库中的注释信息进行关键词匹配查找。例如,对核酸或蛋白质 数据库输入关键词“ human adrenergic recptors”(人的肾上腺素受体),即可找出数据库中所 有和人的肾上腺素受体有关的序列条目。数据库查询有时也称数据库检索,它和因特网上通 过搜索引擎查找需要的信息是一个概念。而数据库搜索是指通过特定的序列相似性比对算 法,找出核酸或蛋白质序列数据库中与代查序列( query sequence)具有一定程度相似性的 序列。例如,给定人的肾上腺素受体序列,通过数据库搜索,在核酸或蛋白质序列数据库中 找出与该代查査序列具有一定相似性的序列。显然,数据库检索和数据库搜索是在生物信息学 中是两个完全不同的概念,它们所要解决的问题、所采用的方法和得到的结果均不相同 基于文字注释信息的数据库检索是核酸和蛋白质序列分析的一个重要组成部分,这 点不应予以忽略。然而,在生物信息学应用研究中,我们经常面临的问题是已经测得一个核 酸序列片段,或一个由核酸序列翻译得到的蛋白质序列片段,而尚无注释信息。此时,数据 库搜索就成了确定对该序列进一步分析研究的有效方法。本章将重点介绍序列比对的基本概 念和常用算法,特别是对代查序列和目标( subject)序列之间的相似性关系,做一些定量的 分析。 为了识别一个新测定的序列和一个已知基因家族之间的进化关系,确定它们是否具有 同源性,通常需要通过序列比对,找出它们之间核苷酸碱基或氨基残基的最大匹配,从而定 量给出其相似性程度。如果两者的相似性程度很低,则很难确定它们是否具有同源性,除非 使用亲源性分析( Phylogeny Analysis)等其它分析方法,或有实验结果加以证实。通过对基 因或蛋白质之间家族关系的分析,可以从浩繁的基因组信息中找出一些线索,从而对该基因
第四章 双序列比对 4.1 引言 本章介绍序列比对时常用的几个概念，包括同一性（identity）、相似性（similarity）同 源性（homology）等。这些概念，在蛋白质和核酸序列比对时经常使用。双序列比对（pairwise alignement）是指通过一定的算法对两个 DNA 或蛋白质序列进行比对分析，从而找出两者 之间最大相似性匹配。双序列比对是序列分析常用方法之一，是多序列比对和数据库搜索的 基础。双序列比对基于一定的算法，而这些算法是基于序列本身的属性而不是关于该序列的 注释信息。双序列比对基本上可以分为两类，一类是基于序列的局部相似性，而另一类则基 于序列的全局相似性。两者之间无论是生物学基础，还是所用的算法，都有很大区别。 4.2 数据库检索和数据库搜索 数据库检索（database query）和数据库搜索（database search）是分子生物信息学中两 个不同的概念，有时常被混淆，有必要把这两个术语作简单说明。所谓数据库检索，是指对 序列、结构以及各种二次数据库中的注释信息进行关键词匹配查找。例如，对核酸或蛋白质 数据库输入关键词“human adrenergic recptors”（人的肾上腺素受体），即可找出数据库中所 有和人的肾上腺素受体有关的序列条目。数据库查询有时也称数据库检索，它和因特网上通 过搜索引擎查找需要的信息是一个概念。而数据库搜索是指通过特定的序列相似性比对算 法，找出核酸或蛋白质序列数据库中与代查序列（query sequence）具有一定程度相似性的 序列。例如，给定人的肾上腺素受体序列，通过数据库搜索，在核酸或蛋白质序列数据库中 找出与该代查序列具有一定相似性的序列。显然，数据库检索和数据库搜索是在生物信息学 中是两个完全不同的概念，它们所要解决的问题、所采用的方法和得到的结果均不相同。 基于文字注释信息的数据库检索是核酸和蛋白质序列分析的一个重要组成部分，这一 点不应予以忽略。然而，在生物信息学应用研究中，我们经常面临的问题是已经测得一个核 酸序列片段，或一个由核酸序列翻译得到的蛋白质序列片段，而尚无注释信息。此时，数据 库搜索就成了确定对该序列进一步分析研究的有效方法。本章将重点介绍序列比对的基本概 念和常用算法，特别是对代查序列和目标（subject）序列之间的相似性关系，做一些定量的 分析。 为了识别一个新测定的序列和一个已知基因家族之间的进化关系，确定它们是否具有 同源性，通常需要通过序列比对，找出它们之间核苷酸碱基或氨基残基的最大匹配，从而定 量给出其相似性程度。如果两者的相似性程度很低，则很难确定它们是否具有同源性，除非 使用亲源性分析（Phylogeny Analysis）等其它分析方法，或有实验结果加以证实。通过对基 因或蛋白质之间家族关系的分析，可以从浩繁的基因组信息中找出一些线索，从而对该基因
或蛋白质家族的完整性( completeness进行预测。例如,假定某个基因家族的10个成员在 鼠中已知,而在人中只找到7个,那么很有可能还有3个成员在人的基因组中有待发现。这 些分析结果还可用于药理学和分子生物学研究,用来解释某些受体对某种药物的特殊反应 尽管这些受体的序列在人基因组中还没有测得。它可以为分子生物学家以鼠的序列数据为模 板克隆人的该基因的受体提供可能性。 为了能够更有效地分析数据库搜索结果,有必要对序列比对的基本原理和数据库搜索 的常用算法和有一个比较详细的介绍。 43字母表和复杂度 核酸和蛋白质序列可以看成是由字母表中选出的字母组成的。一个字母表的复杂度定 义为它所包含的不同字母的数目。例如英语字母表的复杂度是26:DNA序列的字母表复杂 度是4。假定序列中含有不确定的碱基N(例如表达序列标签EST),则其复杂度为5。蛋白 质序列由20种氨基酸残基组成,其复杂度为20。若某个残基未定,则用X表示。有时用B 表示天冬酰胺或天冬氨酸,若用三字符表示,则写成Asx:用Z表示谷氨酰胺或谷氨酸,若 用三字符表示,则写成Glx。有些序列比对程序对这些特殊残基进行预处理。本章中将不涉 及这些特殊残基,只讨论由20中普通氨基酸组成的蛋白质序列 44算法和程序 在开始介绍序列比对的基本原理前,有必要分清算法和程序之间的区别。所谓算法, 是指按照一定的方式描述计算过程或处理某个问题的一系列步骤,而程序则是算法的具体实 现,也就是用某种计算机语言编写的实现某个算法的一在组指令集合。一个算法可能会有多 种实现的方法。如果算法的描述或定义明确,那么这些不同的实现方法,即不同的程序应给 出同样的结果。然而,对某个算法可能有不同的理解,在具体实现时,可能会有一定的区别。 4双序列比对简例 首先,我们用一个简单的例子说明序列比对的基本原理。图6.1所示是对两个蛋白质序 列片段进行比对的一般方法,基本思想是将两个序列上下排列,若上下对应的残基相同,则 用竖线表示。可以通过插入空位(gap)使上下两个序列具有最好的匹配,即两个序列之间 对用所对应的相同残基最多。 插入空位前 序列1(代查序列) AGGVLIIQVE
或蛋白质家族的完整性（completeness）进行预测。例如，假定某个基因家族的 10 个成员在 鼠中已知，而在人中只找到 7 个，那么很有可能还有 3 个成员在人的基因组中有待发现。这 些分析结果还可用于药理学和分子生物学研究，用来解释某些受体对某种药物的特殊反应， 尽管这些受体的序列在人基因组中还没有测得。它可以为分子生物学家以鼠的序列数据为模 板克隆人的该基因的受体提供可能性。 为了能够更有效地分析数据库搜索结果，有必要对序列比对的基本原理和数据库搜索 的常用算法和有一个比较详细的介绍。 4.3 字母表和复杂度 核酸和蛋白质序列可以看成是由字母表中选出的字母组成的。一个字母表的复杂度定 义为它所包含的不同字母的数目。例如英语字母表的复杂度是 26；DNA 序列的字母表复杂 度是 4。假定序列中含有不确定的碱基 N（例如表达序列标签 EST），则其复杂度为 5。蛋白 质序列由 20 种氨基酸残基组成，其复杂度为 20。若某个残基未定，则用 X 表示。有时用 B 表示天冬酰胺或天冬氨酸，若用三字符表示，则写成 Asx；用 Z 表示谷氨酰胺或谷氨酸，若 用三字符表示，则写成 Glx。有些序列比对程序对这些特殊残基进行预处理。本章中将不涉 及这些特殊残基，只讨论由 20 中普通氨基酸组成的蛋白质序列。 4.4 算法和程序 在开始介绍序列比对的基本原理前，有必要分清算法和程序之间的区别。所谓算法， 是指按照一定的方式描述计算过程或处理某个问题的一系列步骤，而程序则是算法的具体实 现，也就是用某种计算机语言编写的实现某个算法的一在组指令集合。一个算法可能会有多 种实现的方法。如果算法的描述或定义明确，那么这些不同的实现方法，即不同的程序应给 出同样的结果。然而，对某个算法可能有不同的理解，在具体实现时，可能会有一定的区别。 4.5 双序列比对简例 首先，我们用一个简单的例子说明序列比对的基本原理。图 6.1 所示是对两个蛋白质序 列片段进行比对的一般方法，基本思想是将两个序列上下排列，若上下对应的残基相同，则 用竖线表示。可以通过插入空位（gap）使上下两个序列具有最好的匹配，即两个序列之间 对用所对应的相同残基最多。 插入空位前 序列 1 （代查序列） AGGVLIIQVE ||||||
序列2(目标序列) GGVLIQVG 插入空位后 序列1(代查序列) GGVLIIQVE 序列2(目标序列) AGGVLI-QvG 图61利用插入空位的方法获得最佳序列匹配 图中竖线表示相同残基之间的匹配,插入空位前共有6个相同残基,插入空位后 共有9个相同残基 下一步,则可以计算相同残基个数,并用分数给出定量指标。如图61中未经比对以前 的得分为6,而比对后的得分为9。 显然,从这个例子中可以看出,匹配对准的相同残基数越多,两个序列之间相似性比 对的得分就越高。当然,这只是一个用来说明比对原理的简单例子,序列很短,只有10来 个残基,而大多数蛋白质序列的长度为200到500个残基,甚至更长。其次,这两个序列的 长度几乎相等,而在实际情况下代查序列和目标序列的长度往往差别很大。此外,这两个序 列的大部分残基相同,没有其它可选择的匹配方式 另一方面,序列比对结果也可以根据引入空位的数目和非匹配残基的数目来度量。由 此而引出距离矩阵的概念,即可以用距离矩阵的方式表示两个序列之间的相似性距离。序列 比对所用的距离矩阵可能不止一个,同一算法的不同实现所用的距离矩阵可能会有所不同 46子序列 为了进一步说明序列比对的基本原理,下面我们用一对比较接近实际的序列。假定序 列A有400个残基,序列B有650个残基。如果序列A与序列B的一部分相同,则可以认 为A是B的子序列。此时,只要在适当部位插入空位,就可以使序列A和序列B完全匹配 假定序列A中有两个片段分别与序列B中的两个片段相同。通过序列比对,可以找出 这些相同片段,并在序列A中插入空位,使序列A与序列B有最大的匹配,如图62(b) 所示。此时,可以找出序列A与序列B之间具有最好匹配的子序列。利用简单的渐进算法 可以直接实现上述比对,因为两个序列之间的相似片段比较明显。 47同一性和相似性 上述序列比对实例只是简要说明了如何找出两个序列之间完全相同的片段。实际操作
序列 2 （目标序列） AGGVLIQVG 插入空位后 序列 1 （代查序列） AGGVLIIQVE |||||| ||| 序列 2 （目标序列） AGGVLI-QVG 图 6.1 利用插入空位的方法获得最佳序列匹配 图中竖线表示相同残基之间的匹配，插入空位前共有 6 个相同残基，插入空位后 共有 9 个相同残基 下一步，则可以计算相同残基个数，并用分数给出定量指标。如图 6.1 中未经比对以前 的得分为 6，而比对后的得分为 9。 显然，从这个例子中可以看出，匹配对准的相同残基数越多，两个序列之间相似性比 对的得分就越高。当然，这只是一个用来说明比对原理的简单例子，序列很短，只有 10 来 个残基，而大多数蛋白质序列的长度为 200 到 500 个残基，甚至更长。其次，这两个序列的 长度几乎相等，而在实际情况下代查序列和目标序列的长度往往差别很大。此外，这两个序 列的大部分残基相同，没有其它可选择的匹配方式。 另一方面，序列比对结果也可以根据引入空位的数目和非匹配残基的数目来度量。由 此而引出距离矩阵的概念，即可以用距离矩阵的方式表示两个序列之间的相似性距离。序列 比对所用的距离矩阵可能不止一个，同一算法的不同实现所用的距离矩阵可能会有所不同。 4.6 子序列 为了进一步说明序列比对的基本原理，下面我们用一对比较接近实际的序列。假定序 列 A 有 400 个残基，序列 B 有 650 个残基。如果序列 A 与序列 B 的一部分相同，则可以认 为 A 是 B 的子序列。此时，只要在适当部位插入空位，就可以使序列 A 和序列 B 完全匹配。 假定序列 A 中有两个片段分别与序列 B 中的两个片段相同。通过序列比对，可以找出 这些相同片段，并在序列 A 中插入空位，使序列 A 与序列 B 有最大的匹配，如图 6.2（b） 所示。此时，可以找出序列 A 与序列 B 之间具有最好匹配的子序列。利用简单的渐进算法， 可以直接实现上述比对，因为两个序列之间的相似片段比较明显。 4.7 同一性和相似性 上述序列比对实例只是简要说明了如何找出两个序列之间完全相同的片段。实际操作
中可以利用计算机程序实现上述序列比对的基本算法。然而,序列比对不仅需要考虑子序列 之间的匹配,而且需要对整个序列进行比较。也就是说,必须考虑两个序列中所有残基的匹 配。这就意味着,不可能使所有残基都能严格匹配。在这种情况下,比对过程中确定空位的 过程变得十分复杂。最简单的办法使通过不加限制地插入空位的办法获得相同残基的最大匹 配数。我们知道,空位的引入,意味着两个序列之间残基的插入或删除。如果对引入空位不 加限制,所得比对结果即使分值较高,也缺乏生物学依据。因此,必须有一种机制,对空位 的引入加以限制。常用的方法就是空位罚分,即每插入一空位就在总分值中罚去一定分值, 即加上一负分值,包括起始空位罚分和延伸空位罚分。所谓起始空位,是指序列比对时,在 一个序列中插入一个空位,使两个序列之间有更好的匹配:所谓延伸空位,是指在引入一个 或几个空位后,继续引入下一个连续的空位,使两个序列之间有更好的匹配。延伸空位罚分 值可以与起始空位罚分值相同,也可以比起始空位罚分值小。因此,序列比对最终结果的分 数值是两个序列之间匹配残基的总分值与空位罚分的总和 上述序列比对过程中,只考虑了残基的同一性,即两个序列之间完全相同的匹配残基 数目。可以把这种只考虑残基同一性的矩阵理解为一个分数值为1和0的分数矩阵(见表 6.1),即相同残基的分数值为1,不同残基的分数值为θ。这种矩阵通常称为稀疏矩阵,因 为矩阵大多数单元的值为0。显然,这种单一的相似性分数矩阵具有很大局限性。改进分数 矩阵的表征性能,找出那些潜在的具有生物学意义的最佳匹配,提高数据库搜索的灵敏度 而又不至于降低信噪比,是序列比对算法的核心 相似性分数矩阵就是为解决上述问题而产生的。相似性分数矩阵的构建,是基于远距离 进化过程中观察到的残基替换率,并用不同的分数值表征不同残基之间相似性程度。恰当选 择相似性分数矩阵,可以提高序列比对的敏感度,特别是两个序列之间完全相同的残基数比 较少的情况下。必须说明,相似性分数矩阵有其固有的噪声,因为它们在对两个具有一定相 似性的不同残基赋予某个相似性分值时的同时,也引进了比对过程的噪声。这就意味着随着 微弱信号的增强,随机匹配的可能性也会增大。本书不准备深入讨论有关相似性分数矩阵的 问题,而只对两个常用的相似性分数矩阵作简单介绍,即突变数据矩阵和残基片段替换矩阵。 471突变数据矩阵 突变数据矩阵( Mutation data matriⅸx,简称MD, Dayhoff等,1978)是基于单点可接 受突变的概念,即 Point Accepted Mutation,简称PAM。1个PAM的进化距离表示在100个 残基中发生一个可以接受的残基突变的概率。对应于一个更大进化距离间隔的突变概率矩 阵,可以通过对原始矩阵进行一定的数学处理获得。例如,PAM250相似性分数矩阵相当于 在两个序列之间具有20%的残基匹配。 在序列比对中,通常希望使用能够反映一个氨基酸发生改变的概率与两个氨基酸随机
中可以利用计算机程序实现上述序列比对的基本算法。然而，序列比对不仅需要考虑子序列 之间的匹配，而且需要对整个序列进行比较。也就是说，必须考虑两个序列中所有残基的匹 配。这就意味着，不可能使所有残基都能严格匹配。在这种情况下，比对过程中确定空位的 过程变得十分复杂。最简单的办法使通过不加限制地插入空位的办法获得相同残基的最大匹 配数。我们知道，空位的引入，意味着两个序列之间残基的插入或删除。如果对引入空位不 加限制，所得比对结果即使分值较高，也缺乏生物学依据。因此，必须有一种机制，对空位 的引入加以限制。常用的方法就是空位罚分，即每插入一空位就在总分值中罚去一定分值， 即加上一负分值，包括起始空位罚分和延伸空位罚分。所谓起始空位，是指序列比对时，在 一个序列中插入一个空位，使两个序列之间有更好的匹配；所谓延伸空位，是指在引入一个 或几个空位后，继续引入下一个连续的空位，使两个序列之间有更好的匹配。延伸空位罚分 值可以与起始空位罚分值相同，也可以比起始空位罚分值小。因此，序列比对最终结果的分 数值是两个序列之间匹配残基的总分值与空位罚分的总和。 上述序列比对过程中，只考虑了残基的同一性，即两个序列之间完全相同的匹配残基 数目。可以把这种只考虑残基同一性的矩阵理解为一个分数值为 1 和 0 的分数矩阵（见表 6.1），即相同残基的分数值为 1，不同残基的分数值为 0。这种矩阵通常称为稀疏矩阵，因 为矩阵大多数单元的值为 0。显然，这种单一的相似性分数矩阵具有很大局限性。改进分数 矩阵的表征性能，找出那些潜在的具有生物学意义的最佳匹配，提高数据库搜索的灵敏度， 而又不至于降低信噪比，是序列比对算法的核心。 相似性分数矩阵就是为解决上述问题而产生的。相似性分数矩阵的构建，是基于远距离 进化过程中观察到的残基替换率，并用不同的分数值表征不同残基之间相似性程度。恰当选 择相似性分数矩阵，可以提高序列比对的敏感度，特别是两个序列之间完全相同的残基数比 较少的情况下。必须说明，相似性分数矩阵有其固有的噪声，因为它们在对两个具有一定相 似性的不同残基赋予某个相似性分值时的同时，也引进了比对过程的噪声。这就意味着随着 微弱信号的增强，随机匹配的可能性也会增大。本书不准备深入讨论有关相似性分数矩阵的 问题，而只对两个常用的相似性分数矩阵作简单介绍，即突变数据矩阵和残基片段替换矩阵。 4.7.1 突变数据矩阵 突变数据矩阵（Mutation Data Matrix，简称 MD，Dayhoff 等，1978）是基于单点可接 受突变的概念，即 Point Accepted Mutation，简称 PAM。1 个 PAM 的进化距离表示在 100 个 残基中发生一个可以接受的残基突变的概率。对应于一个更大进化距离间隔的突变概率矩 阵，可以通过对原始矩阵进行一定的数学处理获得。例如，PAM250 相似性分数矩阵相当于 在两个序列之间具有 20%的残基匹配。 在序列比对中，通常希望使用能够反映一个氨基酸发生改变的概率与两个氨基酸随机
出现的概率的比值的矩阵。这些比值可以用相关几率( relatedness odds)矩阵表示。在序列 比对过程中,两个序列从头到尾逐个残基进行比对,所得几率值的乘积就是整个比对的分值 在实际使用时,通常取几率值的对数以简化运算。因此,常用的突变数据矩阵PAM250实 际上是几率值的对数矩阵(表62)。矩阵中值大于0的元素所对应的两个残基之间发生突变 的可能性较大,值小于0的元素所对应的两个残基之间发生突变的可能性较小。 表62突变数据相似性分数矩阵PAM250 s02 T-213 2 G-310-115 N410-1002 D-500-10124 E500-100134 Q5|-1-10011224 H-3-1-10-1-221136 R40-10230-11126 K500-1-121001035 M5|-21-213232-1-2006 1-2-10-21-32-2-22-2-2-22 L-6-3-23-24343-2-233426 V-2|-10-101|-222-222-22424 F4|33-545-2-65-5-245012-19 Y0|-3353-7-2444044-2-1-1-2710 W8|2566174715|323|45260017 C S T P AGIND EQH R KIM I L VIF YW 表中把理化性质相似的氨基酸按组排列在一起,正值表示进化上的保守替代, 值越大,保守性越大 序列分析的难点是要确定那些仅有20%相似性的序列之间是否具有同源关系。PAM250
出现的概率的比值的矩阵。这些比值可以用相关几率（relatedness odds）矩阵表示。在序列 比对过程中，两个序列从头到尾逐个残基进行比对，所得几率值的乘积就是整个比对的分值。 在实际使用时，通常取几率值的对数以简化运算。因此，常用的突变数据矩阵 PAM250 实 际上是几率值的对数矩阵（表 6.2）。矩阵中值大于 0 的元素所对应的两个残基之间发生突变 的可能性较大，值小于 0 的元素所对应的两个残基之间发生突变的可能性较小。 表 6.2 突变数据相似性分数矩阵 PAM250 C 12 S 0 2 T -2 1 3 P -3 1 0 6 A -2 1 1 1 2 G -3 1 0 -1 1 5 N -4 1 0 -1 0 0 2 D -5 0 0 -1 0 1 2 4 E -5 0 0 -1 0 0 1 3 4 Q -5 -1 -1 0 0 -1 1 2 2 4 H -3 -1 -1 0 -1 -2 2 1 1 3 6 R -4 0 -1 0 -2 -3 0 -1 -1 1 2 6 K -5 0 0 -1 -1 -2 1 0 0 1 0 3 5 M -5 -2 -1 -2 -1 -3 -2 -3 -2 -1 -2 0 0 6 I -2 -1 0 -2 -1 -3 -2 -2 -2 -2 -2 -2 -2 2 5 L -6 -3 -2 -3 -2 -4 -3 -4 -3 -2 -2 -3 -3 4 2 6 V -2 -1 0 -1 0 -1 -2 -2 -2 -2 -2 -2 -2 2 4 2 4 F -4 -3 -3 -5 -4 -5 -2 -6 -5 -5 -2 -4 -5 0 1 2 -1 9 Y 0 -3 -3 -5 -3 -7 -2 -4 -4 -4 0 -4 -4 -2 -1 -1 -2 7 10 W -8 -2 -5 -6 -6 -7 -4 -7 -7 -5 -3 2 -3 -4 -5 -2 -6 0 0 17 C S T P A G N D E Q H R K M I L V F Y W * 表中把理化性质相似的氨基酸按组排列在一起，正值表示进化上的保守替代， 值越大，保守性越大。 序列分析的难点是要确定那些仅有 20%相似性的序列之间是否具有同源关系。PAM250