数据库相似性搜索.ppt

《数据库相似性搜索.ppt》由会员分享，可在线阅读，更多相关《数据库相似性搜索.ppt（34页珍藏版）》请在三一办公上搜索。

1、第四章 数据库相似性搜索,王红岩,序 言,序列两两比对的一个主要应用就是在数据库中基于相似性检索生物序列。这个过程包括提交查询序列和对查询序列与数据库中的每一序列进行两两比对。所以数据库相似性搜索就是一个大规模的序列两两比对。这种类型的搜索是一种最有效的用来推导新测定序列功能的方法。然而，第三章讲述的动态规划算法速度太慢因此大多数时候是不实用的。为了提高序列比较的计算速度需要特殊的搜索方法。这章将要介绍数据库搜索方法的理论和应用。,数据库搜索的独特要求,对序列数据库进行搜索的算法有独特的要求。第一个标准是敏感性，它是指找到尽可能多的相似序列的能力。它是用正确识别属于同一家族的序列范围来度量的。

2、这些正确识别的序列在数据库搜索中被认为是“真阳性“。第二个标准是选择性，也叫特异性，它是指排除不正确序列的能力。这些不正确的序列是在数据库搜索中被错误识别的无关序列，它们被称为”假阳性“。第三个标准就是速度，它是指从数据库搜索中得到结果所用的时间，这依赖于数据库的大小，有时速度可能是最重要的因素。理想上，人们总是希望在数据库搜索中得到最大的敏感性，特异性和速度。然而，同时满足这三个要求在实际中是非常困难的。通常是提高了敏感性就降低了特异性。而降低特异性又可能会使结果包含许多假阳性。同样的，提高速度经常会付出敏感性和特异性下降的代价。我们经常需要在这三个标准之间作出折衷。,数据库搜索的独特要求,

3、在数据库搜索和许多其它生物信息学领域中有两种基本类型的算法。一种是穷举法，它用一种严格的算法通过考察所有的数学组合来找一个特定问题的最佳的或者精确的解。动态规划算法是穷举法的一个例子，它在计算上是非常精确的。另一种是启发式方法，它是一种利用拇指规则（经验法则）来寻找经验上的或是近似最优结果的计算策略。本质上，这种类型的算法是一种根据一些标准缩小搜索空间的快捷方法。然而，这种快捷方法并不保证找到最佳或是最精确的结果。经常用它是因为要在不显著牺牲计算结果的正确性情况下和可以接受的时间内获得结果。,启发式数据库搜索,用动态规划算法，比如Smith-Waterman算法，搜索一个大型数据库尽管是精确可

4、靠的，但是速度太慢以至于在计算机资源有限的时候是不切实际的。十年前做的一个估计显示，用当时的常规计算机系统以一个包含100个残基的查询序列搜索一个包含300000个残基的数据库需要2-3小时。因此搜索速度成为一个重要的问题。为了提高比较速度必须使用启发式方法。启发式算法之所以表现出更快的搜索速度是因为它只考察那些用动态规划算法计算过的有可能匹配的序列。,启发式数据库搜索,目前，主要有两种用于数据库搜索的算法：BLAST和FASTA。这些算法不保证能找到最理想的比对和真正同源的序列，但是比动态规划算法快50-100倍。提高速度是通过适度地牺牲搜索的敏感性和特异性实现的，而这种牺牲很容易被分子生物

5、学工作者接受。两种算法都能通过识别相似序列片段来合理地预测序列的相似性。,启发式数据库搜索,BLAST和FASTA都是用基于单词的启发式方法来进行快速序列两两比对的算法。这是序列两两比对的第三种方法。它是通过寻找两条序列中显著的或是近似显著的相似连续字母来实现的。这些短的字符串叫做单词，它类似于点阵法中用到的窗口。一个基本的假设是两条相关序列中至少包含一个共同单词。在识别出匹配的单词后，用一个比较长的算法来从单词开始扩展相似区域。一但找到高得分的序列相似区域，就把这些高得分区域连接起来以得到一个全序列比对。,基本局部比对搜索工具（BLAST）,BLAST程序是NCBI的Stephen Alts

