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

Bordewich, Magnus; Semple, Charles; Wicke, Kristina

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