Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
On the Complexity of Optimising Variants of Phylogenetic Diversity on Phylogenetic Networks
Bordewich, Magnus; Semple, Charles; Wicke, Kristina
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 | Mar 28, 2024 |
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 |
Files
Published Journal Article
(628 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright 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/)
You might also like
Evaluating Gaussian Grasp Maps for Generative Grasping Models
(2022)
Conference Proceeding
On the Maximum Agreement Subtree Conjecture for Balanced Trees
(2022)
Journal Article
Autoencoders Without Reconstruction for Textural Anomaly Detection
(2021)
Conference Proceeding
Improving Robotic Grasping on Monocular Images Via Multi-Task Learning and Positional Loss
(2021)
Conference Proceeding
A universal tree-based network with the minimum number of reticulations
(2018)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search