Phylogenetic diversity within seconds

Bui Quang Minh*, Steffen Klaere, Arndt Von Haeseler

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

32 Citations (Scopus)

Abstract

We consider a (phylogenetic) tree with n labeled leaves, the taxa, and a length for each branch in the tree. For any subset of k taxa, the phylogenetic diversity is defined as the sum of the branch-lengths of the minimal subtree connecting the taxa in the subset. We introduce two time-efficient algorithms (greedy and pruning) to compute a subset of size k with maximal phylogenetic diversity in O(n log k) and O[n + (n - k) log(n - k)] time, respectively. The greedy algorithm is an efficient implementation of the so-called greedy strategy (Steel, 2005; Pardi and Goldman, 2005), whereas the pruning algorithm provides an alternative description of the same problem. Both algorithms compute within seconds a subtree with maximal phylogenetic diversity for trees with 100,000 taxa or more.

Original languageEnglish
Pages (from-to)769-773
Number of pages5
JournalSystematic Biology
Volume55
Issue number5
DOIs
Publication statusPublished - 1 Oct 2006
Externally publishedYes

Fingerprint

Dive into the research topics of 'Phylogenetic diversity within seconds'. Together they form a unique fingerprint.

Cite this