网格化MRRF距离矩阵并行生物进化树算法  

MRRF:The Grid MapReduce-Robinson-Foulds Distance Matrix Based Parallel Evolutionary Trees Algorithm

作　　者：李春青[1] 李海生[1] 梁婷婷[1] 赵凯[2] 

机构地区：[1]广西民族师范学院,广西崇左532200 [2]平顶山学院,河南平顶山467000

出　　处：《西南师范大学学报（自然科学版）》2016年第2期85-91,共7页Journal of Southwest China Normal University(Natural Science Edition)

基　　金：2014年度广西高校科学技术研究项目(YB2014417);2014年度河南省科技计划项目(142102210225)

摘　　要：针对传统生物进化树执行效率不高的问题,提出一种网格化MapReduce-Robinson-Foulds(MRRF)距离矩阵并行生物进化树算法.首先,基于HashRF算法基本思想,设计实现了生物进化树MapReduce模型的网格化构建,以及网格参数计算;其次,利用两阶段MapReduce过程分别获得Robinson-Foulds距离子矩阵和联合后的距离总矩阵,实现了进化树在MapReduce架构下的Robinson-Foulds矩阵表示.最后,通过与Hash和HashRF算法进行对比,显示MRRF算法在运行时间和算法加速比上均要优于对比算法,并通过仿真对网格计算节点在不同核心数情况下对算法的影响进行了实验研究.According to the problem of low efficiency in traditional evolutionary trees,a kind of grid MapReduce-Robinson-Foulds distance matrix based parallel evolutionary trees algorithm.Firstly,based on the design idea of the HashRF algorithm,the grid MapReduce model of evolutionary trees has beenconstructed,and the grid parameters been computed.Secondly,the two stage MapReduce process have been used to obtain the Robinson-Foulds distance submatrix and the joint total matrix,which hasrealized the evolutionary trees representation in the form of the Robinson-Foulds matrix under the MapReduce framework.Finally,by comparing with Hash and HashRF algorithm,the algorithm in this paper is running fasterwith better speedup,and then the effectness of different cores for the algorithm has beenstudied through simulation.

关 键 词：Robinson-Foulds距离 生物进化树 MAPREDUCE 网格化 并行计算 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]