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

来源期刊：东北大学学报(自然科学版)2019年第11期

论文作者：于长永 李淼淼 赵楚 马海涛

文章页码：1543 - 1548

关键词：读取映射;编辑距离;相似性查询;鸽笼原理;确认算法;

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