6、chul于1990年发明的，它目前已经成为最流行的序列分析程序之一。BLAST使用启式方发法比对查询序列和数据库中的所有序列。它的目标是找到相关序列间的高得分无空位片段。高于给定阈值的这种片段的存在说明序列相似不是随机的，它能帮助人们从数据库中不相关的序列中辨别相关的序列。BLAST通过下面的过程来完成序列比对。第一步是根据查询序列建立一个单词列表。一般地，每一个单词对于蛋白质序列来说包含3个残基，对于DNA序列来说包含11个残基。这个列表包含从查询序列中提取的所有可能单词。这个步骤也叫搜索种子。第二步是搜索出现这些单词的数据库中的序列。这步是识别包含匹配单词的数据库序列。,基本局部比对搜索工

7、具（BLAST）,第三步是用一个给定的得分矩阵给匹配的单词打分。如果一个单词的得分高于某个阈值就认为它是匹配的。第四步是通过用同样的得分矩阵给比对打分来从两个方向扩展单词。扩展一直继续直到比对得分由于失配降低到一个阈值之下为止（蛋白质序列的下降阈值是22 而DNA序列是20）。得到的结果是叫做高得分片段对（HSP）的无空位连续片段对。在BLAST的原始版本中，最高得分的高得分片段对就作为最后的结果了。它们也叫做最大得分对。在最近的BLAST的改进的程序中可以进行有空位比对。在有空位的BLAST中，用动态规划算法从两个方向扩展选择的最高得分片段以引进空位。如果得分高于某个阈值扩展就继续；否则就终

8、止。然而，总的得分允许临时低于阈值最后再达到阈值之上。在得到最后比对结果之前需要对末端区域进行修整。,基本局部比对搜索工具（BLAST）,变形 BLAST是一个包含BLASTN，BLASTP，BLASTX，TBLASTN和TBLASTX的程序族。BLASTN用一个核酸序列查询核酸数据库。BLASTP用一个蛋白质序列作为查询序列来查询蛋白质序列数据库。BLASTX用核酸序列作为查询序列，它把查询序列按照六种阅读框翻译成蛋白质序列然后查询蛋白质序列数据库。TBLASTN用蛋白质序列作为查询序列查询核酸序列数据库，查询时把数据库中的核酸序列按照六种阅读框翻译成蛋白质序列。TBLASTX用核酸序列作为

9、查询序列去查询核酸序列数据库，查询时查询序列和数据库中序列都被按照六种阅读框翻译成蛋白质序列。,基本局部比对搜索工具（BLAST）,变形 如果要在新测定的基因组序列中搜索编码蛋白质的序列就要用到TBLASTN，它会把数据库中的核酸序列按六种阅读框翻译成蛋白质序列。它可以帮助人们识别出还没有注释的编码蛋白质的基因。如果查询序列是DNA序列，那么可以用TBLASTX进行蛋白质水平的比较。然而两个程序都是非常精细的所以搜索过程可能很慢。,基本局部比对搜索工具（BLAST）,变形 BLAST web服务器（）已经被设计出来了，它能简化选择程序的任务。程序是基于查询序列的类型（蛋白质序列，DNA序列还被

10、翻译的DNA序列）组织的。除此之外，特殊用途的程序被单独编组。例如，bl2seq，免疫球蛋白BLAST和VecSceen，一个去除序列的载体污染的程序。被设计用来搜索基因组数据库的程序也被单独列出来。,基本局部比对搜索工具（BLAST）,统计显著性 BLAST的输出结果提供一系列按统计显著性分级的匹配序列。显著性分数帮助人们从不相关的序列中识别出有进化关系的序列。一般说来，只有分数高于某个阈值的相似序列才被显示出来。这里的统计度量与单个序列两两比对稍微不同；数据库越大存在的不相关序列比对就越多。这就需要一个新的参数来计算进行序列比对的总次数，这个次数是同数据库的规模成正比的。在BLAST搜索中

