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

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