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.
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.
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.
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
TAXA are provided as input; the rest is computed by
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
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
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.