高效的分布式大规模基因组序列组装

摘要

在基因组序列组装算法中，一个最基本的问题就是如何合适的选择上下游的短序列用于组装成一个长序列。当单独从一个种子序列进行扩展的时候，大量的重复的区域将会导致非常多的扩展的候选，从而导致序列组装问题非常的复杂。目前通用的方法就是选择一个基于短序列（双端序列）之间的重叠信息然后进行组装的。然而当所组装的基因组序列是非常高重复的复杂数据的时候，这种方法将面临巨大的挑战，尤其是序列数据中还包含有错误、高重复的序列以及不均衡的测序深度导致基因组中某些区域只有少量的序列覆盖或者大量的序列覆盖。所有的这些原因导致了现在的组装程序得不到最完美的组装基因组数据。
　　本文提出了通过原始读长信息寻找基于多个无参考序列的拼接算法产生的重叠群之间的重叠信息，来进行再组装。算法通过首先将重叠群建立k-mer位置索引，然后进行读长映射、潜在重叠群聚类、可组装重叠群聚类等步骤进行搭支架。整个算法流程能高效率便捷的运行，将整个算法流程设计为基于Hadoop的分布式平台，并在多个部分使用MapReduce算法，且在较小的内存机器上就可以运行。在大肠杆菌的基因组数据集上运行结果表明，本文提出的算法在组装的多项指标上据表现出良好的性能，在N50指标上有将近46％的提高，整体的组装覆盖度更加接近参考序列，并且算法能在Hadoop平台上高效的运行。

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．1．1 基于生物大数据分布式平台的研究现状

1．1．2 大规模基因组组装的研究现状

1．2 研究内容、目的和意义

1．2．1 研究内容

1．2．2 研究目的和意义

1．3 本文贡献

1．4 本文结构安排

第二章 分布式计算和序列组装

2．1 分布式计算

2．1．1 分布式开源平台Hadoop

2．1．2 并行计算框架MapReduce

2．2 基因组测序技术与组装

2．2．1 基因测序技术

2．2．2 基因组拼接与组装

2．2．3 基因组序列de novo组装算法

2．3 布隆过滤器Bloom Filter

2．4 本章小结

第三章 基于MapReduce的组装算法

3．1 基本原理

3．2 数据预处理

3．3 k-mer位置索引

3．4 读长拆分与映射

3．5 可组装重叠群聚类

3．5．1 重叠群相似度

3．5．2 重叠群精确匹配

3．6 类内重叠群组装

3．7 本章小结

第四章 实验设计与结果分析

4．1 数据集和数据预处理

4．1．1 数据集准备

4．1．2 读长纠错

4．1．3 重叠群拼接

4．2 组装质量

4．3 组装可视化

4．4 本章小结

第五章 结论和展望

参考文献

发表论文和参加科研情况

致谢