Kleinman, Aaron and Harel, Matan and Pachter, Lior (2013) Affine and Projective Tree Metric Theorems. Annals of Combinatorics, 17 (1). pp. 205-228. ISSN 0218-0006. doi:10.1007/s00026-012-0173-2. https://resolver.caltech.edu/CaltechAUTHORS:20170303-162557287
![]() |
PDF
- Submitted Version
See Usage Policy. 916kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170303-162557287
Abstract
The tree metric theorem provides a combinatorial four-point condition that characterizes dissimilarity maps derived from pairwise compatible split systems. A related weaker four point condition characterizes dissimilarity maps derived from circular split systems known as Kalmanson metrics. The tree metric theorem was first discovered in the context of phylogenetics and forms the basis of many tree reconstruction algorithms, whereas Kalmanson metrics were first considered by computer scientists, and are notable in that they are a non-trivial class of metrics for which the traveling salesman problem is tractable. We present a unifying framework for these theorems based on combinatorial structures that are used for graph planarity testing. These are (projective) PC-trees, and their affine analogs, PQ-trees. In the projective case, we generalize a number of concepts from clustering theory, including hierarchies, pyramids, ultrametrics, and Robinsonian matrices, and the theorems that relate them. As with tree metrics and ultrametrics, the link between PC-trees and PQ-trees is established via the Gromov product.
Item Type: | Article | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| |||||||||||||||
ORCID: |
| |||||||||||||||
Additional Information: | © 2012 Springer Basel. Received March 4, 2011. We thank Laxmi Parida for introducing us to the applications of PQ-trees in biology during a visit to UC Berkeley in 2008. Thanks also to an anonymous reviewer whose careful reading of an initial draft of the paper helped us greatly. AK was funded by an NSF graduate research fellowship. | |||||||||||||||
Funders: |
| |||||||||||||||
Subject Keywords: | hierarchy; Gromov product; Kalmanson metric; Robinsonian metric; PC-tree; PQ-treep; hylogenetics; pyramid; ultrametric | |||||||||||||||
Issue or Number: | 1 | |||||||||||||||
Classification Code: | Mathematics Subject Classification: 05C05, 92B10 | |||||||||||||||
DOI: | 10.1007/s00026-012-0173-2 | |||||||||||||||
Record Number: | CaltechAUTHORS:20170303-162557287 | |||||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20170303-162557287 | |||||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||||||||
ID Code: | 74745 | |||||||||||||||
Collection: | CaltechAUTHORS | |||||||||||||||
Deposited By: | George Porter | |||||||||||||||
Deposited On: | 06 Mar 2017 16:23 | |||||||||||||||
Last Modified: | 11 Nov 2021 05:29 |
Repository Staff Only: item control page