基于块排序索引的生物序列局部比对查询技术*
时间：2021.03.04 | 腊八蒜怎么腌创作：欧阳地 |
| |
福建金线莲Block Sorting Index-bad Techniques for Local Alignment Searches on Biological Sequences
李永光王镝 王国仁 马宜菲
五年级上册数学教案(东北大学信息科学与工程学院计算机系统研究所 沈阳 110004)
Abstract A common query against large protein and gene quence data ts is to locate targets that are similar to an input query quence. The current t popular arch tools, such as BLAST, employs heuristics to improve the speed of such arches. However, such heuristics can sometimes miss targets, which in many cas is undesirable. The alternative to BLAST is to u an accurate algorithm, Such as Smith-Waterman(S-W) algorithm. However, the accurate algorithms are computationally very expensive. Recently, a new te
chnique, OASIS, has been propod to improve the efficiency and accuracy by employing dynamical programming during traversing suffix tree and its speed is comparable to BLAST. But its main drawback is too much memory consuming. We propo an efficient and accurate algorithm for locally aligning genome quences. We construct a block sorting index structure for the large quence. The index structure is less than the suffix tree index and can be fit for large data size. Experimental results show that our algorithm has better performance than OASIS.
Keywordsquence; block sorting index; accuracy
1. 引言
随着人类基因组计划的不断发展，在结构基因学和功能基因学的研究过程中，生物序列的相似性分析成为一种有效的手段[1]。通常情况下，两条DNA长序列，可能只在很小的区域内(密码区)存在关系；不同家族的蛋白质往往具有功能和结构上的相同的一些区域。因而，研究序列局部相似性比研究全序列相似性往往更有意义。
序列局部比对是一种关于片段相似性的定性描述[1]。通常的方法是通过动态规划[2]进行精确查找两个序列的最优局部比对，但因其代价太大，对超长生物序列直接应用这种技术是不可行的。为了提高查询速度，启发式算法当前被广泛应用，这些算法可以分为三类：基于哈希表的算法、基于频率空间过滤的算法、基于后缀树索引的算法。
基于哈希表的典型算法有FASTA[5]和BLAST[6]。FASTA的核心思想是对数据库序列中的所有模式进行哈希索引。在查询时基于哈希索引可以快速检索出可能的匹配模式。然后根据这些模式的扩展得到更长的序列。BLAST算法是建立在严格的统计学的基础之上，它主要用于发现具有较高的相似性的局部比对。在大多数情况下，根据局部比对参数会产生若干个HSP(High-score Sequence Pairs)。然后把所有匹配分值大于阈值的HSP作为结果。这种基于启发式算法的过滤原理尽管在一定程度上尽量减少丢失局部比对的结果，但精确率却不可能达到100%，一些符合条件的匹配序列可能不在查询结果中。
MRS[4]是基于频率空间过滤的代表方法，它采用滑动窗口和小波变换技术，设计了一种高效的生物序列搜索方法。根据频率距离是编辑距离的上界的过滤原理，可以节省大约50%的编辑距离计算。这种技术比较适合长的DNA序列，但不适合蛋白质序列的比对分析。
另外一些方法是基于后缀树技术的, 该类方法一般是通过对一条序列构建后缀树，然后利用后缀树快速查找到匹配的模式。对于后缀树中的某个分支，如果完全匹配的模式的个数超过给定阈值，那么就对该分支使用BLAST作进一步的查询。这类算法对阈值比较低的查询处理效率太低。OASIS[3]通过在遍历后缀树的同时运用动态规划算法，提供了一种精确的序列局部比对的搜索方法。其实验结果表明，它比动态规划算法快很多，而且可以和BLAST相提并论，但存储后缀树需要很大的存储空间，其构造过程也是复杂的。
本文首先提出了一种基于块排序索引算法来计算序列比对，我们引入基于这种索引结构的片断向量的概念，通过片断向量的扩展完成动态规划算法，从而完成序列比对查找过程。算法采用A*[8]搜索策略，进行过滤，当计算查询序列部分匹配时，搜索算法同时计算匹配剩余查询所得分值的上界，根据阈值，如果上界分值小于阈值，那么该片段向量就被过滤掉，从而减少搜索空间的计算。在搜索的每一步，算法首先扩展可能产生最优局部比对的片断向量，这就能保证返回的结果按照比对的分值由达到小排序。实验结果表明，我们的算法在性能和过滤能力上都优于OASIS。
本文的主要贡献在于通过运用较小的索引结构，我们提出一种精确有效的局部比对搜索算
法，因而这种算法为在大的生物数据集提供了一种可行有效的精确局部比对查找策略。
怎样查话费
本文余下部分的组织结构如下：第2部分给出了本文的背景知识；第3部分具体介绍了核心数据结构和算法；第4部分给出了测试结果和性能分析；第5部分总结全文。
2.背景知识
动态规划算法能精确计算生物序列全局和局部比对，在这一部分，我们首先介绍生物序列的局部比对的概念，然后讨论动态规划算法的相关工作，最后介绍块排序索引结构。
2. 1 序列局部比对
给定两条字符序列Q=q1q2…qm, T=t1t2…tn,这两条序列的局部比对是指通过某种方式是“排列”Q和T的子序列。图1给出一个局部比对例子，同时给出三种类型的局部比对操作。
●替换：用相同或者不同字符进行替换（如图1中的1和2标记）。
●删除：允许在目标序列中忽略一个字符（如图1中的3标记）。
●插入：允许在查询序列中忽略一个字符（如图1中的4标记）。
教案详案范文3 1 1 2 4 ●Target：…C A B I N … 1 Query：…D R A I N … |
图1. 局部比对的样例 |
|
物业保洁序列是通过三种操作所得到的分值之和来确定比对得分。每种操作可以形象描述为替换操
作“α→β”，其中插入操作表示为“—→β”,删除操作表示为“α→—”，操作的罚分可以标记为S（α→β）。可以通过替换矩阵S存储这些分值，所以“α→β”的操作代价可以简单表示为Sα,β。表1给出一个通用的替换矩阵的样例。称为单位编辑距离矩阵（因为完全匹配分值为1，否则为-1）。
| A | C | G | T | — |
A | 1 | -1 | -1 | -1 | -1 |
C | -1 | 1 | -1 | -1 | -1 |
G | -1 | -1 | 1 | -1 | -1 |
T | -1 | -1 | -1 | 1 | -1 |
— | -1 | -1 | aspects -1 | -1 | - |
| | | | | |
表1：单位编辑距离矩阵
2. 2 Smith-Waterman(S-W)算法
Smith-Waterman算法通过动态规划[2]的方法计算两条序列局部比对的最大的可能分值，计
算过程需要O(mn)空间和时间的复杂度。算法形成一个m×n的矩阵G，Gi,j保存查询序列和目标序列分别结束在qi和tj的最大比对分值。每一个Gi,j是通过下面的公式(1)计算出来的：
（1）
2. 3块排序索引结构
对于长度为n的序列S（我们的应用中，S以非序列中出现的字符作为结束字符，我们选用结束字符$，并规定$的字典序小于序列中的所有其它字符），进行块排序时对序列S循环移动0~n-1位，得到一个n行列表，将各行按升序排序，就得到了矩阵M，如图2所示，左侧是对序列AGTACGCCTAG$的块排序结果,这里我们不详细说明构造的过程，细节可看见[7]等文献。
图2：序列AGTACGCCTAG的块排序索引结构
下面我们描述基于块排序的索引结构。为了描述的方便我们将矩阵M的第一列称为F列，最后一列成为L列。F[i]和L[j]分别表示F列中的第i个字符和L列中的第j个字符。另外，我们引入函数count (F,i)在F列的前i个字符中，F[i]出现的次数。类似的，我们也定义count (L,j)。
铜锣寨
现在，我们给出在块排序结构中一个字符的后继字符的表达。对于一个字符F[i]，如果F[i]=L[j]并且count（F，i）=count（L，j），则F[j]是F[i]在给定序列中的后继字符。
块排序结构由F列和T列构成，T[i]是一个整数，它表示F[i]的后继字符在F列中的位置，即F[
T[i]]是F[i]在原序列中的后继字符。例如，图2给出序列AGTACCGCCTAG$的块排序结果。F[3]的后继字符是F[T[3]]，即F[5]。块排序索引就有如下的保序性：
