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

摘要

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

目录

声明

摘要

第一章 绪论

1．1 课题研究背景

1．2 课题研究意义

1．3 研究现状

1．3．1 测序技术发展趋势

1．3．2 序列拼接中的关键难题

1．3．3 序列拼接技术的研究现状

1．4 研究的主要内容

1．5 论文组织结构

第二章 基于de Bruijn图的序列拼接技术分析

2．1 基于de Bruijn图的序列拼接原理

2．2 基于de Bruijn图的序列拼接技术分析

2．2．1 Velvet拼接技术

2．2．2 Soapdenovo拼接技术

2．2．3 Idba拼接技术

2．2．4 Abyss拼接技术

2．2．5 性能测试与分析

2．3 本章小结

第三章 双向de Bruijn图

3．1 双向de Bruijn图的数学描述

3．1．1 双向de Bruijn图的顶点

3．1．2 单步-双向边和单步-双向de Bruijn图

3．1．3 多步-双向边和多步-双向de Bruijn图

3．2 双向de Bruijn图的性质

3．3 本章小结

第四章 基于双向de Bruijn图的并行序列拼接的实现

4．1 并行编程相关技术

4．1．1 并行编程模型

4．1．2 MPI相关简介

4．2 序列拼接平台

4．3 模拟数据集生成

4．4 基于双向de Bruijn图的并行序列拼接技术的具体实现

4．4．1 并行序列拼接技术中功能子模块的划分

4．4．2 并行I／O存储模块的实现

4．4．3 单步-双向de Bruijn子图的构建

4．4．4 单步-双向de Bruijn图的分布式存储与构建

4．4．5 单步-双向de Bruijn图邻边融合的实现

4．5 本章小结

第五章 基于双向de Bruijn图的并行拼接技术测试与分析

5．1 测试数据集

5．2 并行计算的相关评价方法

5．3 基于双向deBruijn图的并行拼接技术的性能评测

5．3．1 并行I／O模块的性能测试

5．3．2 单步-双向de Bruijn图的构建性能测试

5．3．3 单步-双向de Bruijn图邻边融合性能测试

5．4 综合性能分析与测试

5．5 本章小结

第六章 总结与展望

6．1 工作总结

6．2 工作展望

参考文献

致谢

作者攻读硕士学位期间的主要研究成果