CGDNA:基于簇图的基因组序列集成拼接算法

基因组测序的目的是获取一个生物体完整的DNA序列信息,而DNA信息是进行遗传学研究和疾病诊断的基础。通常而言,完整的基因组测序分为两个步骤:第一步通过实验手段测定DNA序列片段,第二步通过计算方法把DNA片段拼接为完整的基因组。尽管桑格测序技术成功解析了包括人类在内的多个基因组,但其由于成本过高,目前逐渐被新一代测序技术所取代。新一代测序技术的特点为高通量、高覆盖率、低成本,随之而来的缺点体现为短读长、更多类型的错误。这些特点也给基因拼接算法带来了更大的挑战。鉴于目前的数十种基因拼接算法中并没有一种算法显著优于其它算法,且一些分析表明不同算法的拼接结果具有互补性,提出了CGDNA算法框架,它把不同算法的拼接结果整合到一起,使得整合的结果超越任何单个算法的结果。提出了一种基于簇图的基因组序列集成拼接算法,它通过构建索引、读长映射、重叠群聚簇、构建簇图等步骤将重叠群拼接成更长的序列。实验结果表明,相对于目前最优的算法Velvet、ABySS、SOAPdenovo,CGDNA在N50与最长拼接序列这两项指标上的增长比例高达50%以上,并且达到了较高的覆盖度。当更多的基本算法集成到本算法时,性能可进一步提高。提出的方法大幅提高了基因拼接的长度,为下一步的遗传分析降低了难度,并加快了生物基因组研究的步伐。

CGDNA:An Ensemble De Novo Genome Assembly Algorithm Based on Clustering Graph