Harnessing machine learning to guide phylogenetic-tree search algorithms

Abstract

Inferring a phylogenetic tree is a fundamental challenge in evolutionary studies. Current paradigms for phylogenetic tree reconstruction rely on performing costly likelihood optimizations. With the aim of making tree inference feasible for problems involving more than a handful of sequences, inference under the maximum-likelihood paradigm integrates heuristic approaches to evaluate only a subset of all potential trees. Consequently, existing methods suffer from the known tradeoff between accuracy and running time. In this proof-of-concept study, we train a machine-learning algorithm over an extensive cohort of empirical data to predict the neighboring trees that increase the likelihood, without actually computing their likelihood. This provides means to safely discard a large set of the search space, thus potentially accelerating heuristic tree searches without losing accuracy. Our analyses suggest that machine learning can guide tree-search methodologies towards the most promising candidate trees.

Fig. 1. The trees defined by an SPR move.

For each data sample, two trees and four subtrees were considered: a an example of a starting tree; b, c the two subtrees induced by the pruned branch of a tree a (in red), where b is the pruned subtree and c the remaining subtree; c1, c2 the regrafted branch (in blue) also induces two subtrees, from both sides of the regrafted branch of subtree c; d the resulting tree following the SPR move.

Fig. 2. Performance evaluation scores on empirical datasets.

A histogram of the three performance scores of the learning algorithm evaluated on: a the 4200 starting trees, using cross-validation; b the 1000 validation set starting trees. On the Y axis of both panels a and b are the percentages of empirical datasets in each accuracy score bin: (1) accuracy is computed as the Spearman correlation coefficient between the predicted ranking and the true ranking of neighboring trees; (2) accuracy is the rank (in percentile) of the empirically best neighbor within the predicted ranking; (3) accuracy is the rank (in percentile) of the predicted best neighbor within the empirical ranking.

Fig. 3. Example of an iterative chain of moves.

Evaluation metrics for the convergence behavior of an iterative chain of trees towards the maximum-likelihood tree. The chain was initiated with the Neighbor-Joining tree reconstructed for the protein-coding algae dataset we used as an example throughout the manuscript (iteration #0). The line plots represent the Robinson-Foulds distance from the maximum-likelihood tree (in blue; left Y axis), and the log-likelihood of the tree obtained in each iteration (in orange; right Y axis).

Fig. 4. Feature selection following a backward stepwise elimination procedure.

The mean Spearman correlation coefficient obtained when using a decreasing number of features for training the algorithm on the 4200 starting trees. The box shows the quartiles of the dataset (thus the center is the median) while the whiskers extend to show the 1.5 × IQR past the low and high quartiles. The table at the bottom elaborates the feature composition within each set of features, as determined by the backward stepwise elimination procedure.