Retractions of finite distance functions onto tree metrics

Tools

Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435 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)

Abstract

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
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018) Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Depositing User:	Vishal Gautam
Date Deposited:	04 Mar 2011 12:56
Last Modified:	16 Jun 2023 23:52
URI:	https://ueaeprints.uea.ac.uk/id/eprint/23956
DOI:	10.1016/S0166-218X(98)00128-0

Actions (login required)

View Item