|
4.6 数据库搜索
生物信息数据库查询和搜索是生物学研究人员经常做的工作，它已经成为现代生物学研究的一个组成部分。当一个研究人员通过实验得到一条序列时，他首先希望知道这样的序列是否已经被收录到数据库中；进一步，还希望知道数据库中是否有关于该序列的注释，是否能够在数据库中找到同源序列，如果能够得到这些信息，将有助于他的研究工作。由于分子生物学技术的飞速发展，实验测定的生物分子数据不断增长，导致各种数据库中的数据量非常大。为了有效地利用各种数据，使用户能够迅速得到想要的信息，需要高效的算法搜索数据库。有两种数据库搜索方式，一种是基于正文的查询，即根据关键字、标识符、数据特性进行查询，将查询条件以正文的形式提交给查询系统。另一种是基于序列的搜索，用户给定一个查询序列，要求与数据库中所有的序列进行比较，以获得相似序列或者同源序列。后一种形式搜索的计算量非常大，对于一个给定的序列，要进行成千上万次的序列比较。第3章介绍的序列两两比较动态规划算法时间复杂度为O(n2)，这对于搜索大型数据库来说，算法执行时间太长。由于被搜索序列很长，而且数量巨大，用简单而直接的方法将数据库中每条序列与查询序列进行比对并返回比对得分最高的序列难以奏效。解决问题的一种方法是以硬件完成动态规划算法，或者使用并行计算机。虽然这可以使计算速度得到提高，但是硬件设备代价高，一般的研究人员不可能购置专用的硬件。提高计算速度的另一种方法是设计更快的算法。一般地说，这类算法是基于启发式的方法。对于一个具体的问题，启发式方法往往给出的是一个近似解，但是其计算速度要比精确算法快得多。对于启发式方法，难以准确地估计其计算时间和计算空间。就序列数据库搜索而言，启发式方法虽然不能保证其搜索结果是最佳的，但是一般能返回大部分与查询序列比对得较好的序列。目前，这类算法已成为生物分子数据库搜索的主要工具。在本节中，我们将介绍两个最流行的序列数据库快速搜索程序的算法思想，这两个程序就是FastA和BLAST。相对而言，FastA更适合于蛋白质数据库的搜索，而BLAST则更适合于核酸序列的搜索。此外，还要介绍结构搜索程序VAST。
4.6.1 FastA
FastA程序是第一个被生物学研究人员广泛使用的数据库相似性搜索程序。FastA本身是一种关于序列比较的启发式算法，用于序列数据库搜索，该算法由Lipman 和Pearson首先提出。为了达到较高的搜索敏感程度，程序采用打分矩阵实行局部比对，以获得最佳搜索结果，而为了提高搜索速度，在进行最佳搜索之前，算法使用已知的字串检索出可能的匹配。FastA家族中第一个实用程序是FASTP，该程序用于搜索蛋白质序列数据库，寻找相似序列。FASTP的基本算法是顺序将数据库中的每一个序列与查询序列比较，返回与查询序列非常相似的数据库序列，并附加序列的比对及其它相关信息。下面着重介绍FASTP的基本步骤。设s和t是两条待比较的蛋白质序列，其长度分别为m和n。首先确定两个序列的共同k元组（即连续的k个字符，k-tup），对于蛋白质序列，k=1或2。算法搜索速度和敏感度由参数k控制，k决定了字串的大小。增大k参数就会减少字串命中的数目，也就会减少所需要的最佳搜索的数目，提高搜索速度。另外，在FASTP中还有一个重要的变量，即相对位移，其值介于-n+1和m-1之间。位移决定一条序列相对于另一条序列发生字符替换的位置。如果共同的k元组起始于s[i]和t[j]，那么位移等于i-j。算法设置两个数据结构：（1）查找表；（2）位移向量，即以位移为下标的向量，向量中每个元素的初值全为0。扫描s，产生给定k元组所有位置的列表，见图4.9，其中k值为1。随后扫描t，对于其中的每一个k元组，在上述列表中进行查找，计算t的每一个k元组对应于s中同样k元组的位移。对于所有同时出现在两个序列中的k元组，将对应位移的向量分量加1。设s= FAMLGFIKYLPGCM，t= TGFIKYLPGACT，图4.6显示了经过处理以后查找表和位移向量的最终数据结果。注意，位移+3具有最大的发生数（8），这意味着在这个位移下匹配最多。由此我们可能得到两序列间的一个合理比对：
FAMLGFIKYLPGCM
||||||||
TGFIKYLPGACT
这种方法又称为对角线方法，因为一个位移可以看成是动态规划矩阵的一条对角线。对最大位移的一种可能的应用就是在对应的对角线附近进行动态规划计算。
|
s= |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
|
F |
A |
M |
L |
G |
F |
I |
K |
Y |
L |
P |
G |
C |
M |
|
查找表 |
|
A |
2 |
|
C |
13 |
|
F |
1,6 |
|
G |
5,12 |
|
I |
7 |
|
K |
8 |
|
L |
4,10 |
|
M |
3,14 |
|
P |
11 |
|
Y |
9 |
|
t= |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
T |
G |
F |
I |
K |
Y |
L |
P |
G |
A |
C |
T |
|
|
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
|
|
|
3
10 |
-2
3 |
3 |
3 |
3 |
-3
3 |
3 |
-4
3 |
-8 |
2 |
|
|
位 移 向 量 |
|
-10 |
-9 |
-8 |
-7 |
-6 |
-5 |
-4 |
-3 |
-2 |
-1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
8 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
图4.9 FASTP的查找表和位移向量
FASTP对共同k元组进行更深入的分析，并将在同一位移下距离较近的多个k元组联合起来，其联合准则是经验性的。这些被联合的k元组形成区域。一个区域可被看成是一个片段对，或无空白的局部对比排列，根据匹配或失配对区域进行打分。
FASTP对前一步产生的5个最好区域按PAM矩阵进行重新打分，最高的得分就是序列s和序列t相似性的初始得分。对于数据库中的每一个序列，均按上述方法计算与查询序列比较的初始得分。根据初始得分，将所有数据库序列按非递增顺序排序，对于排在前面的几个具有最高初始得分的序列，利用动态规划算法计算它们与查询序列最优对比排列的得分。然而，因为这是对相似序列的已知区域进行比对，计算过程仅限于初始对比排列（对应于初始得分的对比排列）附近区域。所以，比起完全使用动态规划算法来进行查询序列与所有可能目标序列间的比对，FASTP 要快得多。在一般情况下，如果两个序列是相关的，则最优得分高于初始得分。
k值的选取影响算法的性能，影响算法的敏感性和特异性。所谓敏感性是指识别相关序列的能力，而特异性则是指去掉假阳性（不相关序列的错配）的能力。在一般情况下，敏感性和特异性是两个矛盾的对立面，难以同时兼顾两个方面。在FASTP或其它FASTA家族程序中，小的k值增加敏感性，而大的k值加强特异性。FASTN是与FASTP类似的一个程序，用于搜索核酸数据库。
改进程序FASTP，形成一个性能更好的程序FastA。FastA的一个特点是既可以处理蛋白质序列，也可以处理DNA序列。FastA另一个不同之处是对初始得分的计算。在选择了最佳区域以后，将相邻区域联合起来，即使这些区域不属于同一条对角线。对于相似的序列对，经过这样处理后，其初始得分大大提高，接近于最优得分。另外，FastA取前10个最好区域进行优化计算。
FastA的基本思想于前面介绍的FASTP算法相似，在进行序列比较时，首先寻找两个序列中相同的短序列片段，关注相同的区域，在此基础上进行序列比对。FastA的算法步骤如下：
（1） 确定两个序列的共同k元组（即连续的k个字符），对于蛋白质序列，k=1或2，而对于DNA序列，则k=4~6。两个序列中完全相同的k元组被称为热点，将连续的热点定位在动态规划矩阵的对角线上。利用查找表或者哈稀表（Hash table）存放一条序列的所有k元组，并用另一条序列的k元组对表进行搜索。
（2） 在动态规划矩阵中寻找10条最佳的热点对角游程（diagonal run），每条对角游程是处于同一条对角线上的一系列相邻的热点。一条游程不一定要包含相应对角线上的所有热点，一条对角线可能有多个游程。为了评价对角游程，FastA为每个热点赋予一个正的得分，而对相邻热点间的空白位置给出一个负分，并且其分值随距离的增大而减小。对角游程的得分等于所有热点得分和空白位置得分的总和。
（3） 一条对角游程实际上对应于一对已经比对好的子序列，该比对由匹配（热点）和失配（空白区域）组成，但是不包括任何插入或删除，因为该比对是根据动态规划矩阵的一条对角线而得到的。利用蛋白质或核酸的替换矩阵评价对角游程，取得分最高的游程。令这一步找到的最佳子比对（subalignment）为init1。除了计算init1之外，还要进行筛选，过滤掉得分相对比较低的对角游程。
（4） 将相邻的高得分对角游程进行合并，形成新的序列比对。由于是不同对角线的组合，所以新的序列比对中一定存在字符的插入和删除。在实现时，以加权有向图作为数据结构，其中图的各个顶点代表前面已经找出的子序列比对，顶点的权值对应于序列比对的得分。对于图中的两个顶点u和v，如果v所代表的子序列比对的起始点所在的行和列均大于u所代表的子序列比对的终点所在的行和列，则在图中建立一条从u到v的有向边，并赋予该边一个负的权值，其绝对值的大小依赖于连接u和v所需要插入的空位数。FastA在这样的图中寻找一条总权值最大的路径，合并该路径上的所有子序列比对，作为最优的序列比对，并标记为initn。
（5） 进一步计算除initn之外的其它比对。考虑init1所对应的对角线，分析动态规划矩阵中以该对角线为中心的一个带状区域，init1中的两个子序列的最佳比对路径很可能就处于该带状区域内。假设确实如此，则利用动态规划算法在该带状区域内计算最佳的局部比对，或者通过合并该带状区域中的对角游程，找出最佳的局部比对。令这一步找出的最佳局部比对为opt。注意带宽的选择依赖于k元组的大小。
| 
常用在线数据库