简介

背景

算法

简介

生物资讯学中（生物信息学），BLAST(Basic Local Alignment Search Tool") 它是一个用来比对生物序列的一级结构（如不同蛋白质的氨基酸序列或不同基因的DNA序列）的算法。 已知一个包含若干序列的数据库，BLAST可以让研究者在其中寻找与其感兴趣的序列相同或类似的序列。 例如如果某种非人动物的一个以前未知的基因被发现，研究者一般会在人类基因组中做一个BLAST搜索来确认人类是否包含类似的基因（通过序列的相似性）。BLAST算法以及实现它的程序由美国国家生物技术信息中心（NCBI）的Eugene Myers、Stephen Altschul、Warren Gish、David J. Lipman及Webb Miller博士开发的。

背景

BLAST是一个被广泛使用于分析生物资讯的程式，因为它可以兼顾我们在做搜寻时的速度以及搜寻结果的精确度。因为当我们所要搜寻的目标数据库非常庞大的时候，速度就变成一项很需要考量的因素。在像BLAST和FASTA这些快速算法被开发之前，我们是使用动态规划算法来作数据库的序列搜寻，这真的非常的耗时。BLAST使用启发式搜索来找出相关的序列，在速度上比完全只使用动态规划大约快上50倍左右，不过它不像动态规划能够保证搜寻到的序列（Database sequence）和所要找的序列（Query sequence）之间的相关性，BLAST的工作就是尽可能找出数据库中和所要查询的序列相关的资讯而已，精确度稍微低一点。此外，BLAST比FASTA更快速，因为BLAST只对比较少出现或是较重要的一些关键字作更进一步的分析，而FASTA是考虑所有共同出现在所要搜寻的序列和目标序列的字。从下面介绍的算法可以更进一步的了解。

算法

这边我们以蛋白质对蛋白质序列搜寻所用的程式BLASTP之实做的步骤，来了解BLAST这程式的主要思想。移除Query序列中之低复杂度以及有串接重复现象的区域低复杂度是指由很少种类的元素（如氨基酸）所组成的一个区域；而串接重复现象是指在一个Query序列中，有两段串连的区域它们组成的方式一模一样。这两种在序列中的区域可能会让BLAST找出一些虽然分数够高，但是其实和Query序列并不相关之序列，所以在我们执行搜寻之前，要先把Query序列中的这两种区域滤掉。BLAST的实际作法是，它会把这些区域用符号代替，并且在搜索的时候忽略这些符号。蛋白质序列中，就用X符号标示；而DNA序列中，则用N符号标示。低复杂度区域的部份，BLAST是用一个叫做SEG的程式来处理蛋白质序列，而用叫做DUST的程式来处理DNA序列。另一方面，，蛋白质序列中之串接重复现象的区域则是使用XNU来处理。将Query序列中每k个字的组合做成一个表以k=3为例（DNA序列中，我们则常以k=11为例），我们"依序"将Query序列中每3个字的组合视为一个字组，并将这些字组列在一张字组表上，直到Query序列中最后一个字也被收入进表上为止。由图一可以更清楚的了解整个作法。