Andreas Spillner,
Binh T. Nguyen and
Vincent Moulton. Computing phylogenetic diversity for split systems. In TCBB, Vol. 5(2):235244, 2008. Keywords: abstract network, diversity, phylogenetic network, phylogeny, split. Note: http://dx.doi.org/10.1109/TCBB.2007.70260, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0906/spillner/.
Toggle abstract
"In conservation biology it is a central problem to measure, predict, and preserve biodiversity as species face extinction. In 1992 Faith proposed measuring the diversity of a collection of species in terms of their relationships on a phylogenetic tree, and to use this information to identify collections of species with high diversity. Here we are interested in some variants of the resulting optimization problem that arise when considering species whose evolution is better represented by a network rather than a tree. More specifically, we consider the problem of computing phylogenetic diversity relative to a split system on a collection of species of size $n$. We show that for general split systems this problem is NPhard. In addition we provide some efficient algorithms for some special classes of split systems, in particular presenting an optimal $O(n)$ time algorithm for phylogenetic trees and an $O(nlog n + n k)$ time algorithm for choosing an optimal subset of size $k$ relative to a circular split system. © 2006 IEEE."
