On approximation of optimizing phylogenetic diversity for cluster systems

Abstract

A basic question in conservation biology is how to maximize future biodiversity as species face extinction. One way to approach this question is by measuring the diversity of a set of species in terms of the evolutionary history that those species span in a phylogenetic tree. Maximizing the resulting 'phylogenetic diversity' (PD) is one prominent selection criteria for deciding which species to conserve. The basic PD optimization problem aims to find a k-element subset of a given species set that has maximum PD among all such subsets. In this paper, we consider a generalization of this problem, which arises in situations where we do not know the true tree, or where evolution is not tree-like. We show that a greedy algorithm gives a (1-e⁻¹)-approximation to the general PD optimization problem, and that there is no polynomial-time algorithm that achieves a better approximation ratio unless P=NP.