Optimizing phylogenetic diversity under constraints

Moulton, Vincent, 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)

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
University of East Anglia > Faculty of Science > Research Groups > Computational Biology (subgroups are shown below) > Computational biology of RNA
University of East Anglia > Faculty of Science > Research Groups > Computational Biology (subgroups are shown below) > Phylogenetics
?? RGCB ??
Related URLs:
Depositing User: Vishal Gautam
Date Deposited: 04 Mar 2011 12:47
Last Modified: 25 Jul 2018 05:37
URI: https://ueaeprints.uea.ac.uk/id/eprint/23953
DOI: 10.1016/j.jtbi.2006.12.021

Actions (login required)

View Item