On the Complexity of Optimising Variants of Phylogenetic Diversity on Phylogenetic Networks
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 $\mathcal{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 $\mathcal{T}$ connecting the species in $S$. In this paper, we define 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 different classes of rooted phylogenetic networks
Code (0)
등록된 구현이 없습니다.
Tasks
DiversitySimilar Papers 제목 키워드 기반
Bounds on the Treewidth of Level-k Rooted Phylogenetic Networks
Phylogenetic networks are directed acyclic graphs that depict the genomic evolution of related taxa. Reticulation nodes in such networks (nodes with more than one parent) represent reticulate evolutionary events, such as…
Tree DecompositionPhylogenetic diversity indices from an affine and projective viewpoint
Phylogenetic diversity indices are commonly used to rank the elements in a collection of species or populations for conservation purposes. The derivation of these indices is typically based on some quantitative descripti…
DiversityInvariants for level-1 phylogenetic networks under the random walk 4-state Markov model
Phylogenetic networks can represent evolutionary events that cannot be described by phylogenetic trees, such as hybridization, introgression, and lateral gene transfer. Studying phylogenetic networks under a statistical …
Quantifying the difference between phylogenetic diversity and diversity indices
Phylogenetic diversity is a popular measure for quantifying the biodiversity of a collection $Y$ of species, while phylogenetic diversity indices provide a way to apportion phylogenetic diversity to individual species. T…
DiversityCounting and optimising maximum phylogenetic diversity sets
In conservation biology, phylogenetic diversity (PD) provides a way to quantify the impact of the current rapid extinction of species on the evolutionary `Tree of Life'. This approach recognises that extinction not only …
Diversity