Phylogenetic diversity within seconds.
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.
Minh
Bui Quang
BQ
Center for Integrative Bioinformatics, Vienna, Max F Perutz Laboratories, University of Vienna, Medical University of Vienna, Veterinary University of Vienna, Dr-Bohr-Gasse 9/6, A-1030, Vienna, Austria.
Klaere
Steffen
S
von Haeseler
Arndt
A
D000465:Algorithms; D044822:Biodiversity; D002965:Classification / Q000379:methods; D003198:Computer Simulation / Q000592:standards; D010802:Phylogeny