PhyloMissForest: a random forest framework to construct phylogenetic trees with missing data.

BACKGROUND: In the pursuit of a better understanding of biodiversity, evolutionary biologists rely on the study of phylogenetic relationships to illustrate the course of evolution. The relationships among natural organisms, depicted in the shape of phylogenetic trees, not only help to understand evolutionary history but also have a wide range of additional applications in science. One of the most challenging problems that arise when building phylogenetic trees is the presence of missing biological data. More specifically, the possibility of inferring wrong phylogenetic trees increases proportionally to the amount of missing values in the input data. Although there are methods proposed to deal with this issue, their applicability and accuracy is often restricted by different constraints. RESULTS: We propose a framework, called PhyloMissForest, to impute missing entries in phylogenetic distance matrices and infer accurate evolutionary relationships. PhyloMissForest is built upon a random forest structure that infers the missing entries of the input data, based on the known parts of it. PhyloMissForest contributes with a robust and configurable framework that incorporates multiple search strategies and machine learning, complemented by phylogenetic techniques, to provide a more accurate inference of lost phylogenetic distances. We evaluate our framework by examining three real-world datasets, two DNA-based sequence alignments and one containing amino acid data, and two additional instances with simulated DNA data. Moreover, we follow a design of experiments methodology to define the hyperparameter values of our algorithm, which is a concise method, preferable in comparison to the well-known exhaustive parameters search. By varying the percentages of missing data from 5% to 60%, we generally outperform the state-of-the-art alternative imputation techniques in the tests conducted on real DNA data. In addition, significant improvements in execution time are observed for the amino acid instance. The results observed on simulated data also denote the attainment of improved imputations when dealing with large percentages of missing data. CONCLUSIONS: By merging multiple search strategies, machine learning, and phylogenetic techniques, PhyloMissForest provides a highly customizable and robust framework for phylogenetic missing data imputation, with significant topological accuracy and effective speedups over the state of the art.

Inter-Algorithm Multiobjective Cooperation for Phylogenetic Reconstruction on Amino Acid Data.

Inter-algorithm cooperative approaches are increasingly gaining interest as a way to boost the search capabilities of evolutionary algorithms (EAs). However, the growing complexity of real-world optimization problems demands new cooperative designs that implement performance-driven strategies to improve the solution quality. This article explores multiobjective cooperation to address an important problem in bioinformatics: the reconstruction of phylogenetic histories from amino acid data. The proposed method is built using representative algorithms from the three main multiobjective design trends: 1) nondominated sorting genetic algorithm II; 2) indicator-based evolutionary algorithm; and 3) multiobjective evolutionary algorithm based on decomposition. The cooperation is supervised by an Elite island component that, along with managing migrations, retrieves multitrend performance feedback from each approach to run additional instantiations of the most satisfying algorithm in each stage of the execution. Experimentation on five real-world problem instances shows the benefits of the proposal to handle complex optimization tasks, in comparison to stand-alone algorithms, standard island models, and other state-of-the-art methods.

Applying a multiobjective metaheuristic inspired by honey bees to phylogenetic inference.

The development of increasingly popular multiobjective metaheuristics has allowed bioinformaticians to deal with optimization problems in computational biology where multiple objective functions must be taken into account. One of the most relevant research topics that can benefit from these techniques is phylogenetic inference. Throughout the years, different researchers have proposed their own view about the reconstruction of ancestral evolutionary relationships among species. As a result, biologists often report different phylogenetic trees from a same dataset when considering distinct optimality principles. In this work, we detail a multiobjective swarm intelligence approach based on the novel Artificial Bee Colony algorithm for inferring phylogenies. The aim of this paper is to propose a complementary view of phylogenetics according to the maximum parsimony and maximum likelihood criteria, in order to generate a set of phylogenetic trees that represent a compromise between these principles. Experimental results on a variety of nucleotide data sets and statistical studies highlight the relevance of the proposal with regard to other multiobjective algorithms and state-of-the-art biological methods.