Journal
JOURNAL OF THEORETICAL BIOLOGY
Volume 246, Issue 1, Pages 186-194Publisher
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
DOI: 10.1016/j.jtbi.2006.12.021
Keywords
phylogenetic diversity; greedy algorithm
Categories
Funding
- EPSRC [EP/D068800/1] Funding Source: UKRI
- Engineering and Physical Sciences Research Council [EP/D068800/1] Funding Source: researchfish
Ask authors/readers for more resources
Phylogenetic diversity (PD) is a measure of the extent to which different subsets of taxa span an evolutionary tree, and provides a quantitative tool for studying biodiversity conservation. Recently, it was shown that the problem of finding subsets of taxa of given size to maximize PD can be efficiently solved by a greedy algorithm. In this paper, we extend this earlier work, beginning with a more explicit description of the underlying combinatorial structure of the problem and its connection to greedoid theory. Next we show that an extension of the PD optimization problem to a phylogeographic setting is NP-hard, although a special case has a polynomial-time solution based on the greedy algorithm. We also show how the greedy algorithm can be used to solve some special cases of the PD optimization problem when the sets that are restricted to are ecologically 'viable'. Finally, we show that three measures related to PD fail to be optimized by a greedy algorithm. (c) 2007 Elsevier Ltd. All rights reserved.
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