Retractions of finite distance functions onto tree metrics

Vincent Moulton, Mike Steel

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)215-233
Number of pages19
JournalDiscrete Applied Mathematics
Issue number1-3
Publication statusPublished - Jan 1999

Cite this