Portal de Periódicos da CAPES

Recrafting the neighbor-joining method

2006; BioMed Central; Volume: 7; Issue: 1 Linguagem: Inglês

10.1186/1471-2105-7-29

1471-2105

Thomas Mailund, Gerth Stølting Brodal, Rolf Fagerberg, Christian NS Pedersen, Derek Phillips,

Plant and Fungal Species Descriptions

Abstract 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 Θ( n 3 ) algorithm upon which all existing implementations are based. Results 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 ( n 2 ) but the worst-case remains O ( n 3 ). We empirically evaluate the performance of our algoritms on distance matrices obtained from the Pfam collection of alignments. The experiments indicate that the running time of our algorithms evolve as Θ( n 2 ) 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. Conclusion The experiments show that our algorithms also yield a significant speed-up, already for medium sized instances.