The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Neighbor joining algorithms for inferring phylogenies via LCA-distances

Moran, S (Israel)
Thursday 06 September 2007, 10:20-10:40

Seminar Room 1, Newton Institute


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 ({\em 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\&Nei's NJ. Preliminary experimental results indicate that when executed from an appropriate root taxon, this algorithm provides reconstruction of phylogenies which are competitive with NJ and other common algorithms.


[pps ]




The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