典型文献
LEDA:一种基于Levenshtein距离的DNA序列拼接算法
文献摘要：
针对DNA双端测序产生的两条序列Read1和Read2,提出了一种基于Levenshtein距离的DNA序列拼接算法.根据Read1与Read2末端重叠部分的编辑距离,寻找所有可能正确的序列片段,拼接成完整的DNA序列.该算法将通常用于字符串比对的编辑距离运用到DNA序列的拼接问题中,将DNA序列拼接问题转换成为可能发生插入、删除以及替换操作的字符串比对问题,算法简单,解决了其他拼接算法使用时有诸多限制条件的问题.拼接正确率高达99％,相比于其他拼接算法O(N2)的时间复杂度,时间复杂度仅为O(n·2x),其中N为reads长度,n为overlap长度,x为Read1与Read2末端重叠部分的最小编辑距离,拼接高效,具有良好的技术优势.
文献关键词：
DNA测序技术;Levenshtein距离;拼接算法
中图分类号：
作者姓名：
崔竞松;薛慧;王兰兰;郭迟
作者机构：
空天信息安全与可信计算教育部重点实验室,武汉大学国家网络安全学院,湖北武汉430072;河海大学理学院,江苏南京211100;武汉大学卫星导航定位研究中心,湖北武汉430079
文献出处：
引用格式：
[1]崔竞松;薛慧;王兰兰;郭迟-.LEDA:一种基于Levenshtein距离的DNA序列拼接算法)[J].武汉大学学报（理学版）,2022(03):271-278
A类：
LEDA,Read1,Read2,最小编辑距离
B类：
Levenshtein,拼接算法,双端,字符串,问题转换,转换成,删除,除以,限制条件,N2,时间复杂度,2x,reads,overlap
AB值：
0.204082
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