11、这个统计量就是E值（期望值），这个值反映了从数据库中搜索出的比对结果是随机得到的可能性。,基本局部比对搜索工具（BLAST）,统计显著性 E值同用来评估单序列两两比对的P值相关。BLAST比较查询序列和数据库中的所有序列，所以E值是用下面的公式得到的：E=m*n*P 其中m是数据库中总的残基数，n查询序列的残基数，而P是指一个高得分片段对是由随机得到的可能性。,基本局部比对搜索工具（BLAST）,统计显著性 例如，用一个含有100个残基的序列去查询一个共包含1012个的残基的数据库，对于数据库中每一个匹配序列的无空位高得分片段对的P值都是110-20。那么E值就是这三个值的乘积，其结果表示为

12、100101210-20，等于10-6。在BLAST的输出结果中它被表示成 le-6。它表示这个数据库中序列的匹配是随机发生的可能性是10-6。,基本局部比对搜索工具（BLAST）,统计显著性 E值提供了一个给定的序列纯粹是由于随机匹配得到的可能性。E值越低，数据库序列匹配是随机发生的可能性就越小，因此匹配就越显著。对于E值的经验上的解释是这样的。如果E值小于le-50，那么数据库的匹配序列是同源关系的可能性就极高。如果E值在le-50至0.01之间，那么匹配序列可以被认为是同源的。如果E值在0.01至10之间，那么匹配就是不显著的，但是可以暂时被认为具有远源关系，如果有其它的证据就可以确认它

13、们的同源关系。如果E值大于10，那么序列就被认为不相关的或者具有极远的关系以至于用现有的方法无法发现。,基本局部比对搜索工具（BLAST）,统计显著性 因为E值很可能受到数据库大小的影响，一个明显的问题是随着数据库的增大，给定的匹配序列的E值也会增大。因为两条序列的真正的进化关系是保守的，所以随着数据库的增长序列匹配的可信度就会降低，也就是说随着数据库的增大可能丢失先前已经确定的同源关系。因此，需要一种替代E值的计算方法。,基本局部比对搜索工具（BLAST）,统计显著性 bit分数是除了E值之外在BLAST的输出中用到的另一个重要的统计指示量。bit分数不依靠查询序列的长度和数据库的大小衡量序

14、列的相似性，需要用严格序列两两比对分数对它进行标准化。bit分数（S）是用下面的公式得到的。S=(S-lnK)/ln2 其中是坎贝尔分布常数，S是严格序列比对分数，K是与使用的得分矩阵有关的常数。很明显，bit分数与严格比对分数是线性相关的。因此，bit分数越高匹配的显著性就越高。不管是搜索不同大小的不同数据库还是在数据库增长过程中搜索不同时间的同一个数据库，Bit分数都提供了一种固定的统计指示量。,基本局部比对搜索工具（BLAST）,低复杂性区域 对于蛋白质序列和DNA序列都存在包含高度重复残基的区域，比如重复的短片段，或者是由少数残基组成的高度重复片段。这些区域被认为是低复杂性区域（LCR

15、s）。低复杂性区域在数据库序列中是非常普遍的，估计低复杂性区域占公共数据库中蛋白质序列的15%。查询序列中的这些成分会引起假的数据库匹配从而人为地提高了不相关序列比对分数。,基本局部比对搜索工具（BLAST）,低复杂性区域 为了避免由于低复杂性区域的匹配引起的高相似得分使真正相似的序列不显著的问题，过滤掉查询序列和数据库中序列的问题区域以提高信噪比是非常重要的。常用的过程是掩蔽。一共有两种类型的掩蔽：硬掩蔽和软掩蔽。硬掩蔽就是在BLAST程序中用一个意义不明确的字符，如核酸序列用的N或蛋白质序列用的X，来取代问题区域以避免使用问题区域比对从而避免假阳性。缺点是由于缩短了比对的长度可能使真正同源

16、的序列得分降低。软掩蔽保留问题序列但是减小它们的作用，就是在构建单词表的时候忽略它们，但是在单词扩展和最优化比对时使用它们。,基本局部比对搜索工具（BLAST）,低复杂性区域 SEG是一个能在执行数据库搜索前识别并掩蔽重复序列的程序。它通过比较某一区域残基的出现频率和在数据库中残基出现的平均频率来识别低复杂性区域。如果查询序列的某一区域的残基出现频率明显高于数据库中的平均频率，则这个区域就被标记为低复杂性区域。SEG已经被集成到基于web的BLAST程序中。需要一个低复杂性过滤器选项面板来标记低复杂性区域。RepeatMasker(/)是一个用Smith-Waterman算法通过比较查询序列和

