已知信码序列为1011_从零开始生物信息学(4):序列比对-Blast算法简介

前言

Blast算法的全称是(B asic L ocal A lignment S earch T ool)，中文叫做基本局部相似性比对搜索工具 ，在1990年由Altschul等人提出的双序列局部比对算法，是一套在蛋白质数据库或DNA数据库中进行相似性比较的分析工具。Blast程序能迅速与公开数据库进行相似性序列比较。BLAST结果中的得分是对相似性的统计说明。还有，Blast算法是一种启发式的算法。

为什么需要Blast?

这是因为传统的基于动态规划的局部性比对性算法例如常见的Smith–Waterman采用的是精确的序列比对，也就是算法得到的是比对序列的局部最优解，虽然有着较好的比较结果，但是对于长度为n和m的两个待比较序列，局部性比对算法的时间复杂度有O(mn)，这个时间复杂度对于序列匹配来说代价太大，特别是当序列长度较长的时候。Blast是一种在局部性比对基本上一种近似比对的算法。它在保持较高精度的情况下可以大大减少程序运行的时间，是大规模序列对比问题一个速度和精确性都可以接受的一个解决方法。因此Blast算法很适合用于实际场景中。

算法原理

下面这张图可以很好地刻画整个Blast的算法流程：

1.Filtering

在进行比对之前，我们需要对query的序列进行过滤（通常序列比对是将未知序列与已知的序列进行比对，我们把未知的序列叫做query序列），主要过滤的是低复杂度区域（"Low-complexity region"） ，也就是序列的一段区域只包含种类很少的碱基或者氨基酸，即有大量重复，因为这些区域会导致最后的计算得分很高或者混淆Blast的运算。BLAST的实际作法是，它会把这些区域用符号代替，并且在搜索的时候忽略这些符号。蛋白质序列中，就用X符号标示；而DNA序列中，则用N符号标示。低复杂度区域的部分，BLAST是用一个叫做SEG的程序来处理蛋白质序列，而用叫做DUST的程序来处理DNA序列。而且这一步直接就在seeding之前就完成了。

2.Seeding

首先，需要把比对的序列按照一定长度拆分成多个连续‘seed words’（通常来说对于蛋白质序列是以三个氨基酸为一个seed word, DNA碱基序列以11个长度为一个seed word，这个阈值可以自己定义），word的长度越小，最终的比对准确率就越高，所需要的时间也越长 。比如对于一个蛋白质序列PQFEFG，设定seed word长度为3，那么就可以依次形成四个seed word。

3.Matching

Matching步骤就是与参考序列进行索引的过程，因为我们参考序列一般已经导入到数据库中，并且已经做好了索引了，所以matching这个过程是非常快的，常用的如哈希索引 和后缀树 都是非常高效的索引方式，哈希是典型的空间换时间的算法，而后缀树面对这种字符也有很好的查询性能，并且能节省储存空间。

这样我们就可以得到每个seed word在参考比对序列对应的位置。

4.Extending

这个步骤是整个Blast算法里面最耗时的，主要思想就是希望把匹配得到的seed word延伸成更长的片段，同时，计算延伸后的得分，当得分小于指定的阈值，停止延伸。如下图所示，我们知道最优的匹配结果和主对角线方向是平行的，因此我们沿着主对角线方向进行双方向的延伸，直到打分低于一定的阈值停止，我们将最后的比对结果叫做高分片段对（high-scoring segment pair, HSP） ，这里延伸的方法和Smith-Waterman算法 基本一致，就是只计算MATCH的得分，因为Blast初始版本是不允许有GAP的。

当延伸的得分在下降的时候，我们就选择停止：

最后，我们计算出每个seed Word的HSP得分，并且排序，选取TOP作为候选，通过最后的显著性分析，得到最终结果。

5.显著性分析

通常HSP序列的显著性分析可以通过计算E值来确定，E值（Expect score ）计算如下：

简单说，m是数据库长度，n是query的长度，S是HSP分数，其他两个参数是修正系数，那么这个E值有什么用呢？通过上面的公式，简单理解就是，E值衡量了在随机情况下，数据库存在的比当前匹配分数更好的比对的数目 。听起来有点绕口，我理解就是，假如，我有一个随机生成的seed word AAA，那么它也有一定概率在数据库找到对应的索引，并且计算出一个HSP的得分，但是这个得分是由数据库中对应索引分布决定的，也就是常见的比对更加可靠，我们不希望我们的seed word是一个不可靠的seed，因此我们利用E值来计算统计意义上的均值，来衡量这个seed的可靠程度，比如，E=10就意味着会有10个随机的匹配获得与当前比对相等或者更高的分数。

最后通过设定E值过滤掉不合理的HSP比对序列，最后就可以得到最终比对的结果。

以上就是Blast算法的基本原理。

欢迎大家关注我的知乎专栏：从零开始生物信息学

相同内容也可以关注我的微信公众号: 壹读基因：