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

doi:10.12068/j.issn.1005-3026.2019.11.005

东北大学学报:自然科学版 ›› 2019, Vol. 40 ›› Issue (11): 1543-1548.DOI: 10.12068/j.issn.1005-3026.2019.11.005

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

于长永，李淼淼，赵楚，马海涛

(东北大学秦皇岛分校计算机与通信工程学院，河北秦皇岛066004)

收稿日期:2019-03-13 修回日期:2019-03-13 出版日期:2019-11-15 发布日期:2019-11-05
通讯作者: 于长永
作者简介:于长永(1981-)，男，辽宁海城人，东北大学副教授.
基金资助:
国家自然科学基金资助项目(61772124，61401080，61402087); 河北省自然科学基金资助项目(F2015501049); 河北省教育厅项目 (QN2014339); 中央高校基本科研业务费专项资金资助项目(N150402002).

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.

Received:2019-03-13 Revised:2019-03-13 Online:2019-11-15 Published:2019-11-05
Contact: LI Miao-miao
About author:-
Supported by:
-

摘要/Abstract

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

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

Abstract: 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 500bp 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.

Key words: read mapping, edit distance, similarity search, pigonhole principle, verification algorithm

中图分类号:

TP311.131

于长永，李淼淼，赵楚，马海涛. 一种新颖的编辑距离限制下的相似性确认算法[J]. 东北大学学报:自然科学版, 2019, 40(11): 1543-1548.

YU Chang-yong， LI Miao-miao， ZHAO Chu， MA Hai-tao. A Novel Similarity Verification Algorithm Under Edit Distance Limitation[J]. Journal of Northeastern University Natural Science, 2019, 40(11): 1543-1548.

参考文献

