Discrete CATS Seminar
U N I V E R S I T Y   O F   K E N T U C K Y
WHERE CATS =
845 PATTERSON OFFICE TOWER
2008 - 2009
"Least Squares Methods for Equidistant Tree Reconstruction"
San Francisco State University
Tuesday, September 30, 2008
4:00 pm, 208 Classroom Building
UPGMA is a heuristic method identifying the least squares equidistant
phylogenetic tree given empirical distance data among n taxa. We
study this classic algorithm using the geometry of the space of all
equidistant trees with n leaves, also known as the Bergman complex
of the graphical matroid for the complete graph K_n. We show that
UPGMA performs an orthogonal projection of the data onto a maximal
cell of the Bergman complex. We also show that the equidistant tree
with the least (Euclidean) distance from the data is obtained from
such an orthogonal projection, but not necessarily given by UPGMA.
Using this geometric information we give an extension of the UPGMA
algorithm. We also present a branch and bound method for finding the
best equidistant tree. Finally, we prove that there are distance data
among n taxa which project to at least (n-1)! equidistant trees.