Recognizing treelike k-dissimilarities

DOI10.1007/S00357-012-9115-2zbMATH Open1360.62333arXiv1206.1374OpenAlexW1991581005MaRDI QIDQ263358FDOQ263358

Authors: Sven Herrmann, Andreas Spillner, Katharina T. Huber, Vincent Moulton 

Publication date: 4 April 2016

Published in: Journal of Classification (Search for Journal in Brave)

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.

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

Recommendations

• A characterization of dissimilarity families of trees
• The split decomposition of a \(k\)-dissimilarity map
• On dissimilarity vectors of general weighted trees
• On graphlike \(k\)-dissimilarity vectors
• Reconstructing trees from subtree weights.

zbMATH Keywords

phylogenetic treedissimilaritymetric\(k\)-dissimilarity4-point conditionequidistant treeultrametric condition

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Problems related to evolution (92D15) Trees (05C05) Clustering in the social and behavioral sciences (91C20)

Cites Work

• A tropical interpretation of \(m\)-dissimilarity maps
• A fast algorithm for constructing trees from distance matrices
• Two dimensional quantification based on the measure of dissimilarity among three elements
• An order theoretic framework for overlapping clustering
• Triadic distance models: axiomatization and least squares representation
• \(n\)-semimetrics
• Reconstructing trees from subtree weights.
• Three-way distances
• Phylogenetic diversity over an abelian group
• \(n\)-way metrics
• Basic phylogenetic combinatorics.
• Recognition of Tree Metrics
• A Review of Hierarchical Classification
• A Note on Three-Way Dissimilarities and Their Relationship with Two-Way Dissimilarities
• Sets of double and triple weights of trees

Cited In (19)

• Treelike families of multiweights
• Dissimilarity and similarity measures for comparing dendrograms and their applications
• Families of multiweights and pseudostars
• On graphlike \(k\)-dissimilarity vectors
• The split decomposition of a \(k\)-dissimilarity map
• Title not available (Why is that?)
• On some relations between 2-trees and tree metrics
• Title not available (Why is that?)
• Reconstructing trees from subtree weights.
• Weighted graphs with distances in given ranges
• Dissimilarity vectors of trees are contained in the tropical Grassmannian
• Moduli space of families of positive \((n - 1)\)-weights
• Three-way symbolic tree-maps and ultrametrics
• A characterization of dissimilarity families of trees
• Recognition of Tree Metrics
• Binary trees for dissimilarity data
• Lassoing and corralling rooted phylogenetic trees
• A characterization of distance matrices of weighted cubic graphs and Peterson graphs
• On the weights of simple paths in weighted complete graphs

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)