Phylogenetic diversity and the greedy algorithm
Phylogenetic diversity and the greedy algorithm
复制标题
DOI：
10.1080/10635150590947023
复制
发表时间：
2005-08-01
影响因子：
6.5
通讯作者：
Steel, M
中科院分区：
文献类型：
--
作者：
Steel, M
给定一个系统发育树，其叶子由物种集合标记，并且具有加权边缘，该物种的任何子集的“系统发育多样性”是连接该物种的最小子树的边缘权重之和。这一措施与生物多样性保护相关，人们可能希望根据物种包含的进化变异程度来比较不同的物种子集。在这篇文章中，我们表明系统发育多样性具有一个有吸引力的数学特性，确保我们可以通过贪心算法轻松解决以下问题：找到最大系统发育多样性的任何给定大小 k 的物种子集。我们还描述了该结果的扩展，它还允许为物种分配权重。
Given a phylogenetic tree with leaves labeled by a collection of species, and with weighted edges, the "phylogenetic diversity" of any subset of the species is the sum of the edge weights of the minimal subtree connecting the species. This measure is relevant in biodiversity conservation where one may wish to compare different subsets of species according to how much evolutionary variation they encompass. In this note we show that phylogenetic diversity has an attractive mathematical property that ensures that we can solve the following problem easily by the greedy algorithm: find a subset of the species of any given size k of maximal phylogenetic diversity. We also describe an extension of this result that also allows weights to be assigned to species.