Optimizing phylogenetic diversity across two trees

Bordewich, M.; Semple, C.; Spillner, A.

doi:10.1016/j.aml.2008.05.004

Optimizing phylogenetic diversity across two trees

Bordewich, M.; Semple, C.; Spillner, A.

Authors

Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor

C. Semple

A. Spillner

Abstract

We present a polynomial-time algorithm for finding an optimal set of taxa that maximizes the weighted sum of the phylogenetic diversity across two phylogenetic trees. This resolves one of the challenges proposed as part of the Phylogenetics Programme held at the Isaac Newton Institute for Mathematical Sciences (Cambridge, 2007). It also completely closes the gap between optimizing phylogenetic diversity on one tree, which is known to be in P, and optimizing phylogenetic diversity across three or more trees, which is known to be NP-hard.

Citation

Bordewich, M., Semple, C., & Spillner, A. (2009). Optimizing phylogenetic diversity across two trees. Applied Mathematics Letters, 22(5), 638-641. https://doi.org/10.1016/j.aml.2008.05.004

Journal Article Type	Article
Publication Date	May 1, 2009
Deposit Date	Dec 21, 2009
Journal	Applied Mathematics Letters
Print ISSN	0893-9659
Publisher	Elsevier
Peer Reviewed	Peer Reviewed
Volume	22
Issue	5
Pages	638-641
DOI	https://doi.org/10.1016/j.aml.2008.05.004
Keywords	Phylogenetic diversity.