Speeding Up Neighbour-Joining Tree Construction

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

Technical Report, ALCOMFT-TR-03-102, ALCOM-FT, 9 pages, November 2003.

Abstract

A widely used method for constructing phylogenetic trees is the neighbour-joining method of Saitou and Nei. We develope heuristics for speeding up the neighbour-joining method which generate the same phylogenetic trees as the original method.

All heuristics are based on using a quad-tree to guide the search for the next pair of nodes to join, but differ in the information stored in quad-tree nodes, the way the search is performed, and in the way the quad-tree is updated after a join.

We empirically evaluate the performance of the heuristics on distance matrices obtained from the Pfam collection of alignments, and compare the running time with that of the QuickTree tool, a well-known and widely used implementation of the standard neighbour-joining method. The results show that the presented heuristics can give a significant speed-up over the standard neighbour-joining method, already for medium sized instances.

Online version

alcomft-tr-03-102.pdf (326 Kb)

BIBT_EX entry

@techreport{alcomft-tr-03-102,
  author = "Gerth Stølting Brodal and Rolf Fagerberg and Thomas Mailund and Christian Nørgaard Storm Pedersen and Derek Phillips",
  institution = "ALCOM-FT",
  month = "November",
  number = "ALCOMFT-TR-03-102",
  pages = "9",
  title = "Speeding Up Neighbour-Joining Tree Construction",
  year = "2003"
}