Ordinal properties of tree distances Original Research Article

The order distance associated with a dissimilarity is defined comparing the weak orders of the proximity values relative to each element of a set X. We first demonstrate that if a dissimilarity is a tree distance, its order distance is also a tree distance that can be represented on the same tree, with different edge lengths. Then, for any quadruple, we compare its metric topology, evaluated from the tree distance, and its ordinal topology based on the weak order relations. From these comparisons we establish some ordinal properties of a tree distance and we give a necessary and sufficient condition for an ordinal dissimilarity, that is a weak order on the set of pairs on X, to be representable on a tree. Finally, we define a constructive algorithm to build a tree distance from a given tree ordinal dissimilarity.