BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Branch and Bound reconstruction of Balanced Minimum Evolution opti
 mal trees - Fabio Pardi
DTSTART:20071114T140000Z
DTEND:20071114T150000Z
UID:TALK9159@talks.cam.ac.uk
CONTACT:David MacKay
DESCRIPTION:The classical question in phylogenetics is: how should we use 
 the\ncharacteristics of a group of species to infer their phylogenetic tre
 e?\nA variety of methods that address this question have been developed in
 \nthe past 40 years.  Among them\, distance-based methods (such as\nNeighb
 or-joining) base their reconstruction on a matrix of distances\nbetween ea
 ch pair of species.  Typically\, they are used whenever speed\nof executio
 n is of critical importance.\n\nBalanced Minimum Evolution (BME) has been 
 recently proposed as a\ncriterion for distance-based tree reconstruction. 
  It is based on\nPauplin's formula\, which provides a natural estimate of 
 the total length\nof a tree\, as a function of its topology and a matrix o
 f estimated\npairwise distances.  The objective is to find the tree topolo
 gy that\nminimizes this length estimate\, as short trees are usually the o
 nes that\nbest reflect the 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\ntheoretical reasons\, there are strong experimental 
 reasons supporting\nBME-guided tree reconstruction.  However\, the publish
 ed methods are\nheuristic and do not attempt to construct BME-optimal tree
 s.\n\nThe main aim of this talk will be to present a Branch and Bound appr
 oach\nfor finding BME-optimal trees.  We derived bounds on the BME score o
 f a\ntree based on the score of a partially constructed tree.  This\nelimi
 nates the need to explore large parts of the space of all possible\ntrees\
 , but still guarantees that all optimal trees will be found.  The\nefficie
 ncy of this approach compares well with that of other Branch and\nBound ap
 proaches such as the ones for Maximum Parsimony.  Finally\, the\ntopologic
 al accuracy of the reconstructed trees will also be discussed.\n\n\n
LOCATION:TCM Seminar Room\, Cavendish Laboratory\, Department of Physics
END:VEVENT
END:VCALENDAR