BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Inference Group
SUMMARY:Branch and Bound reconstruction of Balanced Minimu
m Evolution optimal trees - Fabio Pardi
DTSTART;TZID=Europe/London:20071114T140000
DTEND;TZID=Europe/London:20071114T150000
UID:TALK9159AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/9159
DESCRIPTION:The classical question in phylogenetics is: how sh
ould we use the\ncharacteristics of a group of spe
cies to infer their phylogenetic tree?\nA variety
of methods that address this question have been de
veloped in\nthe past 40 years. Among them\, dista
nce-based methods (such as\nNeighbor-joining) base
their reconstruction on a matrix of distances\nbe
tween each pair of species. Typically\, they are
used whenever speed\nof execution is of critical i
mportance.\n\nBalanced Minimum Evolution (BME) has
been recently proposed as a\ncriterion for distan
ce-based tree reconstruction. It is based on\nPau
plin's formula\, which provides a natural estimate
of the total length\nof a tree\, as a function of
its topology and a matrix of estimated\npairwise
distances. The objective is to find the tree topo
logy that\nminimizes this length estimate\, as sho
rt trees are usually the ones that\nbest reflect t
he data.\n\nRecently\, it has been shown that Neig
hbor-joining can be viewed as a\ngreedy algorithm
aiming to optimise BME. Together with other\ntheo
retical reasons\, there are strong experimental re
asons supporting\nBME-guided tree reconstruction.
However\, the published methods are\nheuristic an
d do not attempt to construct BME-optimal trees.\n
\nThe main aim of this talk will be to present a B
ranch and Bound approach\nfor finding BME-optimal
trees. We derived bounds on the BME score of a\nt
ree based on the score of a partially constructed
tree. This\neliminates the need to explore large
parts of the space of all possible\ntrees\, but st
ill guarantees that all optimal trees will be foun
d. The\nefficiency of this approach compares well
with that of other Branch and\nBound approaches s
uch as the ones for Maximum Parsimony. Finally\,
the\ntopological accuracy of the reconstructed tre
es will also be discussed.\n\n\n
LOCATION:TCM Seminar Room\, Cavendish Laboratory\, Departme
nt of Physics
CONTACT:David MacKay
END:VEVENT
END:VCALENDAR