Technical Report CS-2006-11

A simple and natural neighbor joining criterion based on the above characterization is used to provide a family of consistent neighbor-joining algorithms which are simpler and more efficient than Saitou&Nei's NJ. A large subclass of this family is shown to be optimal under Atteson's robustness criterion for reconstruction of 'sufficiently long' edges; in this respect it outperforms NJ. A specific algorithm in this subclass is shown to provide a simpler version of the known 3-approximation algorithm of an arbitrary metric by an additive metric.

Our neighbor joining algorithms are pivotal, in the sense that when the input is not consistent with some tree, the output tree may depend on a root-taxon selected by the algorithm. We present experimental results for two variants of our algorithm on simulated data generated according to a well accepted evolutionary model. These experiments indicate that for the right selection of the root, the tree returned by our algorithm is likely to be topologically closer to the true tree than the one returned by NJ. The experimental results also indicate that selecting a root-taxon closer to the origin of evolution is likely to produce a more accurate tree. An interesting phenomenon demonstrated by our results is that in this evolutionary model, trees which best approximate the input distances are usually not the trees which best approximate the correct topology.