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