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

崔竞松，薛 慧，王兰兰，郭 迟

1.空天信息安全与可信计算教育部重点实验室，武汉大学国家网络安全学院，湖北武汉 430072；

2.河海大学 理学院，江苏 南京 211100；

3.武汉大学卫星导航定位研究中心，湖北武汉430079

0 引言

DNA测序技术是指在给定的基因组中确定碱基序列排列方式，碱基序列包括腺嘌呤（A）、胸腺嘧啶（T）、胞嘧啶（C）与鸟嘌呤（G）。两条核苷酸序列配对构成DNA序列，其中每一对碱基A与T、G与C构成碱基对（base pair，bp）［1］。DNA测序技术是生物学家们了解DNA结构的重要技术手段。

目前的测序技术大致可以分为三代。第一代测序技术——传统的Sanger测序［2］，早在1977年被提出。该测序技术能够产生长度约为1 000的读段，且测序错误率极低，范围在0.001%～0.01%，但是Sanger测序成本高，速度慢，应用范围受到限制。因此，自2005年以来，大量的第二代测序技术被提出，第二代测序技术通常也被称为下一代测序技术［3］（next-generation sequencing，NGS）。与第一代Sanger测序相比，下一代测序技术成本较低，可以在较短的时间内对大量的DNA序列片段同时测序，而且其测序错误率也比较低，为0.5%～1.0%。但是，下一代测序技术产生的读段长度较短，一般仅包含75到300个碱基。因此，为了解决下一代测序技术存在的读段长度较短的问题，第三代测序技术被提出，主要包括Single Mplecule Real Time Sequencing［4］和Oxford Nanopore［5］。第 三代测序技术能够产生包含超过10 000个碱基的读段，但是测序错误率过高，在10%～15%，远远高于第一代测序技术和下一代测序技术。而且，第三代测序技术的测序成本也明显高于下一代测序技术。

由于下一代测序技术的低测序成本、低错误率和高通量等特性，目前该测序技术为市面上应用最为广泛的测序技术。……