FastA和BLAST程序是目前最常用的基于局部相似性的数据库搜索程序，它们都基于查找完全匹配的短小序列片段，并将它们延伸得到较长的相似性匹配。它们的优势在于可以在普通的计算机系统上运行，而不必依赖计算机硬件系统而解决运行速度问题。

BLAST是目前常用的数据库搜索程序，它是Basic Local Alignment Search Tool的缩写，意为“基本局部相似性比对搜索工具”[Altschul, 1990, 1997]。国际著名生物信息中心都提供基于Web的BLAST服务器。BLAST程序之所以使用广泛，主要因为其运行速度比FastA等其它数据库搜索程序快，而改进后的BLAST程序允许空位的插入。我们可以访问NCBI的网站在线进行BLAST和FastA的搜索

BLAST搜索

BLAST算法本身很简单，它的基本要点是序列片段对（segment pair）的概念。所谓序列片段对是指两个给定序列中的一对子序列，它们的长度相等，且可以形成无空位的完全匹配。BLAST算法首先找出代查序列和目标序列间所有匹配程度超过一定阈值的序列片段对，然后对具有一定长度的片段对根据给定的相似性阈值延伸，得到一定长度的相似性片段，称高分值片段对（high-scoring pairs, HSPs）。这就是无空位的BLAST比对算法的基础，也是BLAST输出结果的特征。

BLAST软件包实际上是综合在一起的一组程序，不仅可用于直接对蛋白质序列数据库和核酸序列数据库进行搜索，而且可以将检测序列翻译成蛋白质或将数据库翻译成蛋白质后再进行搜索，以提高搜索结果的灵敏度(表3.1)。位置特异性叠代BLAST (Position-Specific Iterated BLAST，简称PSI-BLAST)则是对蛋白质序列数据库进行搜索的改进，其主要思想是通过多次叠代找出最佳结果。具体做法是利用第一次搜索结果构建位置特异性分数矩阵，并用于第二次的搜索，第二次搜索结果用于第三次搜索，依此类推，直到找出最佳搜索结果。此外，BLAST不仅可用于检测序列对数据库的搜索，还可用于两个序列之间的比对。

表3.1BLAST程序检测序列和数据库类型

BLAST程序是免费软件，可以从美国国家生物技术信息中心NCBI等文件下载服务器上获得，安装在本地计算机上，包括UNIX系统和WINDOWS系统的各种版本。但必须有BLAST格式的数据库，可以从NCBI下载，也可以利用该系统提供的格式转换工具由其它格式的核酸或蛋白质序列数据库经转换后得到。对核酸序列数据库而言，不论用哪种方式，都需要很大的磁盘空间；而程序运行时，需要有较大的内存和较快的运算速度，因此必须使用高性能的服务器。对一般用户来说，目前常用的办法是通过NCBI、EBI等国际著名生物信息中心的BLAST服务器进行搜索。北京大学生物信息中心也提供了BLAST数据库搜索服务。需要说明的是，各生物信息中心BLAST用户界面有所不同，所提供的数据库也可能不完全相同，使用前最好先进行适当的选择。欧洲生物信息研究所BLAST服务器的用户界面(图3.3)比较简洁，提供的数据库和参数很多，用户可以根据不同要求，选择不同的数据库和各种参数。一般情况下，可以先按照系统给定的缺省参数进行初步搜索，对结果进行分析后再适当调整参数，如改变相似性矩阵、增加或减少空位罚分值、调节检测序列滑动窗口大小等。对于核酸序列数据库，一般选择重复序列屏蔽功能，而对于蛋白质序列，特别是球蛋白，通常不必选择重复序列屏蔽功能。

http://www.cbi.pku.edu.cn/chinese/documents/bioinfor/overview/web3/Image14.jpg与 FastA" TITLE="Blast 与 FastA" />

图3.3 欧洲生物信息学研究所的BLAST服务器的用户界面

图3.4是BLAST程序运行结果实例。这里，检测序列是与细胞凋亡有关的人自噬基因氨基酸序列，通过欧洲生物信息学研究所的BLAST服务器对包括SwissProt和TrEMBL数据库在内的蛋白质数据库进行搜索。输出结果中包括程序名称、版本号以及文献引用出处，以及检索序列的名称、数据库名称；列出相似性值较高的序列条目，以及它们在数据库中的编号和简要说明。每个条目后面给出相似性分数值Score和期望频率值E，以相似性分数值大小为序排列，分数越高，相似性越大。而E值则表示随机匹配的可能性，E值越大，随机匹配的可能性也越大。最后给出检测序列和目标序列的比对结果(限于篇幅，图中只给出检测序列和一个目标序列的比对结果)。

