FASTA
FASTA程序是第一个广泛使用的数据库相似性搜索程序。为了达到较高的敏感程度，程序引用取代矩阵实行局部比对以获得最佳搜索。但众所周知，使用这种策略会非常耗费工作时，为了提高速度，在实施耗时的最佳搜索之前，程序使用已知的字串检索出可能的匹配。在速度和敏感度之间权衡选择依赖于ktup参数，它决定了字串的大小。增大ktup参数就会减少字串命中的数目，也就会减少所需要的最佳搜索的数目，提高搜索速度。缺省的ktup值在进行蛋白比较时选择2，但是在间距较大的情况下，将ktup值降为1较为理想。
FASTA程序并不会研究每一个遇到的字串命中，但在一开始会寻找包含若干个附近的命中的片段。使用启发式方法，这些片段会被赋予分值，最好的一个在输出时会显示为init1分值，这若干个片段会被组合起来，一个新的initn分值会从中计算出来。然后在最好的初始片段中局限于其对角线带上，会进行一次包含空位的局部比对以评估最可能的匹配。这个最佳比对的分值会在输出时显示为opt分值。对最后报导的比对来说，还要进行一次全程的Smith-Waterman比对。图7.9b显示了一个例子。对数据库中的每一个序列都只会由一个最佳的比对，但是，如果蛋白质中包含若干个模块，一些很有意义的比对就会被错过，匹配序列还必须由LALIGN程序作进一步分析。
从2.0版本开始，FASTA对每一个检索到的比对都提供一个统计学显著性的评估。程序为随机分值假定了一个极值分布，但是改写了概率密度函数的形式，其中预期的分值与数据库中的序列长度的自然对数呈线形关系，这样，可以使用简单的线形回归函数计算常规的比对的z值。最后，计算出预期的E值，从而给出那些z值不小于已知值的随机比对的预期数目。
BLAST
BLAST程序对数据库搜索进行了大量的改良，提高了搜索速度，同时把数据库搜索建立在了严格的统计学基础之上。但是，为了达到这一目的，仍然需要权衡选择，也就是说，局部比对的限制条件可能不包括空位。这个限制条件对应用
Karlin-Altschul统计学极为有利，另一方面，既然空位没有明确地放在模型中，结果就不会象人们期望的那样接近于预期的比对。这并不是说插入和确实会妨碍匹配，在大多数情况下，比对仅仅会被分解为若干个明显的HSPs。无论如何，老版本的BLAST程序（1.4以前）的局限性在新版本中已经被消除了，新版本在对待空位问题上有着明确的作法（在下面讨论）。
对于一个即将被BLAST程序报告的比对，其中必然包含一个HSP，其分值不小于终止值S。这个终止值因人而异，但是使用时是很难知道其合适值的。因为程序基于Karlin-Altschul统计学，人们可以指明一个预期的终止E值，然后软件会在考虑搜索背景的性质的基础上（比如数据库的大小，取代矩阵的性质）计算出正确的S值。BLAST的一项创新就是邻近字串的思想。这个协定不需要字串确切地匹配，在引入取代矩阵的情况下，当主题序列中的字串有一个最低分值T时，BLAST就宣布找到了一个命中的字串。这个策略允许较长字串长度（W）（为了提高速度），而忽略了敏感度。于是，T值称为制衡速度和敏感度的临界参数，而W是很少会变化的。如果T值增大，可能的命中字串的数目就会下降，程序执行就会加快，减小T值会发现较远的关系。
发生一个字串命中后，程序会进行没有空位的局部寻优，比对的最低分值是S。将比对同时向左方和右方延伸并将分值加和就会得到结果。当遭遇一系列的最低分值时，加和的分值就会下降，这时，分值就不再可能反弹回S值。这个发现为附加的启发式知识提供了依据，因此，当分值的降低（与遭遇的最大值相比）超过分值下降阈值X时，命中的延伸就会终止。于是，系统回减少毫无指望的命中延伸，继续进行其它操作。
使用BLAST
可以通过e-Mail、WWW或控制台命令操作BLAST程序，无论如何，一次数据库搜索包括四种基本元素：BLAST程序的名称，数据库名称，查询序列和大量的合适的参数，很显然，当以上元素发生变化时，搜索的细节就会随之改变。为
了避免混淆，我们把BLAST功能性描述为普通名词，避免提及专有工具。读者可能会要参考使用到的专有工具的有关内容。要得到关于用e-Mail执行BLAST搜索的介绍，给blast@ncbi.nlm.nih.gov发一封含有“HELP”的邮件；在WWW工具中，帮助是在线的；如果使用Unix系统，使用man blast可以获得详细的帮助信息。
表7.1、BLAST程序： 程序 Blastp 数据库 蛋白质 查询 蛋白质 内容 使用取代矩阵寻找较远的关系：可以进行SEG过滤。 核苷酸 核苷酸 寻找较高分值的匹配，对较远关系不太适用。 对于新的DNA序列和ESTs的分析极为有用。 Tblastn 蛋白质 核苷酸（翻译） 对于寻找数据库中没有标注的编码区极为有用。 对于分析EST极为有用。 Blastn Blastx 核苷酸（翻译） 蛋白质 tblastx 核苷酸（翻译） 核苷酸（翻译） 几种不同的BLAST可以通过查询序列和数据库序列的类型来加以区分：blastp比较的是查询蛋白同蛋白质数据库；相应于核酸序列的程序是blastn；如果序列类型不同，DNA序列可以被翻译成蛋白序列（所有六种阅读框架）后同蛋白序列进行比较，blastx比较一个DNA的查询序列同一个蛋白质序列库，其结果对分析新序列和ESTs很有用；对于一个基于核酸序列库的蛋白质查询，tblastn程序对于寻找数据库中序列的新的编码区很有用；最后一个只在特殊情况下使用（在这里介绍只是出于完整的考虑），tblastx将DNA查询序列和核酸序列库中的序列全部翻译成蛋白质序列，然后进行蛋白质序列比较，这个程序主要应用于
ESTs比较，尤其是当人们怀疑到其中有可能的编码区，即使并没有确切地发现这一区域。
所有这些程序使用服务器上的序列数据库，从而不需要本地的数据库，表7.2和7.3陈列了一些BLAST使用的蛋白质和核酸的序列数据库。对于常规的搜索，nr数据库拥有大量的氨基酸和核酸序列，同时合并相同的序列以减少冗余度。为了检测在过去30天里提出或更新的序列，提供了一个称为“month”的数据库。不管是nr还是month，都是日日更新。表7.2和7.3中列出的其它一些数据库在一些特别的环境里十分有用，比如在比较模型物种（酵母和大肠杆菌）的全序列时，搜索特别类型的序列（dbest或dbsts），或检测是否存在污染或问题序列（vector，alu或mito）。 表7.2、使用BLAST的蛋白序列数据库： 数据库 Nr 描述 融合了Swiss-Prot,PIR,PRF以及从GenBank序列编码区中得到的蛋白质和PDB中拥有原子坐标的蛋白质，绝非多余。 Month Nr的字集，每月（30天）更新，搜集了过去30天中的最新序列。 Swissprot Swiss-Prot数据库。 拥有三维空间结构的原子坐标的氨基酸序列库。 Pdb Yeast 由酵母基因组中基因编码的全套蛋白质。 ecoli 有大肠杆菌基因组中基因编码的全套蛋白质。 表7.3、使用BLAST的核苷酸序列数据库：
数据库 Nr 描述 极有价值的GenBank，排除了EST，STS和GSS部分。 Month Nr的字集，每月（30天）更新，搜集了过去30天中的最新序列。 Est Genbank中的EST部分（expressed sequence tags, 表达序列标签）。 Sts Genbank中的STS部分 (sequence tagged sites， 序列标签位点)。 Htgs Genbank中的HTG部分 (high throughput genomic sequences， 高容量基因组序列)。 Gss GenbankGSS(genome survey sequences，基因组测定序列)。 酵母的全基因组序列。 Yeast Ecoli 大肠杆菌的全基因组序列。 Mito 脊椎动物线粒体的全基因组序列。 Alu 搜集了灵长类动物的Alu重复序列。 搜集了流行的带菌体的克隆。 vector 一个BLAST搜索的例子会介绍搜索输出的不同元素。如图7.11所示的例子，一种Alzheimer疾病感受性蛋白质的氨基酸序列（由GenBank中L43964翻译）作为查询序列同dbest数据库用tblastn进行搜索。进行这么一次搜索的目的是
生物信息学 第七章：序列比对和数据库搜索
