skip to content

Branch and bound construction of balanced minimum evolution optimal trees

Tuesday 4th September 2007 - 15:30 to 15:50
INI Seminar Room 1

The Balanced Minimum Evolution (BME) score has been recently proposed as a criterion for reconstructing phylogenetic trees based on a distance matrix. It is based on Pauplin's formula, which provides a natural estimate of the total length of a tree, based on 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 trying to minimise 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 a simple bound on the BME score of a tree based on the score of a partially constructed tree. This allows us to eliminate 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.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons