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.
|Full text:||Publisher-imposed embargo |
(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives 4.0.
File format - PDF (584Kb)
|Full text:||(VoR) Version of Record|
Available under License - Creative Commons Attribution 4.0.
Download PDF (614Kb)
|Publisher Web site:||https://doi.org/10.1016/j.tcs.2022.03.012|
|Publisher statement:||© 2022 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/)|
|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|