LEDA:一种基于Levenshtein距离的DNA序列拼接算法

LEDA:A DNA Sequence Assembly Algorithm Based on Levenshtein Distance

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

A DNA sequence assembly algorithm based on Levenshtein distance is proposed for two sequences Read1 and Read2 generated by DNA paired-end sequencing in this paper.According to the edit distance between the end overlap of Read1 and Read2,all possible correct sequences are found and the sequences are assembled into a complete DNA sequence.The algorithm is innovative in applying Levenshtein distance to DNA sequence assembly problem which transforms a DNA sequence assembly problem into a string alignment problem that insertion,deletion and substitution operations may occur.The algorithm is simple,but it solves the problem of many restrictions when other assembly algorithms are used with the correct rate of stitching as high as 99%.Meanwhile compared with the time complexity of other assembly algorithms O(N^(2)),the time complexity of this algorithm is only O(n·2^(x)),where N is reads length,n is overlap length,and x is the minimum editing distance of the overlap between Read1 and Read2 ends.So this algorithm is well advanced technically.