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

• 作者: 于戈 朱睿 杨晓春 王国仁 王斌
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 局部比对 top-k 外存后缀树 叉子区域
• 年，卷（期）: 2016,（10）
• 所属期刊栏目: 数据科学与工程
• 页码范围: 2061-2074
• 页数: 14页
• 分类号: TP301
• 字数: 14694字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2016.02061

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王国仁	东北大学信息科学与工程学院	228	2804	25.0	45.0
2	于戈	东北大学信息科学与工程学院	426	6587	38.0	64.0
3	杨晓春	东北大学信息科学与工程学院	65	1090	16.0	32.0
4	王斌	东北大学信息科学与工程学院	101	945	14.0	28.0
5	朱睿	东北大学信息科学与工程学院	3	6	1.0	2.0