17、包含重复序列的固定的库来识别重复序列的独立的掩蔽程序。如果某一序列区域的比对得分高于阈值，这个区域就被认为是一个低复杂性区域。对应的碱基被掩蔽为N或X。,基本局部比对搜索工具（BLAST）,BLAST的输出格式 BLAST的输出包括一个图示，一个匹配列表和一个序列比对的文本说明。图示包括带颜色的横线，通过它们可以快速识别出数据库序列匹配的数目和匹配的相似性得分。横线的颜色与匹配序列的相似性一致（红色：最相关，绿色和蓝色：适度相关，黑色：不相关）。横线的长度代表了匹配序列相对于查询序列的跨度。每一条横线都被链接到与这条序列相关的文字说明部分。图示的下面是一组按E值递增的顺序排列的相匹配序列。每一

18、个序列都包含登录号，数据库记录的题目（通常是一部分），bit分数和E值。,基本局部比对搜索工具（BLAST）,BLAST的输出格式 匹配序列列表下面就是文本说明。它包括三个部分：头部，统计资料和比对。头部包括基因索引号或者是数据库序列的参考文献号和一行的数据库序列描述。在它下面是搜索输出的统计资料，它包括bit分数，E值，一致性比例，相似性比例和空位。在具体比对部分，查询序列在一对序列的上部而搜索出来的数据库序列在下部并且被标号为Object。在两条序列之间，相一致的残基被写在相应的位置，而不一致但是相似的残基用“+”标记。查询序列中任何被标记为低复杂性区域的残基都被标记为X或N所以比对不包含

19、这些区域。,FASTA,FASTA（FAST ALL，)实际上是第一个数据库相似性搜索工具，它出现在BLAST之前。FASTA用哈希策略来查找长度为k的一小段连续的残基之间的匹配。这种残基组成的字符串叫做k元组，它和BLAST中的单词是同义的，但是通常比单词短。k元组的典型长度是蛋白质序列为两个残基而DNA序列为六个残基。FASTA算法的第一步是用哈希策略识别两条序列中的k元组。这种策略是构造显示两条序列中每一个k元组位置的查找表。两条序列中的每一个共同k元组的位置差是通 过用第一条序列中的位置减去第二条序列中的位置来得到的，这个差被表示为位移。具有相同位移值的k元组被连接起来表示一段连续的一

20、致性序列区域，它对应于二维矩阵中的一条连续的对角线。,FASTA,第二步是缩小两条序列之间的高相似区域。通常，在哈希阶段能识别出两条序列之间的许多对角线。具有最密集对角线的前十个区域被识别出来作为高相似区域。对这些区域中的对角线用一个得分矩阵进行打分。沿同一条对角线的邻近的高相似区域被连接起来形成单一序列比对。这个阶段允许应用空位罚分从而在不同的对角线之间引进空位。引进空位之后的得分需要重新计算出来。在第三步中，用Smith-Waterman算法对引进空位的比对进一步提炼以得到最终的比对。最后一步是向BLAST算法一样用E值对最终比对结果进行统计评价。,FASTA,和BLAST相似，FASTA

21、也有许多子程序。欧洲生物信息学协会提供基于web的FASTA程序允许使用蛋白质或核酸序列作为查询序列来搜索蛋白质序列或核酸序列数据库。可靠的程序的变形有FASTX，它先把DNA序列翻译成蛋白质序列然后用这个蛋白质序列查询蛋白质序列数据库，还有TFASTX，他以蛋白质序列作为查询序列，用它去搜索翻译成蛋白质序列的DNA序列数据库。,FASTA,统计显著性 FASTA也使用E值和bit分数。在FASTA中估计这两个参数本质上和BLAST相同。不过，FASTA提供了一个更具有统计意义的参量就是Z分数。它描述在数据库搜索中与平均分数的标准误差。因为大多数的与查询序列的比对都是不相关序列比对，所以得到的

