Least Squares Methods for Equidistant Tree Reconstruction

Details Least Squares Methods for Equidistant Tree Reconstruction Least Squares Methods for Equidistant Tree Reconstruction

2008-08-28

arxiv.org/abs/0808.3979v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Least Squares Methods for Equidistant Tree Reconstruction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Least Squares Methods for Equidistant Tree Reconstruction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Least Squares Methods for Equidistant Tree Reconstruction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-327929