Hereditarily Optimal Realizations of Consistent Metrics

Andreas Dress^{1,2}, Katharina T. Huber^{3}, Alice Lesser^{4}, and Vincent Moulton^{3}

dress@mis.mpg.de, dress@sibs.ac.cn

{katharina.huber, vincent.moulton}@cmp.uea.ac.uk

alice.lesser@lcb.uu.se

Annals of Combinatorics 10 (1) p.63-76 March, 2006

Abstract:

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.

References:

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/.