dc.contributor.author |
Minh, BQ |
en |
dc.contributor.author |
Klaere, Steffen |
en |
dc.contributor.author |
von Haeseler, A |
en |
dc.date.accessioned |
2012-05-28T01:47:17Z |
en |
dc.date.issued |
2006 |
en |
dc.identifier.citation |
Systematic Biology 55(5):769-773 2006 |
en |
dc.identifier.issn |
1063-5157 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/18672 |
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 |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
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 |
http://purl.org/eprint/accessRights/RestrictedAccess |
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 |