<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume10 Issue1" %>
Hereditarily Optimal Realizations of Consistent Metrics
Andreas Dress1,2, Katharina T. Huber3, Alice Lesser4, and Vincent Moulton3
1Department of Combinatorics and Geometry, CAS-MPG Partner Institute for Computational Biology, Shanghai Instituts for Biological Sciences, Chinese Academy of Sciences, 320 Yue Yang Road, Shanghai, China
2Max-Planck-Institut fuer Mathematik in den Naturwissenschaften Inselstrasse 22 - 26 D-04103 Leipzig, Germany
dress@mis.mpg.de, dress@sibs.ac.cn
3School of Computing Sciences, University of East Anglia, Norwich, NR4 7TJ, UK
{katharina.huber, vincent.moulton}@cmp.uea.ac.uk
4The Linnaeus Centre for Bioinformatics, Uppsala University, Box 598, 751 24 Uppsala, Sweden.
Annals of Combinatorics 10 (1) p.63-76 March, 2006
AMS Subject Classification: 05C12, 05C90, 52C99
One of the main problems in phylogenetics is to find good approximations of metrics by weighted trees. As an aid to solving this problem, it could be tempting to consider optimal realizations of metrics — the guiding principle being that, the (necessarily unique) optimal realization of a tree metric is the weighted tree that realizes this metric. And, although optimal realizations of arbitrary metrics are, in general, not trees, but rather weighted networks, one could still hope to obtain a phylogenetically informative representation of a given metric, maybe even more informative than the best approximating tree. However, optimal realizations are not only difficult to compute, they may also be non-unique. Here we focus on one possible way out of this dilemma: hereditarily optimal realizations. These are essentially unique, and can be described in a rather explicit way. In this paper, we recall what a hereditarily optimal realization of a metric is and how it is related to the 1-skeleton of the tight span of that metric, and we investigate under what conditions it coincides with this 1-skeleton. As a consequence, we will show that hereditarily optimal realizations for consistent metrics, a large class of phylogentically relevant metrics, can be computed in a straight-forward fashion.
Keywords: tight span, finite metric space, optimal realization, weakly compatible


1. I. Althöfer, On optimal realizations of finite metric spaces by graphs, Discrete Comput. Geom. 3 (1988) 103--122.

2. H.J. Bandelt and A. Dress, A canonical decomposition theory for metrics on a finite set, Adv. Math. 92 (1992) 47--105.

3. H.J. Bandelt, P. Forster, B. Sykes, and M. Richards, Mitochondrial portraits of human population using median networks, Genetics 141 (1995) 743--753.

4. P. Buneman, The recovery of trees from measures of dissimilarity, In: Mathematics in the Archaeological and Historical Sciences, F. Hodson et al., Eds., Edinburgh University Press, (1971) pp. 387--395.

5. A. Dress, Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces, Adv. Math. 53 (1984) 321--402.

6. A. Dress, Towards a classification of transitive group actions on finite metric spaces, Adv. Math. 74 (1989) 163--189.

7. A. Dress, M. Hendy, K.T. Huber, and V. Moulton, On the number of vertices and edges in the Buneman graph, Ann. Comb. 1 (1997) 329--337.

8. A. Dress, K.T. Huber, J. Koolen, and V. Moulton, Six points suffice: how to check for metric consistency, European J. Combin. 22 (2001) 465--474.

9. A. Dress, K.T. Huber, and V. Moulton, Some variations on a theme by Buneman, Ann. Comb. 1 (1997) 339--352.

10. A. 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) 299--311.

11. A. Dress, K.T. Huber, and V. Moulton, Hereditarily optimal realizations of metrics: why are they relevant in phylogenetic analysis and how does one compute them?, In: Algebraic Combinatorics and Applications, A. Betten et al., Eds., Springer-Verlag, (2001) pp. 110--117.

12. A. Dress, K.T. Huber, and V. Moulton, An explicit computation of the injective hull of certain finite metric spaces in terms of their associated Buneman complex, Adv. Math. 168 (2002) 1--28.

13. A. Dress, V. Moulton, and W. Terhalle, T-theory: an overview, European J. Combin. 17 (1996) 161--175.

14. S.L. Hakimi and S.S.Yau, Distance matrix of a graph and its realizability, Quart. Appl. Math. 22 (1964) 305--317.

15. K.T. Huber, V. Moulton, P. Lockhart, and A. Dress, Pruned median networks: a technique for reducing the complexity of median networks, Mol. Phylogenet. Evol. 19 (2001) 302--310.

16. D. Huson, SplitsTree: a program for analyzing and visualizing evolutionary data, Bioinformatics 14 (1998) 68--73.

17. W. Imrich, J.M.S. Simões-Pereira, and C. Zamfirescu, On optimal emdeddings of metrics in graphs, J. Combin. Theory Ser. B 36 (1984) 1--5.

18. V. Klee and P. Kleinschmidt, Convex polytopes and related complexes, In: Handbook of Combinatorics, Vol. 1, R. Graham, M. Grotschel, and L. Lovasz, Eds., The MIT Press, (1995) pp. 875--917.

19. C. Semple and S. Steel, Phylogenetics, Oxford University Press, 2003.

20. J.M.S. Simões-Pereira and C. Zamfirescu, Submatrices of non-tree-realizable distance matrices, Linear Algebra Appl. 44 (1982) 1--17.

21. P.Winkler, The complexity of metric realization, SIAM J. Discrete Math. 1 (1988) 552--559.

22. K. Zaretsky, Reconstruction of a tree from the distances between its pendant vertices, Uspekhi Mat. Nauk (Russian Mathematical Surveys) 20 (1965) 90--92 (in Russian).

23. The following list details programs for computing polytopes and polyhedra: http://www.math.tu-berlin.de/polymake/, http://www.qhull.org/.