%0 Journal Article %1 minh2006 %A Minh, Bui Quang %A Klaere, Steffen %A von Haeseler, Arndt %D 2006 %J Syst. Biol. %K Biodiversity_conservation Comparative_genomics Greedy_algorithm Phylogenetic_diversity Phylogenetic_tree Pruning_algorithm %N 5 %P 769-773 %T Phylogenetic Diversity within Seconds %U http://dx.doi.org/10.1080/10635150600981604 %V 55 %X 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 On + (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.

@article{minh2006, 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.}, added-at = {2009-05-14T12:41:45.000+0200}, author = {Minh, Bui Quang and Klaere, Steffen and von Haeseler, Arndt}, biburl = {https://www.bibsonomy.org/bibtex/2f06e2a3a15b51d2a625d53b627ef0ccc/compevol}, interhash = {a2f0a15304ecc0937bc04b5af8097df5}, intrahash = {f06e2a3a15b51d2a625d53b627ef0ccc}, journal = {Syst. Biol.}, keywords = {Biodiversity_conservation Comparative_genomics Greedy_algorithm Phylogenetic_diversity Phylogenetic_tree Pruning_algorithm}, month = Oct, number = 5, pages = {769-773}, timestamp = {2009-05-14T12:41:45.000+0200}, title = {Phylogenetic Diversity within Seconds}, url = {http://dx.doi.org/10.1080/10635150600981604}, volume = 55, year = 2006 }