Retractions of finite distance functions onto tree metrics

Moulton, Vincent ORCID: and Steel, Mike (1999) Retractions of finite distance functions onto tree metrics. Discrete Applied Mathematics, 91 (1-3). pp. 215-233. ISSN 0166-218X

Full text not available from this repository. (Request a copy)


Trees with positively weighted edges induce a natural metric on any subset of vertices, however not every metric is representable in this way. A problem arising in areas of classification, particularly in evolutionary biology, is how to approximate an arbitrary distance function by such a tree metric, 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, but this is lacking in several popular methods, for example (as we show) in “neighbor joining.” However, a continuous transformation, due to Buneman, frequently leads to uninteresting trees. We show how Buneman's construction can be refined so as to lead to more informative trees without sacrificing continuity, and we provide two simple examples of its use. We also provide a sufficient condition for both the Buneman construction, and its refinement to correctly recover the underlying tree.

Item Type: Article
Faculty \ School: Faculty of Science > School of Computing Sciences
Depositing User: Vishal Gautam
Date Deposited: 04 Mar 2011 12:56
Last Modified: 15 Dec 2022 01:57
DOI: 10.1016/S0166-218X(98)00128-0

Actions (login required)

View Item View Item