On approximation of optimizing phylogenetic diversity for cluster systems

Type of content
Discussion / Working Papers
Publisher's DOI/URI
Thesis discipline
Degree name
Publisher
University of Canterbury
Journal Title
Journal ISSN
Volume Title
Language
Date
2009
Authors
Faller, Beáta
Semple, Charles
Steel, M. A.
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.

Description
Citation
Keywords
Ngā upoko tukutuku/Māori subject headings
ANZSRC fields of research
Fields of Research::49 - Mathematical sciences::4901 - Applied mathematics::490102 - Biological mathematics
Rights
All Rights Reserved