[1]Deng D，Li G L，Feng J H，et al.Top-k string similarity search with edit-distance constraints［C］// IEEE 29th International Conference on Data Engineering(ICDE).Washington D C，2013:925-936.
[2]Zhang Z J，Hadjieleftheriou M，Ooi B C，et al.Bed-tree;an all-purpose index structure for string similarity search based on edit distance［C］// Proceedings of the ACM SIGMOD International Conference on Management of Data.Indianapolis，2010:915-926.
[3]Deng D，Li G L，Feng J H.A pivotal prefix based filtering algorithm for string similarity search［C］// SIGMOD Conference.Snowbird，2014:673-684.
[4]Hadjieleftheriou M，Koudas N，Srivastava D.Incremental maintenance of length normalized indexes for approximate string matching［C］// SIGMOD Conference.Rhode Island，2009:429-440.
[5]Li，C，Lu J H，Lu Y M，et al.Efficient merging and filtering algorithms for approximate string searches［J］.International Conference on Data Engineering，2008，7(12):257-266.
[6]Wandelt S，Wang J，Leser U，et al.State-of-the-art in string similarity search and join［J］.ACM Sigmod Record，2014，43(1):64-76.
[7]Jiang Y，Li G，Feng J，et al.String similarity joins:an experimental evaluation［J］.International Conference on Very Large Data Bases，2014，7(8):625-636.
[8]Xiao C，Wang W，Lin X M，et al.Efficient similarity joins for near-duplicate detection［J］.ACM Transaction，2011，36(3):131-140.
[9]Jiang Y，Deng D，Wang J N，et al.Efficient parallel partition-based algorithms for similarity search and join with edit distance constraints［C］//EDBT/ICDT.New York，2013:341-348.
[10]Bi F，Chang L，Zhang W，et al.Efficient string similarity search:a cross pivotal based approach［C］// International Conference on Database Systems for Advanced Applications.Hanoi，2015:545-564.
[11]Levenstein V.Binary codes capable of correcting spurious insertions and deletions of ones［J］.Problems of Information Transmission，1965，1(1):8-17.
[12]Yu M，Wang J，Li G L，et al.A unified framework for string similarity search with edit-distance constraint［J］.International Conference on Very Large Data Bases Journal，2017，26(2):249-274.
[13]米琳.基于q-gram的字符串相似性查询研究［J］.现代计算机(专业版)，2014(6):12-16.(Mi Lin.Research on string similarity query based on q-gram［J］.Modern Computer(Professional Edition)，2014(6):12-16.)
[14]Mishra S，Gandhi T，Arora A，et al.Efficient edit distance based string similarity search using deletion neighborhoods［C］//EDBT/ICDT.New York，2013:375-383.
[15]Rheinlnder A，Knobloch M，HochmuthN，et al.Prefix tree indexing for similarity search and similarity joins on genomic data［C］//International Conference on Scientific and Statistical Database Management.Berlin，2010:519-536.
[16]Xin H，Greth J，Emmons J，et al.Shifted hamming distance:a fast and accurate SIMD-friendly filter to accelerate alignment verification in read mapping［J］.Bioinformatics，2015，31(10):1553-1560.(上接第1542页)
[3]Zink M D，Brüser C，Winnersbach P，et al.Heartbeat cycle length detection by a ballistocardiographic sensor in atrial fibrillation and sinus rhythm［J］.Biomed Research International，2015(19):1-10.
[4]Etemadi M，Inan O T.Wearable ballistocardiogram and seismocardiogram systems for health and performance［J］. Journal of Applied Physiology，2017，124(612):452-461.
[5]Lim Y G，Hong K H，Kim K K，et al.Monitoring physiological signals using nonintrusive sensors installed in daily life equipment［J］.Biomedical Engineering Letters，2011，1(1):11-20.
[6]Bruser C，Diesel J，Zink M D H，et al.Automatic detection of atrial fibrillation in cardiac vibration signals［J］. IEEE Journal of Biomedical and Health Informatics，2013，17(1):162-171.
[7]Acharya U R，Fujita H，Lih O S，et al.Automated detection of arrhythmias using different intervals of tachycardia ECG segments with convolutional neural network［J］. Information Sciences，2017，405:81-90.
[8]金晶晶，王旭，杨丹.基于体震信号的心率测量方法［J］.东北大学学报(自然科学版)，2009，30(2):176-179.(Jin Jing-jing，Wang Xu，Yang Dan.Heart rate measurement based on fluttering signal from human body［J］.Journal of Northeastern University(Natural Science)，2009，30(2):176-179.)
[9]Fan X，Yao Q，Cai Y，et al.Multi-scaled fusion of deep convolutional neural networks for screening atrial fibrillation from single lead short ECG recordings［J］.IEEE Journal of Biomedical and Health Informatics，2018，22(6):1744-1753.
[10]Lecun Y L，Bottou L，Bengio Y，et al.Gradient-based learning applied to document recognition［J］.Proceedings of the IEEE，1998，86(11):2278-2324.
[11]Golkov V，Dosovitskiy A，Sperl J I，et al.Q-Space deep learning:twelve-fold shorter and model-free diffusion MRI scans［J］. IEEE Transactions on Medical Imaging，2016，35(5):1344-1351.
[12]Van Grinsven M，van Ginneken B，Hoyng C，et al.Fast convolutional neural network training using selective data sampling:application to hemorrhage detection in color fundus images［J］.IEEE Transactions on Medical Imaging，2016，35(5):1273-1284.
[13]Kiranyaz S，Ince T，Gabbouj M.Real-time patient-specific ECG classification by 1D convolutional neural networks［J］.IEEE Transactions on Bio-medical Engineering，2015，63(3):664-675.

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

A Novel Similarity Verification Algorithm Under Edit Distance Limitation

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

本文评价

[1]	马海涛，祁实，于长永，赵宇海. 基于频率的Read Mapping种子选择算法[J]. 东北大学学报:自然科学版, 2019, 40(5): 609-613.
[2]	王少鹏，闻英友，赵宏. 滑动窗口下数据流完全加权最大频繁项集挖掘[J]. 东北大学学报:自然科学版, 2016, 37(7): 931-936.
[3]	周项敏;赵相国;王国仁. 通过精练查询空间改善高维数据的相似性查询[J]. 东北大学学报(自然科学版), 2005, 26(9): 856-859.
[4]	张怠杰;张跃;姚天顺. 面向数据的英汉机译系统中关于组合基于实例的技术[J]. 东北大学学报(自然科学版), 1999, 20(3): 4--.