Phylogenetic Diversity within Seconds

Show simple item record Minh, BQ en Klaere, Steffen en von Haeseler, A en 2012-05-28T01:47:17Z en 2006 en
dc.identifier.citation Systematic Biology 55(5):769-773 2006 en
dc.identifier.issn 1063-5157 en
dc.identifier.uri en
dc.description.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. en
dc.publisher Society of Systematic Biologists en
dc.relation.ispartofseries Systematic Biology en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. en
dc.rights.uri en
dc.title Phylogenetic Diversity within Seconds en
dc.type Journal Article en
dc.identifier.doi 10.1080/10635150600981604 en
pubs.issue 5 en
pubs.begin-page 769 en
pubs.volume 55 en
dc.rights.holder Copyright: Society of Systematic Biologists en
dc.identifier.pmid 17060198 en
pubs.end-page 773 en
dc.rights.accessrights en
pubs.subtype Article en
pubs.elements-id 91504 en
pubs.record-created-at-source-date 2010-09-01 en
pubs.dimensions-id 17060198 en

Files in this item

There are no files associated with this item.

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace