A hybrid approach to parallelize a fast non-dominated sorting genetic algorithm for phylogenetic inference
A hybrid approach to parallelize a fast non-dominated sorting genetic algorithm for phylogenetic inference
复制标题
DOI：
10.1002/cpe.3269
复制
发表时间：
2015-03-10
影响因子：
2
通讯作者：
Vega-Rodriguez, Miguel A.
中科院分区：
文献类型：
--
作者：
Santander-Jimenez, Sergio;Vega-Rodriguez, Miguel A.
计算生物学领域包含了大量的优化问题，这些问题表现出非确定性多项式时间的硬复杂性。如今，系统发生学家正在处理越来越多的生物学数据，必须对这些数据进行分析才能解释现代物种的起源。生物体之间的进化关系通常通过称为系统发育树的树形结构来描述。在推断遗传学时，必须解决两个主要挑战。第一，可靠的进化树的推理数据集，不同的最优性原则支持相互冲突的进化假设。第二，处理巨大的树搜索空间，传统的顺序策略不能应用。从这个意义上说，系统发育推理可以受益于高性能计算和进化计算的结合，在减少的执行时间内进行复杂的进化历史的重建。在本文中，我们介绍了多目标遗传算法，一个混合的OpenMP/MPI方法并行化一个著名的多目标元启发式，快速非支配排序遗传算法（NSGA-II）。该算法根据两个原则：最大简约和最大似然，对多核簇进行系统发育分析。主要目标是联合收割机的好处共享内存和分布式内存编程范例，有效地推断出一组高质量的帕累托解决方案。六个真实的核苷酸数据集上的实验和与其他混合并行方法的比较表明，多目标遗传学能够在并行，多目标和生物结果方面取得显着的性能。版权所有（c）2014约翰威利父子有限公司
The field of computational biology encloses a wide range of optimization problems that show non-deterministic polynomial-time hard complexities. Nowadays, phylogeneticians are dealing with a growing amount of biological data that must be analyzed to explain the origins of modern species. Evolutionary relationships among organisms are often described by means of tree-shaped structures known as phylogenetic trees. When inferring phylogenies, two main challenges must be addressed. First, the inference of reliable evolutionary trees on data sets where different optimality principles support conflicting evolutionary hypotheses. Second, the processing of enormous tree searches spaces where traditional sequential strategies cannot be applied. In this sense, phylogenetic inference can benefit from the combination of high performance computing and evolutionary computation to carry out the reconstruction of complex evolutionary histories in reduced execution times. In this paper, we introduce multiobjective phylogenetics, a hybrid OpenMP/MPI approach to parallelize a well-known multiobjective metaheuristic, the fast non-dominated sorting genetic algorithm (NSGA-II). This algorithm has been designed to conduct phylogenetic analyses on multi-core clusters in accordance with two principles: maximum parsimony and maximum likelihood. The main goal is to combine the benefits of shared-memory and distributed-memory programming paradigms to efficiently infer a set of high-quality Pareto solutions. Experiments on six real nucleotide data sets and comparisons with other hybrid parallel approaches show that multiobjective phylogenetics is able to achieve significant performance in terms of parallel, multiobjective, and biological results. Copyright (c) 2014 John Wiley & Sons, Ltd.