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

摘要

The field of computational biology encloses a wide range of optimization problems that show nondeterministicrnpolynomial-time hard complexities. Nowadays, phylogeneticians are dealing with a growingrnamount of biological data that must be analyzed to explain the origins of modern species. Evolutionaryrnrelationships among organisms are often described by means of tree-shaped structures known as phylogeneticrntrees. When inferring phylogenies, two main challenges must be addressed. First, the inference ofrnreliable evolutionary trees on data sets where different optimality principles support conflicting evolutionaryrnhypotheses. Second, the processing of enormous tree searches spaces where traditional sequential strategiesrncannot be applied. In this sense, phylogenetic inference can benefit from the combination of high performancerncomputing and evolutionary computation to carry out the reconstruction of complex evolutionaryrnhistories in reduced execution times. In this paper, we introduce multiobjective phylogenetics, a hybridrnOpenMP/MPI approach to parallelize a well-known multiobjective metaheuristic, the fast non-dominatedrnsorting genetic algorithm (NSGA-II). This algorithm has been designed to conduct phylogenetic analysesrnon multi-core clusters in accordance with two principles: maximum parsimony and maximum likelihood.rnThe main goal is to combine the benefits of shared-memory and distributed-memory programmingrnparadigms to efficiently infer a set of high-quality Pareto solutions. Experiments on six real nucleotide datarnsets and comparisons with other hybrid parallel approaches show that multiobjective phylogenetics is ablernto achieve significant performance in terms of parallel, multiobjective, and biological results.