Inference of Large Phylogenies Using Neighbour-Joining

Martin Simonsen; Thomas Mailund; Christian Nørgaard Storm Pedersen

doi:10.1007/978-3-642-18472-7_26

Inference of Large Phylogenies Using Neighbour-Joining

Martin Simonsen, Thomas Mailund, Christian Nørgaard Storm Pedersen

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

22 Citations (Scopus)

Abstract

The neighbour-joining method is a widely used method for phylogenetic reconstruction which scales to thousands of taxa. However, advances in sequencing technology have made data sets with more than 10,000 related taxa widely available. Inference of such large phylogenies takes hours or days using the Neighbour-Joining method on a normal desktop computer because of the O(n^3) running time. RapidNJ is a search heuristic which reduce the running time of the Neighbour-Joining method significantly but at the cost of an increased memory consumption making inference of large phylogenies infeasible. We present two extensions for RapidNJ which reduce the memory requirements and \makebox{allows} phylogenies with more than 50,000 taxa to be inferred efficiently on a desktop computer. Furthermore, an improved version of the search heuristic is presented which reduces the running time of RapidNJ on many data sets.

Original language	English
Journal	Biomedical Engineering Systems and Technologies
Volume	127
Issue	5
Pages (from-to)	334-344
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-642-18472-7_26
Publication status	Published - 2011

Keywords

Neighbour-Joining
algorithmics
bioinformatics

Access to Document

10.1007/978-3-642-18472-7_26

Library access?

Check availability with the Royal Danish Library

Cite this

@article{a6d1626cb13e4171a8a28928e19142ab,

title = "Inference of Large Phylogenies Using Neighbour-Joining",

abstract = "The neighbour-joining method is a widely used method for phylogenetic reconstruction which scales to thousands of taxa. However, advances in sequencing technology have made data sets with more than 10,000 related taxa widely available. Inference of such large phylogenies takes hours or days using the Neighbour-Joining method on a normal desktop computer because of the O(n\textasciicircum{}3) running time. RapidNJ is a search heuristic which reduce the running time of the Neighbour-Joining method significantly but at the cost of an increased memory consumption making inference of large phylogenies infeasible. We present two extensions for RapidNJ which reduce the memory requirements and \textbackslash{}makebox\{allows\} phylogenies with more than 50,000 taxa to be inferred efficiently on a desktop computer. Furthermore, an improved version of the search heuristic is presented which reduces the running time of RapidNJ on many data sets.",

keywords = "Neighbour-Joining, algorithmics, bioinformatics",

author = "Martin Simonsen and Thomas Mailund and Pedersen, \{Christian N{\o}rgaard Storm\}",

year = "2011",

doi = "10.1007/978-3-642-18472-7\_26",

language = "English",

volume = "127",

pages = "334--344",

journal = "Biomedical Engineering Systems and Technologies",

publisher = "Springer Verlag",

number = "5",

}

TY - JOUR

T1 - Inference of Large Phylogenies Using Neighbour-Joining

AU - Simonsen, Martin

AU - Mailund, Thomas

AU - Pedersen, Christian Nørgaard Storm

PY - 2011

Y1 - 2011

N2 - The neighbour-joining method is a widely used method for phylogenetic reconstruction which scales to thousands of taxa. However, advances in sequencing technology have made data sets with more than 10,000 related taxa widely available. Inference of such large phylogenies takes hours or days using the Neighbour-Joining method on a normal desktop computer because of the O(n^3) running time. RapidNJ is a search heuristic which reduce the running time of the Neighbour-Joining method significantly but at the cost of an increased memory consumption making inference of large phylogenies infeasible. We present two extensions for RapidNJ which reduce the memory requirements and \makebox{allows} phylogenies with more than 50,000 taxa to be inferred efficiently on a desktop computer. Furthermore, an improved version of the search heuristic is presented which reduces the running time of RapidNJ on many data sets.

AB - The neighbour-joining method is a widely used method for phylogenetic reconstruction which scales to thousands of taxa. However, advances in sequencing technology have made data sets with more than 10,000 related taxa widely available. Inference of such large phylogenies takes hours or days using the Neighbour-Joining method on a normal desktop computer because of the O(n^3) running time. RapidNJ is a search heuristic which reduce the running time of the Neighbour-Joining method significantly but at the cost of an increased memory consumption making inference of large phylogenies infeasible. We present two extensions for RapidNJ which reduce the memory requirements and \makebox{allows} phylogenies with more than 50,000 taxa to be inferred efficiently on a desktop computer. Furthermore, an improved version of the search heuristic is presented which reduces the running time of RapidNJ on many data sets.

KW - Neighbour-Joining

KW - algorithmics

KW - bioinformatics

U2 - 10.1007/978-3-642-18472-7_26

DO - 10.1007/978-3-642-18472-7_26

M3 - Journal article

VL - 127

SP - 334

EP - 344

JO - Biomedical Engineering Systems and Technologies

JF - Biomedical Engineering Systems and Technologies

IS - 5

ER -

Inference of Large Phylogenies Using Neighbour-Joining

Abstract

Keywords

Access to Document

Library access?

Fingerprint

Cite this