Aarhus University Seal

Speeding Up Neighbour-Joining Tree Construction

Research output: Book/anthology/dissertation/reportReportResearch

  • Gerth Stølting Brodal
  • Rolf Fagerberg, Department of Mathematics and Computer Science, University of Southern Denmark, Denmark
  • Thomas Mailund, Bioinformatics Research Centre, Aarhus University, Aarhus, Denmark., Denmark
  • Christian Nørgaard Storm Pedersen
  • Derek Phillips, University of Waterloo, Canada
  • Department of Computer Science

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 di#er 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.

Original languageEnglish
Place of publicationwww.brics.dk
EditionWork package 5
Number of pages9
Publication statusPublished - 2003

    Research areas

  • Algorithms, Experimentation, Performance, Neighbour-joining, tree construction

See relations at Aarhus University Citationformats

ID: 280720