22、匹配序列的Z分数越高，比对得分离得分分布的平均值就越远，匹配就越显著。如果Z分数大于15就认为匹配是极其显著的，它们当然就是同源关系。如果Z分数在5到15的范围内，序列对被认为有很高的同源可能性。如果Z分数小于5，它们的关系就非常不确定。,FASTA与BLAST的比较,BLAST和FASTA在常规数据库搜索中显示了同样好的性能。然而这两种方法之间也存在一些值得注意的不同点。最主要的不同是在搜索种子阶段。BLAST是用替换矩阵查找匹配的单词，而FASTA是用哈希过程识别显著匹配单词。在默认情况下，FASTA扫描更小的窗口。所以，它给出比BLAST更敏感的结果。在BLAST中使用低复杂性掩蔽技术，

23、使它得到的结果比FASTA具有更高的特异性，因为它降低了潜在的假阳性。BLAST有时给出一条序列的多个最高得分比对，而FASTA只能给出一个最终比对结果。,用Smith-Waterman算法进行数据库搜索,前面已经提到，严格的动态规划算法通常不能用来进行数据库搜索，因为它计算速度慢而且花费代价大。启发法如BLAST和FASTA 提高了计算速度。然而，启发式方法在敏感性方面存在局限而且不保证能找到最佳比对。它们经常不能找到数据库中的远距离相关序列。估计指出对于一些蛋白质序列家族，BLAST会丢失30%的真正同源序列。目前计算技术的发展，如巨型计算机的并行处理，使得动态规划算法成为能满足性能要求的

24、数据库搜索算法。,用Smith-Waterman算法进行数据库搜索,为了实现这个目的，Needleman-Wunsch 和 Smith-Waterman算法的机器代码必须进行修改以使它们能在并行处理环境中运行从而使搜索过程能在合理的时限内完成。目前，它的搜索速度仍然比流行的启发式算法慢。所以，这种方法还不能用在日常工作中。不过，可以利用动态规划算法在序列的水平上找到具有最大敏感性的同源序列。经验上的测试显示穷尽式算法确实能比启发式算法得到更加优秀的结果。下面是一些基于动态规划算法的用于数据库搜索的web程序。,用Smith-Waterman算法进行数据库搜索,ScanPS(Scan Prote

25、in)是一个基于web的适用于并行处理的 Smith-Waterman算法的改进版本的实现程序。它的主要特点是可以像PSI-BLAST那样进行反复的搜索，PSI-BLAST通过第一轮计算结果建立一个数据表，在第二轮搜索中会用到这个表。为了增加敏感性每一轮都使用完整的动态规划算法。ParAlign()是一个基于web的服务器程序，它使用并行处理,用Smith-Waterman算法的并行版本或具有更高速度的启发式算法来进行穷尽式比对。启发式子程序首先找到精确的无空位比对然后以它们为锚点通过合并比对矩阵中的几条对角线的得分来扩展有空位比对。ParAlign 方法的处理速度相当于BLAST但是具有更高

26、的敏感性。,总 结,数据库相似性搜索是分析新的基因或蛋白质序列的基础阶段。在数据库搜索中主要的问题是敏感性，特异性和速度。在搜索大型数据库时速度是最重要的问题。所以为进行有效的数据库相似性搜索提出了启发式方法。主要的启发式数据库搜索算方法是BLAST和FASTA。它们都是使用基于单词的方法进行序列两两比对。BLAST是在数据库中寻找高得分对。而FASTA是用哈希方法识别单词。,总 结,这两个算法使用的主要的数据库匹配显著性统计度量是E值和bit分数。需要注意的是在数据库搜索时要用掩蔽程序过滤低复杂性区域。另外需要注意的一点是用蛋白质序列查询数据库，因为这样可以产生具有更高敏感性的匹配。另外，需要记住BLAST和FASTA都是启发式程序，它们不保证找到所有的同源序列。这些程序会自动地产生显著性的匹配，我们应该用更严格的独立序列比对程序对结果进行检验。计算技术的进步已经使运用完全动态规划程序进行更具敏感性和特异性的数据库查询成为可能。,谢 谢 大 家!,