基因组序列物种聚类问题研究及DNA聚类的云计算实现

摘要

基因组学是研究生物基因组奥秘的新技术，随着测序技术在过去十几年间的高速发展，目前我们已经进入了千元人类基因组阶段，这极大推动了研究微生物信息和群落的功能的宏基因组学发展。同时基于下一代测序技术的宏基因组项目的发展，也产生了海量的生物序列，在对这些数据进行处理和分析中涌现出了大量的分析问题，亟需通过有效的计算手段进行解决。本文围绕着宏基因组序列物种聚类问题和DNA聚类问题进行了深入的研究，主要研究内容和贡献如下:
　　 1.宏基因组序列的物种聚类算法研究
　　 由于宏基因组测序序列中包含多个物种的DNA片段，对宏基因组序列分析需要首先对不同物种的DNA序列进行分离。目前基于无监督的宏基因组序列物种聚类算法主要有MetaCluster和TOSS。基于结构信息的MetaCluster3.0无法有效处理短序列，并且由于k-means算法随机生成中心点，多次运行面临产生的结果不一致的问题。而基于相似度信息进行物种聚类的算法TOSS，却面临着聚类速度较慢，无法处理大规模数据的问题。本文结合了相似度信息和结构信息，并引入了仿射聚类来对宏基因组测序序列物种聚类问题进行分析。实验数据表明我们的算法克服了MetaCluster3.0无法处理短序列的问题，并且运行时间比TOSS快10倍以上。
　　 2.DNA序列聚类算法的云计算实现
　　 下一代测序技术的迅速发展和宏基因组项目的进行均产生了大量的DNA序列，这加剧了当前序列聚类算法的处理能力与测序得到的大量的DNA序列之间的矛盾。目前已有针对DNA序列聚类的算法都是基于单机分析处理的，已经无法应对下一代测序技术产生的迅速增长的序列数据，因此我们基于开源Hadoop的MapReduce云计算框架，开发了基于云计算平台的DNA序列聚类工具。实验数据表明我们的聚类算法具有很强的可扩展性，并且运行效率较高。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．2 研究现状

1．2．1 宏基因组序列物种聚类问题

1．2．2 DNA序列聚类问题

1．3 本文工作

1．4 论文组织

第2章 相关技术与知识

2．1 基因与DNA

2．2 基因组学的相关概念

2．2．1 下一代测序技术

2．2．2 宏基因组学

2．3 云计算在生物信息学中的应用

2．4 本章小结

第3章 宏基因组序列物种聚类问题研究

3．1 问题定义

3．2 已有工作介绍

3．2．1 有参考的物种分类算法

3．2．2 AbundanceBin——基于EM的物种聚类算法

3．2．3 TOSS——基于MCL图聚类的物种聚类算法

3．2．4 MetaCluster——基于k-means的物种聚类算法

3．3 基于仿射聚类的物种聚类算法

3．3．1 研究思路

3．3．2 基于相似度初步聚类

3．3．3 基于仿射聚类的进一步聚类

3．3．4 实验结果及性能分析

3．4 本章小结

第4章 DNA序列聚类算法的云计算实现

4．1 问题描述

4．2 已有相关工作介绍

4．2．1 cd-hit——基于贪心比对的DNA聚类算法

4．2．2 uclust——基于快速搜索的DNA聚类算法

4．3 基于MapReduce的DNA聚类

4．3．1 研究思路

4．3．2 基于MapReduce的DNA聚类

4．3．3 实验结果及性能评价

4．4 本章小结

第5章 总结

5．1 本文工作

5．2 本文贡献与创新之处

5．3 进一步工作

参考文献

附录1 插图索引

附录2 表格索引

致谢

在读期间发表的学术论文

攻读学位期间参加的科研项目