Counting and optimising maximum phylogenetic diversity sets
From MaRDI portal
Abstract: 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 removes species but also the branches of the tree on which unique features shared by the extinct species arose. In this paper, we investigate three questions that are relevant to PD. The first asks how many sets of species of given size preserve the maximum possible amount of PD in a given tree. The number of such maximum PD sets can be very large, even for moderate-sized phylogenies. We provide a combinatorial characterisation of maximum PD sets, focusing on the setting where the branch lengths are ultrametric (e.g. proportional to time). This leads to a polynomial-time algorithm for calculating the number of maximum PD sets of size by applying a generating function; we also investigate the types of tree shapes that harbour the most (or fewest) maximum PD sets of size . Our second question concerns optimising a linear function on the species (regarded as leaves of the phylogenetic tree) across all the maximum PD sets of a given size. Using the characterisation result from the first question, we show how this optimisation problem can be solved in polynomial time, even though the number of maximum PD sets can grow exponentially. Our third question considers a dual problem: If species were to become extinct, then what is the largest possible {em loss} of PD in the resulting tree? For this question, we describe a polynomial-time solution based on dynamical programming.
Recommendations
- Optimizing phylogenetic diversity under constraints
- Optimizing phylogenetic diversity across two trees
- Distribution of phylogenetic diversity under random extinction
- Comparing strategies to preserve evolutionary diversity
- Fast phylogenetic biodiversity computations under a non-uniform random distribution
Cites work
- Lexicographic multi-objective linear programming using grossone methodology: theory and algorithm
- Optimizing phylogenetic diversity across two trees
- Optimizing phylogenetic diversity under constraints
- Phylogeny. Discrete and random processes in evolution
- The minimum latency problem
- Topological sorting of large networks
Cited in
(13)- Optimizing phylogenetic diversity across two trees
- Comparing strategies to preserve evolutionary diversity
- Evolutionary isolation and phylogenetic diversity loss under random extinction events
- Distribution of phylogenetic diversity under random extinction
- Evolutionarily distinctive species often capture more phylogenetic diversity than expected
- Effects of discordance between species and gene trees on phylogenetic diversity conservation
- On the complexity of optimising variants of phylogenetic diversity on phylogenetic networks
- Optimizing phylogenetic diversity under constraints
- Fast phylogenetic biodiversity computations under a non-uniform random distribution
- The expected loss of feature diversity (versus phylogenetic diversity) following rapid extinction at the present
- Optimizing phylogenetic diversity with ecological constraints
- An interchange property for the rooted phylogenetic subnet diversity on phylogenetic networks
- Counting and sampling SCJ small parsimony solutions
This page was built for publication: Counting and optimising maximum phylogenetic diversity sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2161386)