http://www.cbi.pku.edu.cn/chinese/documents/bioinfor/overview/web3/Image15.gif与 FastA" TITLE="Blast 与 FastA" />

图3.4 BLAST程序运行结果实例

FastA搜索

FastA算法是由Lipman和Pearson于1985年发表的（Lipman和Pearson，1985）。FastA的基本思路是识别与代查序列相匹配的很短的序列片段，称为k-tuple。蛋白质序列数据库搜索时，短片段的长度一般是1-2个残基长；DNA序列数据库搜索时，通常采用稍大点的值，最多为6个碱基。通过比较两个序列中的短片段及其相对位置，可以构成一个动态规划矩阵的对角线方向上的一些匹配片段。FastA程序采用渐进（heuristic approach）算法将位于同一对角线上相互接近的短片段连接起来。也就是说，通过不匹配的残基将这些匹配残基片段连接起来，以便得到较长的相似性片段。这就意味着，FastA输出结果中允许出现不匹配残基。这和BLAST程序中的成对片段类似。如果匹配区域很多，FastA利用动态规划算法在这些匹配区域间插入空位。

由FastA搜索产生的典型输出结果的第一行列出程序名称和版本号，以及该程序发表的杂志。接下来列出所提交的序列，然后是所用参数和运行时间，紧跟这些一般信息的是数据库搜索结果。首先列出搜索得到的目标序列简单说明，其数目可由用户定义。所列出的目标序列的信息包括：序列所在数据库名称的缩写，目标序列的标识码、序列号和序列名等部分信息。括号中标明匹配部分的残基数。紧接着是由程序计算得到的初始化和优化后的分数值。最后一列是期望值即E值（详见6.7.3节），用来判断比对结果的置信度。接近于0的E值表明两序列的匹配不大可能是由随机因素造成的。

允许空位的 BLAST

如上所述，最初的BLAST程序只能用于无空位的比对。经验表明比对结果通常会出现一些无空位但不连续的区域，不难想象，有些高分值片段对可以通过一些相似性较低且有空位的片段连接起来，组成了一些更长的或许更具实际生物学意义的比对。基于上述思路，BLAST算法经过改进允许空位插入（Altshul等，1997）。为缩短对数据库初始搜索的时间，新的算法只找出一个最好的高分值片段，并以此为基础运用动态规划方法将这一片段向两端延伸，最终产生的比对结果可能有空位插入。由于免去了查找所有高分值片段对的步骤，新的算法比原算法快3倍。对BLAST算法的进一步扩充，可以考虑双序列比对和多序列比对的有效结合，下一章将详细讨论具体算法。

位点特异性BLAST叠代搜索

位点特异性BLAST（Position-Specific Iterated BLAST，简称PSI-BLAST）叠代搜索（Altschul等，1997），是一种将双序列比对和多序列比对结合在一起的数据库搜索方法。尽管以下事实已经基本得到认同：基于序列模式的数据库搜索灵敏度较高、特异性较好，因而可以发现一些距离较远但却具有生物学意义的相似序列；它的不足之处也不能予以忽视。除了需要大量的计算资源这一缺点外，对于搜索结果的分析解释常常相当困难。这些制约因素限制了它的实际使用范围。PSI-BLAST的基本思路在于根据最初的搜索结果，依照预先定义的相似性阈值将序列分成不同的组，构建一个位点特异性的序列谱，并通过多次叠代不断改进这一序列谱以提高搜索的灵敏度。

和其它叠代算法一样，PSI-BLAS方法既有不少长处，也有它的弊病。例如，如果在比对前不把胶原蛋白、同源多聚体等低复杂度的重复序列屏蔽掉，自动叠代搜索过程会因为这些重复序列的干扰而失败（Holm，1998）。假如第一轮的搜索结果出现一个错误序列，那么最终搜索结果中将会出现许多不期望的无关序列。因此，为了尽量去除大量的错误匹配，仔细分析搜索结果给出的同源关系变得非常重要。