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

摘要：

局部比对是一种衡量字符串间相似程度的技术，它在生物信息学领域具有十分重要的作用。介于此，许多学者已对其进行了深入的研究。然而，随着数据规模的扩大，常规的内存算法已不适用于支持大规模文本数据的局部比对。为解决上述问题，该文研究了基于外存后缀树的 top-k 局部比对算法。它从根本上消除了内存空间对算法的束缚。为了提高算法的性能，该文首先将经典内存算法中的过滤策略引入该文。通过适当的修改，这些策略可以基于外存后缀树有效地降低计算开销。其次，该文提出一种巧妙的算法支持 top-k 局部比对查询。该算法通过引入启发式策略有效规避了 TA 算法的固有问题。具体地，它一方面可以提高算法的过滤能力，另一方面可以降低候选对象的维护代价。再次，该文对外存后缀树和磁盘的工作原理进行了研究。基于此，该文提出一种槽的结构支持查询。该结构既可以实现磁盘的顺序访问，又可以降低磁盘的访问次数。因此，它可以有效提高算法的查询效率。最后，大量的实验验证了该文所提出算法的有效性。

关键词：局部比对、top-k、外存后缀树、叉子区域

所属期刊栏目：39

分类号：TP301(计算技术、计算机技术)

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

在线出版日期：2016-11-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：2061-2074