@book{b0992590983b11dabee902004c4f4f50,
title = "Speeding Up Neighbour-Joining Tree Construction",
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 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.",
keywords = "Algorithms, Experimentation, Performance, Neighbour-joining, tree construction",
author = "Brodal, {Gerth St{\o}lting} and Rolf Fagerberg and Thomas Mailund and Pedersen, {Christian N{\o}rgaard Storm} and Derek Phillips",
year = "2003",
language = "English",
volume = "ALCOMFT-TR-03-102",
publisher = "ALCOM-FT",
edition = "Work package 5",
}