A Caltech Library Service

Affine and Projective Tree Metric Theorems

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.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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:
URLURL TypeDescription Paper ReadCube access
Pachter, Lior0000-0002-9164-6231
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.
Funding AgencyGrant Number
NSF Graduate Research FellowshipUNSPECIFIED
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
Record Number:CaltechAUTHORS:20170303-162557287
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:74745
Deposited By: George Porter
Deposited On:06 Mar 2017 16:23
Last Modified:11 Nov 2021 05:29

Repository Staff Only: item control page