Tools
Tools
Moulton, Vincent 
ORCID: https://orcid.org/0000-0001-9371-6435, Semple, Charles and Steel, Mike
(2007)
Optimizing phylogenetic diversity under constraints.
Journal of Theoretical Biology, 246 (1).
pp. 186-194.
ISSN 0022-5193
Abstract
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.
| Item Type: | Article |
|---|---|
| Faculty \ School: | Faculty of Science > School of Computing Sciences |
| UEA Research Groups: | Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018) Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre |
| Depositing User: | Vishal Gautam |
| Date Deposited: | 04 Mar 2011 12:47 |
| Last Modified: | 15 Jun 2023 18:31 |
| URI: | https://ueaeprints.uea.ac.uk/id/eprint/23953 |
| DOI: | 10.1016/j.jtbi.2006.12.021 |
Actions (login required)
 |
View Item |