Abstract

The classical question in phylogenetics is: how should we use the characteristics of a group of species to infer their phylogenetic tree? A variety of methods that address this question have been developed in the past 40 years. Among them, distance-based methods (such as Neighbor-joining) base their reconstruction on a matrix of distances between each pair of species. Typically, they are used whenever speed of execution is of critical importance.

Balanced Minimum Evolution (BME) has been recently proposed as a criterion for distance-based tree reconstruction. It is based on Pauplin’s formula, which provides a natural estimate of the total length of a tree, as a function of its topology and a matrix of estimated pairwise distances. The objective is to find the tree topology that minimizes this length estimate, as short trees are usually the ones that best reflect the data.

Recently, it has been shown that Neighbor-joining can be viewed as a greedy algorithm aiming to optimise BME . Together with other theoretical reasons, there are strong experimental reasons supporting BME -guided tree reconstruction. However, the published methods are heuristic and do not attempt to construct BME -optimal trees.

The main aim of this talk will be to present a Branch and Bound approach for finding BME -optimal trees. We derived bounds on the BME score of a tree based on the score of a partially constructed tree. This eliminates the need to explore large parts of the space of all possible trees, but still guarantees that all optimal trees will be found. The efficiency of this approach compares well with that of other Branch and Bound approaches such as the ones for Maximum Parsimony. Finally, the topological accuracy of the reconstructed trees will also be discussed.