# Tight Spans of Finite Metric Spaces

## Introduction

To each finite metric space M one can assign a polyhedral complex which captures essential features of M, the tight span T(M). This name was introduced by Bandelt and Dress, but these objects already showed up earlier as the injective envelope of a metric space in the work of Isbell.

The probably easiest examples of finite metric spaces are the tree-like ones: Just take a finite tree, that is, a connected graph without cycles with non-negative weights (or lengths) assigned to the edges. We want to define a metric space on the nodes of the tree. Since shortest paths between any two nodes in a tree are unique, the lengths on the edges define a metric.

Being the bounded subcomplex of an unbounded polyhedron, T(M) is necessarily contractible. Hence, T(M) is one-dimensional if and only if T(M) is a tree. Moreover, if M is tree-like then T(M) is a metrically correct copy of the tree which defined M. In a way, T(M) can be seen as the space of all possible trees which fit best to M.

Interesting examples of finite metric spaces arise in computational biology, more precisely in phylogenetics, as follows: Starting out with a bunch of DNA sequences of individual plants or animals (called taxa) these DNA sequences are first aligned such that it is then possible to compute the (editing) distance between any two taxa. This distance function is only slightly more sophisticated than counting the non-matching bases in the aligned DNA sequences. It naturally defines a finite metric space.

The phylogenetic problem is to (re-)construct the genealogy of a set of taxa. Tight spans now provide one approach to the phylogenetic problem.

## An Example

 Let us consider six species of bees of which are given (very short) fragments of already aligned DNA data. In fact, only 677 bases were taken. The (symmetric) editing distance matrix looks as listed below. The picture of the honeybee (apis mellifera) on the right is taken from Wikipedia.

### The Distance Matrix

 A.andrenof A.mellifer A.dorsata A.cerana A.florea A.koschev A.andrenof 0.0 0.090103395 0.10339734 0.09601182 0.0044313148 0.07533235 A.mellifer 0.090103395 0.0 0.09305761 0.090103395 0.09305761 0.10044313 A.dorsata 0.10339734 0.09305761 0.0 0.116691284 0.106351554 0.10339734 A.cerana 0.09601182 0.090103395 0.116691284 0.0 0.098966025 0.098966025 A.florea 0.0044313148 0.09305761 0.106351554 0.098966025 0.0 0.07828656 A.koschev 0.07533235 0.10044313 0.10339734 0.098966025 0.07828656 0.0

This data set stems from the example file bees.nex of the SplitsTree program of Huson and Bryant. The names of the bees (apis ...) are truncated to eight characters.

### The Tight Span of Six Bees

It is important to keep in mind that the tight span, in general, is a high-dimensional geometric object which is very difficult to visualize.

Our software system polymake allows to deal with and to compute tight spans. Further it can also visualize tight spans by feeding suitable input to various Viewers. However, as already disclaimed in the previous paragraph, these images need a bit of explanation. Here is a polymake file describing the tight span of the six bees. Only the sections `METRIC` and `TAXA` are provided as input; the rest is computed by polymake.

 VISUAL_BOUNDED_GRAPH of tight span VISUAL_TIGHT_SPAN of tight span

The big picture on the left shows a picture of the tight span such that its combinatorial features are emphasized. In particular, it is a difficult image to derive biological information from. The picture is produced with POV-RAY via polymake. The upper right picture is an interactive applet showing the same information as the big image using JavaView, also via polymake. The lower right applet tries to be metrically as correct as possible.

The combinatorial output is obtained via polymake's function `VISUAL_BOUNDED_GRAPH`, while the metric output comes from `VISUAL_TIGHT_SPAN`. In both cases the red points are vertices of the tight span related to taxa, while the yellow ones are non-taxon vertices. In a successful phylogenetic reconstruction they might biologically be interpreted as common ancestors.

The edge colors in both combinatorial outputs indicate the maximum dimension of a bounded face containing that edge. The bluer the edge the higher the dimension. In an example with six taxa, the tight span is either 2-dimensional or 3-dimensional (this was shown by Develin). Our bee related tight span here is 3-dimensional. A red edge means that there is no bounded face of higher dimension containing this edge, purple indicates that there is a 2-face but not no 3-face containing the edge, and blue means that there is a 3-face containing this edge.

The following can be read off the metric picture: The data suggests that A.florea descends from A.andrenof, while all other relationships are more distant.

## References

1. H.-J. Bandelt and A. Dress: Reconstructing the shape of a tree from observed dissimilarity data, Adv. in Appl. Math. 7 (1986), no. 3, 309-343; MR0858908 (87k:05060).
2. M. Develin: Dimensions of tight spans, Preprint math.CO/0407317.
3. A. W. M. Dress: Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces, Adv. in Math. 53 (1984), no. 3, 321-402; MR0753872 (86j:05053).
4. A. W. M. Dress, K. T. Huber, and V. Moulton: A comparison between two distinct continuous models in projective cluster theory: the median and the tight-span construction, Ann. Comb. 2 (1998), no. 4, 299-311; MR1774971 (2002f:91078).
5. E. Gawrilow and M. Joswig: polymake: a framework for analyzing convex polytopes, Polytopes---combinatorics and computation (Oberwolfach, 1997), 43-73, Birkhäuser, Basel, 2000; MR1785292 (2001f:52033).
6. E. Gawrilow, M. Joswig, T. Rörig, and N. Witte: Drawing polytopal graphs with polymake. Comput. Vis. Sci. 13 (2010), no. 2, 99-110.
7. S. Herrmann and M. Joswig: Splitting polytopes. Münster J. Math. 1 (2008), 109-141.
8. H. Hirai: A geometric study of the split decomposition. Discrete Comput. Geom. 36 (2006), no. 2, 331-361.
9. D. H. Huson and D. Bryant, Application of Phylogenetic Networks in Evolutionary Studies, Mol. Biol. Evol., 23(2):254-267, 2006.
10. J. R. Isbell: Six theorems about injective metric spaces, Comment. Math. Helv. 39 (1964), 65-76; MR0182949 (32 #431).
11. B. Sturmfels and J. Yu: Classification of six point metrics, The Electronic Journal of Combinatorics, 11 (2004) R44. Website