科研之友
微信
新浪微博
Facebook
分享链接
摘要
针对DNA双端测序产生的两条序列Read1和Read2，提出了一种基于Levenshtein距离的DNA序列拼接算法。根据Read1与Read2末端重叠部分的编辑距离，寻找所有可能正确的序列片段，拼接成完整的DNA序列。该算法将通常用于字符串比对的编辑距离运用到DNA序列的拼接问题中，将DNA序列拼接问题转换成为可能发生插入、删除以及替换操作的字符串比对问题，算法简单，解决了其他拼接算法使用时有诸多限制条件的问题。拼接正确率高达99%，相比于其他拼接算法O(N2)的时间复杂度，时间复杂度仅为O(n·2x)，其中N为reads长度，n为overlap长度，x为Read1与Read2末端重叠部分的最小编辑距离，拼接高效，具有良好的技术优势。
- 单位
