基于双向de Bruijn图的序列拼接并行化研究与实现

发布时间：2020-01-17 20:59

【摘要】：DNA序列拼接是生物信息学领域研究的重要课题。随着高通量、短序列测序科技的出现,测序覆盖度进一步提高,这给原有的序列拼接技术带来了严峻的挑战。高效的适用于大规模基因组的拼接技术成为处理DNA测序数据的关键。如何结合并行计算技术从而提高序列拼接处理速度成为本文研究的重要课题。 通过对已有的基于de Bruijn图的序列拼接技术的研究与分析,将序列拼接问题抽象为多步-双向de Bruijn图的结构(本文简称为双向deBruijn图),建立数学模型,并对其性质进行推导与论证。根据该图的性质,设计基于双向de Bruijn图结构的并行序列拼接方法,该方法通过融合半扩展单步-双向边得到全扩展多步-双向边集合,即DNA序列拼接过程中contig结构的集合,最终完成序列拼接。 通过对基于双向deBruijn图结构的并行序列拼接方法的每一个执行步骤的确切分析,将该方法划分为四大功能模块进行实现,主要包括：并行I/O模块的设计与实现、单步-双向de Bruijn子图的构建、单步-双向de Bruijn图的分布式存储与构建以及单步-双向de Bruijn图的邻边融合模块的设计与实现。其计算复杂度为O(n/p),通讯复杂度为O(n/p),单机节点的通讯量为O(nlog(n)/p),其中n为DNA序列read的数量,p为CPU个数。 实验测试表明,基于双向de Bruijn图的并行序列拼接有效提高了序列拼接的运算速度,降低了单机运行的内存消耗。在拼接数据量20G的C.elegans基因组时,其可从10个CPU扩展到640,加速比达到20倍,具有良好的可扩展性。
【学位授予单位】：中南大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：Q523;TP338.6

【参考文献】

相关期刊论文 前5条

1 张勇,张轶博,刘军,雷振明;基于取模运算哈希函数映射均衡性研究[J];重庆邮电学院学报(自然科学版);2004年02期

2 迟利华,刘杰,胡庆丰;数值并行计算可扩展性评价与测试[J];计算机研究与发展;2005年06期

3 郑纬民;林皎;罗水华;;DNA序列拼接中欧拉超路算法的新并行策略[J];计算机学报;2006年01期

4 谢桂园;魏文国;;并行文件系统的框架设计和性能研究[J];计算机工程;2009年11期

5 解增言;林俊华;谭军;舒坤贤;;DNA测序技术的发展历史与最新进展[J];生物技术通报;2010年08期

相关硕士学位论文 前2条

1 张博锋;全基因组DNA测序中的片段拼接方法及其并行处理[D];中国人民解放军国防科学技术大学;2002年

2 方小永;DNA序列拼接的分布式并行处理[D];国防科学技术大学;2003年

，

本文编号：2570753