A hybrid approach to parallelize a fast non-dominated sorting genetic algorithm for phylogenetic inference

作者：Santander Jimenez Sergio^*; Vega Rodriguez Miguel A

来源：Concurrency and Computation: Practice and Experience (CCPE) , 2015, 27(3): 702-734.

DOI：10.1002/cpe.3269

• parallel computing
• evolutionary computation
• multiobjective optimization
• bioinformatics
• phylogeny inference

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.

• 出版日期2015-3-10