Retractions of finite distance functions onto tree metrics
type: Item
instance of: scholarly article
title: Retractions of finite distance functions onto tree metrics
zbMATH Open document ID: 0914.05016
DOI: 10.1016/S0166-218X(98)00128-0
published in: Discrete Applied Mathematics
publication date: 1999-06-06T00:00:00Z
review text: A problem arising in areas of classification, particularly in evolutionary biology, is how to approximate an arbitrary distance function by a tree metric, induced by trees with positively weighted edges, and thereby estimate the underlying tree that generated the data. Such transformations, from distances to tree metrics (and thereby to edge-weighted trees) should have some basic properties such as continuity. It is shown that this is lacking for the commonly used neighbor-joining method which is not a retraction. A continuous transformation, due to Buneman [see \textit{F. Hodson, D. Kendall} and \textit{P. Tautu} (eds.), Mathematics in the archaeological and historical sciences, Edinburgh University Press, Edinburgh, 387-395 (1971)] is refined so as to lead to more informative trees without sacrificing continuity and two simple examples of the use of the refined Buneman map, including an application to biological data are provided. A sufficient condition for both the Buneman construction, and its refinement to correctly recover the underlying tree is also provided.
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 92B10
zbMATH DE Number: 1271074
zbMATH Keywords: trees
zbMATH Keywords: retraction
zbMATH Keywords: isolation index
zbMATH Keywords: 4-point condition
zbMATH Keywords: tree metric
zbMATH Keywords: edge-weighted tree
zbMATH Keywords: neighbor joining
zbMATH Keywords: Buneman retraction
author: Vincent Moulton
author: Mike Steel
describes a project that uses: SplitsTree
MaRDI profile type: Publication
cites work: Q4364581
cites work: Recognition of Tree Metrics
cites work: Reconstructing the shape of a tree from observed dissimilarity data
cites work: A canonical decomposition theory for metrics on a finite set
cites work: Q4865834
cites work: A polynomial time algorithm for constructing the refined Buneman tree
cites work: Analyzing and visualizing sequence and distance data using SPLITSTREE
cites work: \(T\)-theory: An overview
cites work: Q4228475
cites work: Q3772406
cites work: Efficient algorithms for inferring evolutionary trees
cites work: The Construction of Hierarchic and Non-Hierarchic Classifications
cites work: Q3859782
cites work: Q3349837
cites work: Q5530466
full work available at URL: s0166-218x(98)00128-0
OpenAlex ID: W2020005532
description: scientific article; zbMATH DE number 1271074