对基因组拼接算法的深入分析和探讨

2016-01-18 13:11:14张磊
电脑知识与技术 2015年33期

张磊

摘要:研究基因组拼接算法,进而更高效地实现全基因组拼接、获取生物体遗传信息,对于生命科学研究具有重要的意义。 拼接之前对数据进行一定的预处理。拼接采用经典的DBG算法,分析了DBG算法的实现步骤以及需要注意的问题。根据read切割K-mer,然后采用位运算压缩存入Hash表。以有效的K-mer为顶点,相邻的K-mer之间连有向边,建立DBG图,然后在该图中寻找Euler路径。每一条Euler路径对应一条contig。最后进行参数组合实验,并将结果与专业软件CLC的结果进行对比。两者效率相近,说明了算法的高效性。

关键词:拼接;DBG图;K-mer;contig;scaffold

中图分类号:Q812;TP311 文献标识码:A 文章编号:1009-3044(2015)33-0123-02

快速和准确地获取生物体的遗传信息对于生命科学研究具有重要的意义。对每个生物体来说,基因组包含了整个生物体的遗传信息,这些信息通常由组成基因组的DNA或RNA分子中碱基对的排列顺序所决定。获得目标生物基因组的序列信息,进而比较全面地揭示基因组的复杂性和多样性,成为生命科学领域的重要研究内容。

本文深入探讨了基因组拼接算法的实现细节,为实现基因组组装算法小平台化提供了参考。

测试数据:一个全长约为120000个碱基对的细菌人工染色体(BAC), 采用Hiseq2000测序仪进行测序,测序深度(sequencing depth)约为70×。

1 背景介绍

基因组组装是指以基因组测序所得的序列片段read数据为输入,利用序列片段之间的交叠关系,再加上配对数据、碱基质量等辅助信息,通过一定的方法手段重建目标基因组序列的过程。基于新一代测序数据的拼接算法,通常包括如下三个阶段:

登录APP查看全文