期刊
JOURNAL OF THEORETICAL BIOLOGY
卷 246, 期 1, 页码 186-194出版社
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
DOI: 10.1016/j.jtbi.2006.12.021
关键词
phylogenetic diversity; greedy algorithm
资金
- EPSRC [EP/D068800/1] Funding Source: UKRI
- Engineering and Physical Sciences Research Council [EP/D068800/1] Funding Source: researchfish
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据