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

作者：于长永; 李淼淼; 赵楚; 马海涛读取映射编辑距离相似性查询鸽笼原理确认算法

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

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社