blast算法初探

在前面我们探讨了两条序列是如何通过动态规划算法进行比对的，但是在现如今的拥有海量数据的数据库中，想直接通过动态规划算法来将所有的序列与query序列一个一个进行比较式不切实际的。因此NCBI数据库开发了blast算法，用来快速的找到与query序列相似度最高的序列。

blast算法简介

blast算法采用的是一种启发式算法。首先将query序列打断成子片段，称之为seed words，然后将seed与预先索引好的序列进行比对，选择seed连续打分较高的位置采用动态规划算法进行延伸，延伸过程也会进行打分，当打分低于某一限度这一延伸过程就会被终止抛弃，最后产生了一系列的高得分序列。最后还要使用E-value对其显著性进行评估，选出比对结果最好的序列。blast的执行过程大致如下图所示： blast算法执行原理

1、seeding

seeding

对于一条query序列，blast并非直接将其进行比对，而是先将其打断成多个片段（seed words）。而且得到的这些seed words也不是直接拿来用的，还要经过一些过滤处理。
首先，对于那些复杂度低的序列，如重复序列，信息含量少，我们将它从seed words中直接去除，以提高速度和降低假阳性。
其次，为提高比对敏感度，blast还会增加一些seed，称之为“neibourhood words”，这些“neibourhood words”是用seed words采用替换矩阵比对得到的与seed words相似的高得分序列。

2、Index database

image.png

而后，通过事先建立好的索引表，来在数据库中快速定位相关的候选序列 以及在候选序列中的具体位置。通过对所有的seed均重复上述操作，就可以得到查询序列与候选数据库序列之间的hit map。

根据前一单元的讨论，我们知道最优比对对应的路径应该平行于主对角线。 因此，我们可以进一步去掉那些零散的hits， 而只允许沿对角线方向有两个及两个以上连续hits的hit cluster，以便进一步缩小搜索空间。 hit cluster

3、Extension

接下来，我们就可以以这些hit cluster为基础，向左右两个方向延伸以扩展得到HSP， 直到总分数的下降超过一个给定的值X后。 在扩展后的区域，我们可以应用上节课讲过的动态规划算法， 以便确定最终的比对， 从而显著降低了计算量。
在得到HSP后还需最后一步对其进行评估打分排序，以获得最为相似的序列。

4、E-value

为什么要进行评估？
举个例子，对于一个长度为L的蛋白序列， 有(1/20)^L的概率会碰到一条完全一致的随机序列。 也就是说，假定你的蛋白序列长度为6个氨基酸， 这个概率就是1.56 * 10(-8)。 那么，现在你用这个蛋白序列在Swiss-Prot数据库中进行检索， 那么随机情况下就会期望有3个100%的匹配（随机概率*数据库中蛋白质序列的数量）， 即使这个长度为6的序列完全是随机产生的。 因此，我们需要有一个方法，来客观的评估一个比对的统计显著性 在我们得到最终的比对之后， 我们还需要评估这个比对的统计显著性，以确保这个比对不是由随机因素引起的。 在BLAST中，用E-value来对此进行度量。 简单的说，E-value是指在随机情况下，获得比当前比对分数相等或更高分数的可能比对条数。 具体来说，如果一个比对的E-value = 10，就意味着会有10个随机匹配获得与当前比对相等或更高的分数。E-value的值可以利用下面的式子进行计算：

E-value
其中， m是query sequence的长度。 n是数据库的大小。 e是自然对数，S是你的分数。 K和lambda是和打分矩阵相关的 相当于是一个normalization（归一化）的factor（因子）。 从下面的公式我们可以看到， E值的大小与数据库大小n成正比， 也就是说数据库越大，随机匹配的可能性也就越大， 和我们刚刚看到的例子是相符的。 另一方面，E值的大小与查询序列的长度m也成正比 这是因为BLAST是局部比对，不需要全长的匹配。 与我们的直觉相符， E值与比对的分数S负相关， 也就是说如果分数越高， 随机碰上的可能性就越小。 同时，公式中的lambda和k是与打分系统与搜索空间相关的两个修正值， 用来平衡不同打分矩阵以及搜索空间对于结果的影响。
为了方便解释，我们可以进一步的把p值和E值进行相互转换， 从图上可以看出，在小于0.1时， E值和p值，也就是概率值，几乎相等。 特别的，当p取0.05时，对应的E-value为0.0513， 因此也常有人将0.05作为E-value的cut-off。 image.png

总结

与Needleman-Wunsch、Smith-Waterman等基于动态规划的算法不同， BLAST是一种启发式的算法， 也就是说，它并不确保能找到最优解，但尽力在更短时间内找到足够好的解。 具体来说，BLAST通过应用Seeding-and-extending策略，只在有限区域应用动态规划算法， 从而有效地降低了计算量、提高了计算速度。 然而，速度的提高是以灵敏度的下降为代价的， 这也是我们之后会提到的一系列启发式算法所共有的trade-off。

参考：北京大学公开课——生物信息学: 导论与方法