基于MapReduce的模体发现问题算法研究

摘要

模体发现问题是生物信息学中的核心问题之一，它对于研究基因表达的调控机制有着极为重要的生物学意义。植入(l,d)模体发现问题是其中一种非常重要的模型，但这一问题是NP难解的，要解决该问题往往要涉及巨大的计算量，因此，利用并行化的方式对问题进行求解就成为一个十分有效的选择。
　　本文将MapReduce并行编程模型引入模体发现问题领域，用于解决该问题中计算复杂度高的难题。MapReduce模型使得用户可以更加专注于求解的问题本身，它将用户的问题分解为两个模块Map和Reduce，而问题的并行化计算、任务调度、节点通信等问题都由部署在大规模集群上的系统来完成。
　　在充分分析植入(l,d)模体发现问题的基础上，本文结合MapReduce编程模型的特点，设计出了一种十分有效的并行算法—PMSPMR算法。在设计PMSPMR算法时必须要考虑数据的划分，不同的数据划分方法，对于算法的实现有着较大影响，本文中对各种可能的算法设计方法进行了详细描述，经过充分的分析，设计出了PMSPMR算法，并对其实现过程进行描述。然后在Hadoop分布式计算平台上对PMSPMR算法进行了实现和分析。经测试表明，PMSPMR算法针对不同难度的问题，在具有不同节点数目的Hadoop集群上运行都取得了很好的效果。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 模体发现问题研究背景及意义

1.2 并行编程模型

1.3 本文研究内容和组织结构

第二章 模体发现问题

2.1 模体发现问题介绍

2.2 模体发现问题研究现状

第三章 MapReduce 分布式并行编程模型

3.1 并行算法的概念和度量

3.2 并行算法的设计

3.3 并行计算编程模型

3.4 MapReduce编程模型

第四章 PMSPMR 算法的设计与实现

4.1 PMSP算法

4.2 PMSPMR算法

第五章 Hadoop 集群上实验结果分析

5.1 Hadoop实验集群的搭建

5.2 Hadoop集群上的实验结果与分析

第六章 结论和展望

致谢

参考文献