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

A Novel Similarity Verification Algorithm Under Edit Distance Limitation

作　　者：于长永 李淼淼 赵楚 马海涛 YU Chang-yong;LI Miao-miao;ZHAO Chu;MA Hai-tao(School of Computer&Communication Engineering,Northeastern University at Qinhuangdao,Qinhuangdao 066004,China)

机构地区：[1]东北大学秦皇岛分校计算机与通信工程学院

出　　处：《东北大学学报（自然科学版）》2019年第11期1543-1548,共6页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金资助项目(61772124,61401080,61402087);河北省自然科学基金资助项目(F2015501049);河北省教育厅项目(QN2014339);中央高校基本科研业务费专项资金资助项目(N150402002)

摘　　要：针对相似性确认步骤中编辑距离计算的高复杂性问题,提出了一种在编辑距离限制下的基于鸽笼原理的字符串相似性确认算法.首先找到满足编辑距离片段映射的片段,以此片段为基准,将长度为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.

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

分 类 号：TP311.131[自动化与计算机技术—计算机软件与理论]