A partial order and cluster-similarity metric on rooted phylogenetic trees (Q2303737)

This article presents an alternative metric based on cluster similarity, which has several advantages. The metric is based on graded partial order, which means that the rank can be used to estimate tree distances. The metric also relies on a natural local operation of moving in tree space, which makes it easy to calculate the neighborhood of a given tree -- a particularly useful property when examining the MCMC (Markov Chain Monte Carlo) tree space. Finally, trees have much larger neighborhoods than other local operation metrics. Although the calculation of distances using a metric is nontrivial, the authors give an approximation of the upper boundary, which corresponds to the true distance in most cases in experimental modeling. This approximation takes polynomial time, and the simulation assumes that the upper bound for the metric does not skew (in contrast to the Robinson-Foulds distance), so there is hope that this metric will also not be skewed. The metric is based on the concept of a hierarchical map that links trees that have similar hierarchies. It is assumed that the new metric will surpass the Robinson-Foulds metric in distinguishing tree sets from real data, as computational experiments have shown that the current metric remains successful in recognizing bifurcated trees in a particular case. Finally, since the approximation of the upper bound is easy to calculate and relatively accurate, it will also reduce problems with the speed of computation. Section 2 introduces the concept of preserving a hierarchy map between trees; it is shown that maps preserving the hierarchy induce a partial order on the set of root phylogenetic trees. Section 3 proposes a metric based on a partial order Hasse diagram induced by mappings preserving the hierarchy. Section 4 gives an algorithm for calculating the upper boundary of a metric and initial results on its properties. Section 5 shows some results of calculations on the program for calculating the upper bound of a metric. Thus, the new metric on the phylogenetic tree-space presented in this article has a number of useful properties for biological applications: as far as it's a cluster similarity metric, the concept of distance between two trees corresponds to the similarity of their hierarchies. Unlike other cluster similarity metrics, this metric has a simple local operation for moving through the space of trees, providing easy calculation of neighborhoods. It can be expected that this function, combined with the property of cluster similarity, will help MCMC searches for the tree-like space around trees of similar hierarchies. In addition, the distribution of distances in a given space of trees seems quite symmetrical and also has a reasonable spread of values. This makes it possible to distinguish trees in the required manner in biological research. Finally, the concept of preserving a hierarchy of cards may be of independent mathematical interest.