The split decomposition of a k-dissimilarity map

DOI10.1016/J.AAM.2012.01.003MaRDI QIDQ432491zbMATH OpenOpenAlexFDO

Authors Sven Herrmann, Vincent Moulton

Publication date 4 July 2012

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.1703

zbMATH Keywords

dissimilarity mapdistancemetric spacepolytopesplit decomposition

Mathematics Subject Classification ID

Trees (05C05) (n)-dimensional polytopes (52B11) Problems related to evolution (92D15)

Abstract: A k-dissimilarity map on a finite set X is a function D : X choose k ightarrow R assigning a real value to each subset of X with cardinality k, k geq 2. Such functions, also sometimes known as k-way dissimilarities, k-way distances, or k-semimetrics, are of interest in many areas of mathematics, computer science and classification theory, especially 2-dissimilarity maps (or distances) which are a generalisation of metrics. In this paper, we show how regular subdivisions of the kth hypersimplex can be used to obtain a canonical decomposition of a k-dissimilarity map into the sum of simpler k-dissimilarity maps arising from bipartitions or splits of X. In the special case k = 2, this is nothing other than the well-known split decomposition of a distance due to Bandelt and Dress [Adv. Math. 92 (1992), 47-105], a decomposition that is commonly to construct phylogenetic trees and networks. Furthermore, we characterise those sets of splits that may occur in the resulting decompositions of k-dissimilarity maps. As a corollary, we also give a new proof of a theorem of Pachter and Speyer [Appl. Math. Lett. 17 (2004), 615-621] for recovering k-dissimilarity maps from trees.

Recommendations

• Recognizing treelike k-dissimilarities
• On graphlike \(k\)-dissimilarity vectors
• A geometric study of the split decomposition
• A tropical interpretation of \(m\)-dissimilarity maps
• The Buneman index via polyhedral split decomposition

Cites work

• \(n\)-semimetrics
• \(n\)-way metrics
• A canonical decomposition theory for metrics on a finite set
• A tropical interpretation of \(m\)-dissimilarity maps
• Combinatorial calculation of characteristic classes
• Dissimilarity vectors of trees are contained in the tropical Grassmannian
• Geometry of cuts and metrics
• How to draw tropical planes
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• Lectures on Polytopes
• On the relation between weighted trees and tropical Grassmannians
• Recognizing treelike k-dissimilarities
• Reconstructing trees from subtree weights.
• Six theorems about injective metric spaces
• Splitting Polytopes
• The tropical Grassmannian
• Three-way distances
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• Triadic distance models: axiomatization and least squares representation
• Triangulations. Structures for algorithms and applications
• Tropical Linear Spaces
• Two dimensional quantification based on the measure of dissimilarity among three elements

Cited in

(4)

• Parity splits by triple point distances in \(X\)-trees
• Recognizing treelike k-dissimilarities
• Trees, tight-spans and point configurations
• The 22 minimal dichotomy decompositions of the \(K_5\)-distance

This page was built for publication: The split decomposition of a \(k\)-dissimilarity map

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q432491)