Optimizing phylogenetic diversity under constraints

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

Full text not available from this repository. (Request a copy)


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
Depositing User: Vishal Gautam
Date Deposited: 04 Mar 2011 12:47
Last Modified: 30 Jan 2023 12:30
URI: https://ueaeprints.uea.ac.uk/id/eprint/23953
DOI: 10.1016/j.jtbi.2006.12.021

Actions (login required)

View Item View Item