Recrafting the Neighbor-Joining Method

Mailund, Gerth Stølting Brodal, Rolf Fagerberg, Christian Nørgaard Storm Pedersen, Derek Phillips

    Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

    145 Downloads (Pure)


    Background: The neighbor-joining method by Saitou and Nei is a widely used method for constructing phylogenetic trees. The formulation of the method gives rise to a canonical Θ(n3) algorithm upon which all existing implementations are based. Methods: In this paper we present techniques for speeding up the canonical neighbor-joining method. Our algorithms construct the same phylogenetic trees as the canonical neighbor-joining method. The best-case running time of our algorithms are O(n2) but the worst-case remains O(n3). We empirically evaluate the performance of our algoritms on distance matrices obtained from the Pfam collection of alignments. Results: The experiments indicate that the running time of our algorithms evolve as Θ(n2) on the examined instance collection. We also compare the running time with that of the QuickTree tool, a widely used efficient implementation of the canonical neighbor-joining method. Conclusions: The experiments show that our algorithms also yield a significant speed-up, already for medium sized instances.
    TidsskriftB M C Bioinformatics
    StatusUdgivet - 2006


    Dyk ned i forskningsemnerne om 'Recrafting the Neighbor-Joining Method'. Sammen danner de et unikt fingeraftryk.