Recognizing treelike k-dissimilarities
From MaRDI portal
Publication:263358
Abstract: A k-dissimilarity D on a finite set X, |X| >= k, is a map from the set of size k subsets of X to the real numbers. Such maps naturally arise from edge-weighted trees T with leaf-set X: Given a subset Y of X of size k, D(Y) is defined to be the total length of the smallest subtree of T with leaf-set Y . In case k = 2, it is well-known that 2-dissimilarities arising in this way can be characterized by the so-called "4-point condition". However, in case k > 2 Pachter and Speyer recently posed the following question: Given an arbitrary k-dissimilarity, how do we test whether this map comes from a tree? In this paper, we provide an answer to this question, showing that for k >= 3 a k-dissimilarity on a set X arises from a tree if and only if its restriction to every 2k-element subset of X arises from some tree, and that 2k is the least possible subset size to ensure that this is the case. As a corollary, we show that there exists a polynomial-time algorithm to determine when a k-dissimilarity arises from a tree. We also give a 6-point condition for determining when a 3-dissimilarity arises from a tree, that is similar to the aforementioned 4-point condition.
Recommendations
Cites work
- A Note on Three-Way Dissimilarities and Their Relationship with Two-Way Dissimilarities
- A Review of Hierarchical Classification
- A fast algorithm for constructing trees from distance matrices
- A tropical interpretation of \(m\)-dissimilarity maps
- An order theoretic framework for overlapping clustering
- Basic phylogenetic combinatorics.
- Phylogenetic diversity over an abelian group
- Recognition of Tree Metrics
- Reconstructing trees from subtree weights.
- Sets of double and triple weights of trees
- Three-way distances
- Triadic distance models: axiomatization and least squares representation
- Two dimensional quantification based on the measure of dissimilarity among three elements
- \(n\)-semimetrics
- \(n\)-way metrics
Cited in
(19)- Treelike families of multiweights
- Binary trees for dissimilarity data
- Dissimilarity vectors of trees are contained in the tropical Grassmannian
- The split decomposition of a \(k\)-dissimilarity map
- Moduli space of families of positive \((n - 1)\)-weights
- On graphlike \(k\)-dissimilarity vectors
- scientific article; zbMATH DE number 3885345 (Why is no real title available?)
- Families of multiweights and pseudostars
- On some relations between 2-trees and tree metrics
- Lassoing and corralling rooted phylogenetic trees
- On the weights of simple paths in weighted complete graphs
- scientific article; zbMATH DE number 6857397 (Why is no real title available?)
- Dissimilarity and similarity measures for comparing dendrograms and their applications
- Reconstructing trees from subtree weights.
- Three-way symbolic tree-maps and ultrametrics
- Weighted graphs with distances in given ranges
- A characterization of dissimilarity families of trees
- Characterization of distance matrices of weighted hypercube graphs and Petersen graphs
- Recognition of Tree Metrics
This page was built for publication: Recognizing treelike \(k\)-dissimilarities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q263358)
