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