Journal
SYSTEMATIC BIOLOGY
Volume 55, Issue 5, Pages 769-773Publisher
OXFORD UNIV PRESS
DOI: 10.1080/10635150600981604
Keywords
-
Categories
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available