资源描述：
《基于MapReduce的模体发现问题算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、摘要模体发现问题是生物信息学中的核心问题之一，它对于研究基因表达的调控机制有着极为重要的生物学意义。植入(l,d)模体发现问题是其中一种非常重要的模型，但这一问题是NP难解的，要解决该问题往往要涉及巨大的计算量，因此，利用并行化的方式对问题进行求解就成为一个十分有效的选择。本文将MapReduce并行编程模型引入模体发现问题领域，用于解决该问题中计算复杂度高的难题。MapReduce模型使得用户可以更加专注于求解的问题本身，它将用户的问题分解为两个模块Map和Reduce，而问题的并行化计算、任务调度、节点通信等问题都由部署在大规模集群上的系统来完成。在充分分析植入(l,d)模体发现
2、问题的基础上，本文结合MapReduce编程模型的特点，设计出了一种十分有效的并行算法—PMSPMR算法。在设计PMSPMR算法时必须要考虑数据的划分，不同的数据划分方法，对于算法的实现有着较大影响，本文中对各种可能的算法设计方法进行了详细描述，经过充分的分析，设计出了PMSPMR算法，并对其实现过程进行描述。然后在Hadoop分布式计算平台上对PMSPMR算法进行了实现和分析。经测试表明，PMSPMR算法针对不同难度的问题，在具有不同节点数目的Hadoop集群上运行都取得了很好的效果。关键词：模体发现并行计算MapReduceHadoopPMSPMRAbstractMotifdis
3、coveryisoneofthecoreproblemsinBioinformatics,whichfortheresearchofthegeneexpressionregulationmechanismhasaveryimportantsignificance.Implanted(l,d)motifdiscoveryisaclassicmodel,buttheproblemhasbeenprovedtobeNPhard.Motifdiscoveryinvolvesahugeamountofcomputation,so,parallelcomputingisagoodchoice.I
4、nthispaperweintroducedMapReduceparallelcomputingmodelintomotifdiscoverytosolvetheproblemofhighComputationalComplexityinmotifdiscovery.MapReducemodelallowstheusertofocusmoreontheproblemwhichneedstosolve,itdecomposestheproblemintotwomodulesMapandReduce,andthesystemautomaticallyparallelizesthecomp
5、utation,schedulestasksandnodescommunicationacrosslarge-scaleclustersofmachines.Onthebasisoffullanalyzingtheimplanted(l,d)motifdiscoveryproblem,andcombiningwithMapReducemodel’scharacteristics,inthispaper,wedesignedaneffectiveparallelingalgorithm--PMSPMRalgorithm.Inordertodesignalgorithm,wemustco
6、nsiderthedatapartitioning,Differentdatapartitionmethodshasgreatinfluencefortheimplementationofthealgorithm.Inthispaper,wedescribedseveralkindsofdesignmethodsindetail,Afterafullanalysisandcomparison,wedesignedandimplementedPMSPMRalgorithmonHadoopdistributedcomputingplatform.Forinstancesoftheprob
7、lemwithdifferentcomputationaldifficulty,theexperimentalresultsonHadoopclustersdemonstratethatPMSPMRhasgoodscalability.Keywords:MotifdiscoveryparallelcomputingMapReduceHadoopPMSPMR目录第一章绪论............................................
