6533b82cfe1ef96bd128f360

RESEARCH PRODUCT

New Algorithms for Computing Phylogenetic Biodiversity

Adrija KalvisaBrody SandelConstantinos Tsirogiannis

subject

Phylogenetic diversitysymbols.namesakeTree (descriptive set theory)Phylogenetic treeOpen problemsymbolsMinimum weightOrder (ring theory)Steiner tree problemMeasure (mathematics)AlgorithmMathematics

description

A common problem that appears in many case studies in ecology is the following: given a rooted phylogenetic tree \(\mathcal{T}\) and a subset R of its leaf nodes, we want to compute the distance between the elements in R. A very popular distance measure that can be used for this reason is the Phylogenetic Diversity (PD), which is defined as the cost of the minimum weight Steiner tree in \(\mathcal{T}\) that spans the nodes in R. To analyse the value of the PD for a given set R it is important also to calculate the variance of this measure. However, the best algorithm known so far for computing the variance of the PD is inefficient; for any input tree \(\mathcal{T}\) that consists of n nodes, this algorithm has Θ(n 2) running time. Moreover, computing efficiently the variance and higher order statistical moments is a major open problem for several other phylogenetic measures. We provide the following results:

yearjournalcountryeditionlanguage
2014-01-01
https://doi.org/10.1007/978-3-662-44753-6_15