We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

On the Complexity of Optimising Variants of Phylogenetic Diversity on Phylogenetic Networks

Bordewich, Magnus and Semple, Charles and Wicke, Kristina (2022) 'On the Complexity of Optimising Variants of Phylogenetic Diversity on Phylogenetic Networks.', Theoretical Computer Science, 917 . pp. 66-80.


Phylogenetic Diversity (PD) is a prominent quantitative measure of the biodiversity of a collection of present-day species (taxa). This measure is based on the evolutionary distance among the species in the collection. Loosely speaking, if T is a rooted phylogenetic tree whose leaf set X represents a set of species and whose edges have real-valued lengths (weights), then the PD score of a subset S of X is the sum of the weights of the edges of the minimal subtree of T connecting the species in S. In this paper, we dene several natural variants of the PD score for a subset of taxa which are related by a known rooted phylogenetic network. Under these variants, we explore, for a positive integer k, the computational complexity of determining the maximum PD score over all subsets of taxa of size k when the input is restricted to dierent classes of rooted phylogenetic networks.

Item Type:Article
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives 4.0.
File format - PDF
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution 4.0.
Download PDF
Publisher Web site:
Publisher statement:© 2022 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (
Date accepted:09 March 2022
Date deposited:09 March 2022
Date of first online publication:26 April 2022
Date first made open access:18 May 2022

Save or Share this output

Look up in GoogleScholar