基于参考集索引的高效序列相似性查找算法

• 作者: 戴东波 朱扬勇 熊赟
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 序列相似性查找 参考集索引 编辑距离
• 年，卷（期）: 2010,（4）
• 所属期刊栏目: 数据库技术
• 页码范围: 718-731
• 页数: 14页
• 分类号: TP311
• 字数: 15134字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2010.03610

摘要

序列数据在文本、Web访问日志文件、生物数据库中普遍存在,对其进行相似性查找是一种重要的获取和分析知识的手段.基于参考集索引技术是一类解决序列相似性查找的有效方法,主要思想是找到序列数据库中的少数序列作为参考集,通过参考集过滤掉数据库中与查询序列不相关的数据,从而高效地回答查询.在现有基于参考集索引技术的基础上,提出一种过滤能力更强的序列相似性查询算法IRI(improved reference indexing).首先,充分利用了先前的查询结果集来加速当前的查询,其次考虑了基于序列特征的上界和下界,使得应用参考集进行过滤的上下界更紧,过滤能力进一步加强.最后,为了避免候选集中费时的编辑距离计算,则只计算前缀序列间的编辑距离,从而进一步加速算法运行.实验采用真实的DNA序列和蛋白质序列数据,结果表明,算法IRI在查询性能上明显优于现有的基于参考集索引方法RI(reference indexing).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱扬勇	复旦大学计算机科学技术学院	91	3435	25.0	58.0
2	熊赟	复旦大学计算机科学技术学院	26	277	7.0	16.0
3	戴东波	复旦大学计算机科学技术学院	6	156	5.0	6.0