Skip to main content

Research Repository

Advanced Search

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

Bordewich, Magnus; Semple, Charles; Wicke, Kristina

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


Authors

Charles Semple

Kristina Wicke



Abstract

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.

Citation

Bordewich, M., Semple, C., & Wicke, K. (2022). On the Complexity of Optimising Variants of Phylogenetic Diversity on Phylogenetic Networks. Theoretical Computer Science, 917, 66-80. https://doi.org/10.1016/j.tcs.2022.03.012

Journal Article Type Article
Acceptance Date Mar 9, 2022
Online Publication Date Apr 26, 2022
Publication Date May 25, 2022
Deposit Date Mar 9, 2022
Publicly Available Date May 18, 2022
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 917
Pages 66-80
DOI https://doi.org/10.1016/j.tcs.2022.03.012
Public URL https://durham-repository.worktribe.com/output/1215733

Files






You might also like



Downloadable Citations