Reconstructing phylogenetic trees efficiently and accurately from distance estimates is
an ongoing challenge in computational biology from both practical and theoretical
considerations. We study algorithms which are based on a characterization of edge-weighted
trees by distances to LCAs (Least Common Ancestors). This characterization enables a
direct application of ultrametric reconstruction techniques to trees which are not necessarily
ultrametric. A simple and natural neighbor joining criterion based on this observation is used
to provide a family of efficient neighbor-joining algorithms. These algorithms are shown to
reconstruct a refinement of the Buneman tree, which implies optimal robustness to noise under
criteria defined by Atteson. In this sense, they outperform many popular algorithms such as
Saitou and Nei's NJ. One member of this family is used to provide a new simple version of the
3-approximation algorithm for the closest additive metric under the ι
∞ norm. A byproduct of
our work is a novel technique which yields a time optimalO (n
2) implementation of common
clustering algorithms such as UPGMA.
