title: Recrafting the neighbor-joining method.
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 Theta(n3) 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(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. The experiments indicate that the running time of our algorithms evolve as Theta(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.
authors.affiliation: Bioinformatics Research Center, University of Aarhus, Denmark. mailund@birc.dk
authors.forename: Thomas
authors.initials: T
authors.lastname: Mailund
authors.forename: Gerth S
authors.initials: GS
authors.lastname: Brodal
authors.forename: Rolf
authors.initials: R
authors.lastname: Fagerberg
authors.forename: Christian N S
authors.initials: CN
authors.lastname: Pedersen
authors.forename: Derek
authors.initials: D
authors.lastname: Phillips
mesh_terms: D000465:Algorithms; D000818:Animals; D016000:Cluster Analysis; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D019143:Evolution, Molecular; D006801:Humans; D016013:Likelihood Functions; D015233:Models, Statistical; D010802:Phylogeny; D016415:Sequence Alignment; D020539:Sequence Analysis, Protein; D012984:Software