| Summary: | <p>Abstract</p> <p>Background</p> <p>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 Θ(<it>n</it><sup>3</sup>) algorithm upon which all existing implementations are based.</p> <p>Results</p> <p>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 <it>O</it>(<it>n</it><sup>2</sup>) but the worst-case remains <it>O</it>(<it>n</it><sup>3</sup>). 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 Θ(<it>n</it><sup>2</sup>) 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.</p> <p>Conclusion</p> <p>The experiments show that our algorithms also yield a significant speed-up, already for medium sized instances.</p>
|
|---|