MrsRF: an efficient MapReduce algorithm for analyzing large collections of evolutionary trees.
MrsRF: an efficient MapReduce algorithm for analyzing large collections of evolutionary trees.
复制标题
DOI：
10.1186/1471-2105-11-s1-s15
复制
发表时间：
2010-01-18
影响因子：
3
通讯作者：
Williams TL
中科院分区：
文献类型：
--
作者：
Matthews SJ;Williams TL
MapReduce是一种并行框架，已被有效地用于为大型计算集群设计大规模并行应用程序。在本文中，我们评估的可行性MapReduce框架设计系统发育的应用程序。感兴趣的问题是生成所有对所有的Robinson-Foulds距离矩阵，它在可视化和聚类大量进化树方面有许多应用。我们介绍了MrsRF（MapReduce Speeds up RF），这是一个多核算法，使用MapReduce范式在t棵树之间生成t × t Robinson-Foulds距离矩阵。我们研究了我们的MrsRF算法在两个大型生物树集上的性能，这两个生物树集分别由20，000棵150个分类群的树和33，306棵567个分类群的树组成。我们的实验表明，MrsRF是一种可扩展的方法，在32个核心上达到超过18的加速比。我们的研究结果还表明，在多核集群上实现最高加速比需要不同的集群配置。最后，我们展示了如何使用RF矩阵来直观地总结系统发育树的集合。我们的研究结果表明，MapReduce是一个很有前途的范例开发多核系统发育的应用程序。结果还表明，不同的多核配置必须进行测试，以获得最佳性能。我们的结论是，RF矩阵发挥了关键作用，在开发技术，总结大型集合的树木。
MapReduce is a parallel framework that has been used effectively to design large-scale parallel applications for large computing clusters. In this paper, we evaluate the viability of the MapReduce framework for designing phylogenetic applications. The problem of interest is generating the all-to-all Robinson-Foulds distance matrix, which has many applications for visualizing and clustering large collections of evolutionary trees. We introduce MrsRF (MapReduce Speeds up RF), a multi-core algorithm to generate a t × t Robinson-Foulds distance matrix between t trees using the MapReduce paradigm. We studied the performance of our MrsRF algorithm on two large biological trees sets consisting of 20,000 trees of 150 taxa each and 33,306 trees of 567 taxa each. Our experiments show that MrsRF is a scalable approach reaching a speedup of over 18 on 32 total cores. Our results also show that achieving top speedup on a multi-core cluster requires different cluster configurations. Finally, we show how to use an RF matrix to summarize collections of phylogenetic trees visually. Our results show that MapReduce is a promising paradigm for developing multi-core phylogenetic applications. The results also demonstrate that different multi-core configurations must be tested in order to obtain optimum performance. We conclude that RF matrices play a critical role in developing techniques to summarize large collections of trees.