Branch and Bound reconstruction of Balanced Minimum Evolution optimal trees

Add to your list(s) Download to your calendar using vCal

• Fabio Pardi
• Wednesday 14 November 2007, 14:00-15:00
• TCM Seminar Room, Cavendish Laboratory, Department of Physics.

If you have a question about this talk, please contact David MacKay.

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.

This talk is part of the Inference Group series.

This talk is included in these lists:

• All Cavendish Laboratory Seminars
• All Talks (aka the CURE list)
• Biology
• Cambridge Neuroscience Seminars
• Cambridge talks
• Centre for Health Leadership and Enterprise
• Chris Davis' list
• Featured lists
• Guy Emerson's list
• Hanchen DaDaDash
• Inference Group
• Inference Group Summary
• Interested Talks
• Joint Machine Learning Seminars
• Life Science
• Life Sciences
• ME Seminar
• ML
• Machine Learning Summary
• Neurons, Fake News, DNA and your iPhone: The Mathematics of Information
• Neuroscience
• Neuroscience Seminars
• Neuroscience Seminars
• Required lists for MLG
• School of Physical Sciences
• Stem Cells & Regenerative Medicine
• TCM Seminar Room, Cavendish Laboratory, Department of Physics
• Thin Film Magnetic Talks
• dh539
• kt532's list
• rp587
• yk373's list

Note that ex-directory lists are not shown.