Technical Report CS-2006-11

Title: Pivotal Neighbor Joining Algorithms for Inferring Phylogenies via LCA-Distances
Authors: Ilan Gronau and Shlomo Moran
Abstract: 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 weighted trees by distances to LCAs (Least Common Ancestors). This characterization combines the theoretical advantages of ultrametrics, with the practical advantages of neighbor joining algorithms.

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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2006
To the main CS technical reports page

Computer science department, Technion