School of Computer Science,McGill University, 3480 University Street, McConnell Engineering Building, Room 318, Montreal, QC H3A 2A7, Canada.
IEEE/ACM Trans Comput Biol Bioinform. 2011 Mar-Apr;8(2):551-6. doi: 10.1109/TCBB.2010.37.
The phylogenetic diversity (PD) of a set of species is a measure of their evolutionary distinctness based on a phylogenetic tree. PD is increasingly being adopted as an index of biodiversity in ecological conservation projects. The Noah's Ark Problem (NAP) is an NP-Hard optimization problem that abstracts a fundamental conservation challenge in asking to maximize the expected PD of a set of taxa given a fixed budget, where each taxon is associated with a cost of conservation and a probability of extinction. Only simplified instances of the problem, where one or more parameters are fixed as constants, have as of yet been addressed in the literature. Furthermore, it has been argued that PD is not an appropriate metric for models that allow information to be lost along paths in the tree. We therefore generalize the NAP to incorporate a proposed model of feature loss according to an exponential distribution and term this problem NAP with Loss (NAPL). In this paper, we present a pseudopolynomial time approximation scheme for NAPL.
一组物种的系统发育多样性（PD）是基于系统发育树衡量它们进化独特性的一种度量。PD 正越来越多地被用作生态保护项目中生物多样性的指标。诺亚方舟问题（NAP）是一个 NP 难优化问题，它抽象出了一个基本的保护挑战，即在给定固定预算的情况下，要求最大化一组分类单元的预期 PD，其中每个分类单元都与保护成本和灭绝概率相关联。到目前为止，文献中只解决了该问题的简化实例，其中一个或多个参数被固定为常数。此外，有人认为 PD 不是允许信息沿着树中的路径丢失的模型的合适度量。因此，我们将 NAP 推广到包含根据指数分布丢失特征的拟议模型，并将此问题命名为带损失的 NAP（NAPL）。在本文中，我们提出了 NAPL 的伪多项式时间逼近方案。
