main page

    Fast Neighbor Joining

    Isaac Elias and Jens Lagergren

    Abstract

    Reconstructing the evolutionary history of a set of species is a fundamental problem in biology and methods for solving this problem are gaged based on two characteristics: accuracy and efficiency. Neighbor Joining (NJ) is a so-called distance-based method that, thanks to its good accuracy and speed, has been embraced by the phylogeny community. It takes the distances between $n$ taxa and produces in $\Theta(n^3)$ time a phylogenetic tree, i.e., a tree which aims to describe the evolutionary history of the taxa. In addition to performing well in practice, the NJ algorithm has optimal reconstruction radius.

    The contribution of this paper is twofold: (1) we present an algorithm called Fast Neighbor Joining (FNJ) with optimal reconstruction radius and optimal run time complexity $O(n^2)$ and (2) we present a greatly simplified proof for the correctness of NJ. Initial experiments show that FNJ in practice has almost the same accuracy as NJ, indicating that the property of optimal reconstruction radius has great importance to their good performance. Moreover, we show how improved running time can be achieved for computing the so-called correction formulas.

    Download

    In Proc. of the 32nd Int. Coll. on Automata, Languages and Programming (ICALP'05), volume 3580 of Lecture Notes in Computer Science, pages 1263-1274. Springer-Verlag, July 2005.
    (PDF, Springer)

    Slides from presentation at Technion, Israel 2006
    (PDF)

    Slides from presentation at ICALP 2005
    (PDF)

    Google scholar citations Go Citeseer

    BibTex 

    @InProceedings{ICALP05:EliasLagergren_FNJ,
  author =      {Isaac Elias and Jens Lagergren},
  title =	{Fast Neighbor Joining},
  booktitle =	{Proc. of the 32nd International Colloquium on Automata, 
                Languages and Programming ({ICALP}'05)},
  pages =	{1263--1274},
  year =	{2005},
  volume =	{3580},
  series =	{Lecture Notes in Computer Science},
  month =	{July},
  publisher =	{Springer-Verlag},
  ISBN =	{3-540-27580-0},
}