Abstract
Three-way dissimilarities are a generalization of (two-way) dissimilarities which can be used to indicate the lack of homogeneity or resemblance between any three objects. Such maps have applications in cluster analysis and have been used in areas such as psychology and phylogenetics, where three-way data tables can arise. Special examples of such dissimilarities are three-way tree-metrics and ultrametrics, which arise from leaf-labelled trees with edges labelled by positive real numbers. Here we consider three-way maps which arise from leaf-labelled trees where instead the interior vertices are labelled by an arbitrary set of values. For unrooted trees, we call such maps three-way symbolic tree-maps; for rooted trees, we call them three-way symbolic ultrametrics since they can be considered as a generalization of the (two-way) symbolic ultrametrics of Bocker and Dress. We show that, as with two- and three-way tree-metrics and ultrametrics, three-way symbolic tree-maps and ultrametrics can be characterized via certain k-point conditions. In the unrooted case, our characterization is mathematically equivalent to one presented by Gurvich for a certain class of edge-labelled hypergraphs. We also show that it can be decided whether or not an arbitrary three-way symbolic map is a tree-map or a symbolic ultrametric using a triplet-based approach that relies on the so-called BUILD algorithm for deciding when a set of 3-leaved trees or triplets can be displayed by a single tree. We envisage that our results will be useful in developing new approaches and algorithms for understanding 3-way data, especially within the area of phylogenetics.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
AHO, A., SAGIV, Y., SZYMANSKI, T., and ULLMAN, J. (1981), “Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions", SIAM Journal of Computing, 28, 1073–1085.
BANDELT, H.-J., FORSTER, P., SYKES, B., and RICHARDS, M. (1995), “Mitochondrial Portraits of Human Populations Using Median Networks", Genetics, 141, 743–753.
BÖCKER, S., and DRESS, A. (1998), “Recovering Symbolically Dated, Rooted Trees from Symbolic Ultrametrics", Advances in Mathematics, 138, 105–125.
CHEPOI, V., and FICHET, B. (2007), “A Note on Three-Way Dissimilarities and Their Relationship with Two-Way Dissimilarities", in Selected Contributions in Data Analysis and Classification, eds. P. Briot et al., Berlin: Springer, pp. 465–475.
DEZA, M.-M., and ROSENBERG, I. (2000), “n-Semimetrics", European Journal of Combinatorics, 21, 797–806.
GRÜNEWALD, S., LONG, Y., and WU, Y. (2017) “Reconstructing Unrooted Phylogenetic Trees from Symbolic Ternary Metrics", arXiv:1702.00190
GURVICH, V. (1984), “Some Properties and Applications of Complete Edge-Chromatic Graphs and Hypergraphs", Soviet Mathematics Doklady, 30(3), 803–807.
GURVICH, V. (2009), “Decomposing Complete Edge-Chromatic Graphs and Hypergraphs", Discrete Applied Mathematics, 157, 3069–3085.
HAYASHI, C. (1972), “Two Dimensional Quantification Based on the Measure of Dissimilarity Among Three Elements", Annals of the Institute of Statistical Mathematics, 24, 251–257.
HEISER, W., and BENNANI, M. (1997), “Triadic Distance Models: Axiomatization and Least Squares Representation", Journal of Mathematical Psychology, 41, 189–206.
HELLMUTH, M., HERNANDEZ-ROSALES, M., HUBER, K.T., MOULTON, V., STADLER, P., and WIESEKE, N. (2013), “Orthology Relations, Symbolic Ultrametrics and Cographs", Journal of Mathematical Biology, 66, 399–420.
HELLMUTH, M., WIESEKE, N., LECHNER, M., LENHOF, H.-P., MIDDENDORF, M., and STADLER, P.F. (2015), “Phylogenomics with Paralogs", PNAS, 112(7), 2058–2063.
HERRMANN, S., HUBER, K.T., MOULTON, V., and SPILLNER, A. (2012), “Recognizing Treelike k-Dissimilarities", Journal of Classification, 29, 321–340.
HUBER, K.T., and SCHOLZ, G.E. (2018) “Beyond Representing Orthology Relations by Trees", Algorithmica, 80(1), 73–103.
JOLY, S., and LE CALVÉ, G. (1995), “Three-Way Distances", Journal of Classification, 12, 191–205.
LAFOND, M., and EL-MABROUK, N. (2015), “Orthology Relation and Gene Tree Correction: Complexity Results WABI 2015, Algorithms in Bioinformatics, 9289, 966–979.
LEVY, D., YOSHIDA, R., and PACHTER, L. (2006), “Beyond Pairwise Distances: Neighbor-Joining with Phylogenetic Diversity Estimates", Molecular Biology and Evolution, 23, 491–498.
SEMPLE, C., and STEEL, M. (2003), Phylogenetics, Oxford Lecture Series in Mathematics and its Applications, Oxford: Oxford University Press.
SIMONYI, G. (2001), Perfect Graphs and Graph Entropy, An Updated Survey, Wiley-Interscience Series in Discrete Mathematics and Optimization, Chichester: Wiley.
WARRENS, M. (2010), 11n-Way Metrics", Journal of Classification, 27, 173–190.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Huber, K.T., Moulton, V. & Scholz, G.E. Three-Way Symbolic Tree-Maps and Ultrametrics. J Classif 36, 513–540 (2019). https://doi.org/10.1007/s00357-018-9274-x
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00357-018-9274-x