Building Very Large Neighbour-Joining Trees

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review


  • Article

    Final published version, 688 KB, PDF document

The neighbour-joining method by Saitou and Nei is a widely used method for phylogenetic reconstruction, made popular by a combination of computational efficiency and reasonable accuracy. With its cubic running time by Studier and Kepler, the method scales to hundreds of species, and while it is usually possible to infer phylogenies with thousands of species, tens or hundreds of thousands of species is infeasible. Recently we developed a simple branch and bound heuristic, RapidNJ, which significantly reduces the average running time. However, the O(n2) space consumption of the RapidNJ method, and the NJ method in general, becomes a problem when inferring phylogenies with 10000+ taxa. In this paper we present two extentions of RapidNJ which reduce memory requirements and enable RapidNJ to infer very large phylogenetic trees efficiently. We also present an improved search heuristic for RapidNJ which improves RapidNJ's performance on many data sets of all sizes.

Original languageEnglish
Title of host publicationBIOINFORMATICS 2010 : Proceedings of the First International Conference on Bioinformatics (part of the 3rd International Joint Conference on Biomedical Engineering Systems and Technologies, BIOSTEC 2010)
EditorsAna Fred, Joaquim Filipe, Hugo Gamboa
Number of pages7
PublisherInstitute for Systems and Technologies of Information, Control and Communication
Publication year2010
ISBN (print)978-989-674-019-1
Publication statusPublished - 2010
EventThe International Joint Conference on Biomedical Engineering Systems and Technologies. - Valencia, Spain
Duration: 20 Jan 201023 Jan 2010


ConferenceThe International Joint Conference on Biomedical Engineering Systems and Technologies.

    Research areas

  • Phylogenetic tree, Neighbour-Joining, Clustering, RapidNJ

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 19058608