一种新颖的编辑距离限制下的相似性确认算法

• 作者: 于长永 李淼淼 赵楚 马海涛
• 来源期刊: 东北大学学报（自然科学版）
• 学科: 工学
• 关键词: 读取映射 编辑距离 相似性查询 鸽笼原理 确认算法
• 年，卷（期）: 2019,（11）
• 所属期刊栏目: 信息与控制
• 页码范围: 1543-1548
• 页数: 6页
• 分类号: TP311.131
• 字数: 5266字
• 语种: 中文
• DOI: 10.12068/j.issn.1005-3026.2019.11.005

摘要

针对相似性确认步骤中编辑距离计算的高复杂性问题,提出了一种在编辑距离限制下的基于鸽笼原理的字符串相似性确认算法.首先找到满足编辑距离片段映射的片段,以此片段为基准,将长度为500 bp的read分段.然后对满足编辑距离片段映射的左右部分递归地进行编辑距离计算,将各段得到的编辑距离相加即为最后结果.最后根据最长公共子串的下限将需要验证的片段数目降到最低,得到优化方案.实验结果表明,基于鸽笼原理的分段递归计算编辑距离的确认算法减少了验证步骤的时间,并能保证假阳率和假阴率都为零.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	于长永	东北大学秦皇岛分校计算机与通信工程学院	18	57	4.0	7.0
2	马海涛	东北大学秦皇岛分校计算机与通信工程学院	14	55	3.0	7.0
3	李淼淼	东北大学秦皇岛分校计算机与通信工程学院	1	0	0.0	0.0
4	赵楚	东北大学秦皇岛分校计算机与通信工程学院	1	0	0.0	0.0