基于外存后缀树的top-k局部比对算法  

Top-k Local Alignment Algorithm Over External Suffix Tree

作　　者：王斌[1] 朱睿[1] 杨晓春[1] 王国仁[1] 于戈[1] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110004

出　　处：《计算机学报》2016年第10期2061-2074,共14页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目基金(2012CB316201);国家自然科学基金(61572122;61173031;61129002;61532021;U1401256);国家优秀青年科学基金(61322208)资助~~

摘　　要：局部比对是一种衡量字符串间相似程度的技术,它在生物信息学领域具有十分重要的作用.介于此,许多学者已对其进行了深入的研究.然而,随着数据规模的扩大,常规的内存算法已不适用于支持大规模文本数据的局部比对.为解决上述问题,该文研究了基于外存后缀树的top-k局部比对算法.它从根本上消除了内存空间对算法的束缚.为了提高算法的性能,该文首先将经典内存算法中的过滤策略引入该文.通过适当的修改,这些策略可以基于外存后缀树有效地降低计算开销.其次,该文提出一种巧妙的算法支持top-k局部比对查询.该算法通过引入启发式策略有效规避了TA算法的固有问题.具体地,它一方面可以提高算法的过滤能力,另一方面可以降低候选对象的维护代价.再次,该文对外存后缀树和磁盘的工作原理进行了研究.基于此,该文提出一种槽的结构支持查询.该结构既可以实现磁盘的顺序访问,又可以降低磁盘的访问次数.因此,它可以有效提高算法的查询效率.最后,大量的实验验证了该文所提出算法的有效性.Local alignment is a common technique for finding a pair of highly similar substrings from two given sequences, which is very important in the biological information field. With the enlargement of data scale, the state of arts memory-based algorithms are not suitable for answering local alignment when handling long text data. In this paper, we study the problem of local alignment top-k query over external suffix tree. It could break the bottleneck limited by the memory space. In order to avoid unnecessary computing cost, we firstly employ a series of filtering strategies based on the classic memory-based algorithms. Via property amending them, these algorithms could effectively enhance the performance of our solution. We then propose a novel algorithm for answering top-k query local alignment over external suffix tree. It empolies the heuristic strategy for avoiding the defect of TA-algorithm. For one thing, it could provide a powerful threshold for filtering. For another, it could efficiently reduce the candidates maintainance cost. Then, we deeply study the operational principle of external suffix tree and disk. As the basis, we propose several techniques for optimizing external memory accessing. The results of the experiments on the real genetic data demonstrate the effectiveness of our algorithms.

关 键 词：局部比对 TOP-K 外存后缀树 叉子区域 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]