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

A Novel Similarity Verification Algorithm Under Edit Distance Limitation

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

For the high complexity problem of edit distance calculation in the similarity confirmation step,a string similarity confirmation algorithm based on pigonhole principle under the limitation of edit distance is proposed.Firstly,it found a segment satisfies the edit distance segment mapping,then based on this segment,the read length of 500 bp was segmented.Then the edit distance of right and left parts was calculated and all parts sum to the final result.Finally,based on the longest common substring,the number of segments to be verified is minimized,and an optimization scheme was obtained.The experimental result show that this verification algorithm reduces the time of the verification step,and ensures the zero false positive and false negative rate.