<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 11 Issue 1" %>
Some Uses of the Farris Transform in Mathematics and Phylogenetics—A Review
A. Dress1, K.T. Huber2, V. Moulton2
1Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22-26, D 04103 Leipzig, Germany
2School of Computing Sciences, University of East Anglia, Norwich, NR4 7TJ, United Kingdom
{katharina.huber, vincent.moulton}@cmp.uea.ac.uk
Annals of Combinatorics 11 (1) p.1-37 March, 2007
AMS Subject Classification: 05C12, 0502, 05C90, 92B99
In 1970, Farris introduced a procedure that can be used to transform a tree metric into an ultra metric. Since its discovery, Farris' procedure has been used extensively within phylogenetics where it has become commonly known as the Farris transform. Remarkably, the Farris transform has not only been rediscovered several times within phylogenetics, but also in other fields. In this paper, we will review some of its various properties and uses.
    The paper is divided into four parts and, altogether, 12 sections. In the first part, we introduce a standardized scheme for classifying those dissimilarity mappings to which the Farris transform can be applied — scheme that has evolved over the years, but has apparently not been spelled out before in sufficient detail. In the second part, we will discuss how a straightforward generalization of the Farris transform naturally arises in T-Theory. The third part describes how this generalized Farris transform can be used to approximate dissimilarities by tree metrics. And in the final part, we describe some further, “non-standard” applications of the Farris transform.
Keywords: Farris transform, T-theory, Gromov product, Gromov transform, covariance mapping, additive map, Linnean map, tree metric, ultra-metric


1. R. Agarwala, V. Bafna, M. Farach, B. Narayanan, M. Paterson, and M. Thorup, On the approximability of numerical taxonomy: fitting distances by tree metrics, In: Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York (1996) pp. 365-372.

2. J. Apresjan, An algorithm for constructing clusters from a distance matrix, Mashinnyi Perevod: Prikladnaja Lingvistika 9 (1966) 3-18.

3. E. Baake, What can and cannot be inferred from pairwise sequence comparisons?, Math. Biosci. 154 (1998) 1-21.

4. H.-J. Bandelt, Recognition of tree metrics, SIAM J. Discrete Math. 3 (1990) 1-6.

5. H.-J. Bandelt and A. Dress, Weak hierarchies associated with similarity measures — an additive clustering technique, Bull. Math. Biol. 51 (1989) 133-166.

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

7. H.-J. Bandelt and M. Steel, Symmetric matrices representable by weighted trees over a cancellative abelian monoid, SIAM J. Discrete Math. 8 (1995) 517-525.

8. J.-P. Barthélémy and A. Guénoche, Trees and Proximity Representations, John Wiley & Sons, Ltd., Chichester, 1991.

9. S. Böcker and A. Dress, Recovering symbolically dated, rooted trees from symbolic ultrametrics, Adv. Math. 138 (1) (1998) 105-125.

10. B. Bowditch, Notes on Gromov's hyperbolicity criterion for path metric spaces, In: Group Theory from a Geometric Viewpoint, E. Ghys et al. Eds., World Sci. Publ., River Edge, NJ (1991) pp. 64-167.

11. G. Brossier, Approximation des dissimilarités par des arbres additifs, Math. Sci. Hum. 91 (1985) 5-21.

12. D. Bryant and A. Dress, Lineraly independent split systems, Europ. J. Combin., in press.

13. D. Bryant and V. Moulton, Consistency of the neighbor-net algorithm for constructing phylogenetic networks, submitted.

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

15. V. Chepoi and B. Fichet: l —Approximation via Subdominants, J. Math. Psych. 44 (2000) 600-616.

16. M. Chrobak and L. Lamore, Generosity helps or an 11-competitive algorithm for three servers, J. Algorithms 16 (1994) 234-263.

17. M. Coornaert and A. Papadopoulos, Symbolic Dynamics and Hyperbolic Groups, Lecture Notes in Mathematics, Vol. 1539, Springer-Verlag, Berlin, 1993.

18. G.M. Crippen and T.F. Havel, Distance Geometry and Molecular Conformation, Chemometrics Series, Vol. 15, John Wiley & Sons, Inc., New York, 1988.

19. C. Darwin, On the Origin of Species by Means of Natural Selection, or the Preservation of Favoured Races in the Struggle for Life, 1859.

20. W.H.E. Day, Computational complexity of inferring phylogenies from dissimilarity matrices, Bull. Math. Biol. 29 (9) (1987) 461-467.

21. M. Develin and B. Sturmfels, Tropical Convexity, Doc. Math. 9 (2004) 1-27.

22. M. Develin and B. Sturmfels, Erratum for “Tropical Convexity”, Doc. Math. 9 (2004) 205- 206.

23. M.M. Deza and M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics, Vol. 15, Springer-Verlag, Berlin, 1997.

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

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

26. A. Dress, Proper Gromov transforms of metrics are metrics, Appl. Math. Lett. 15 (2002) 995-999.

27. A. Dress, Towards a theory of holistic clustering, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. Vol. 37, Amer. Math. Soc., Providence, (1997) pp. 271-289.

28. A. Dress, B. Holland, K.T. Huber, J.H. Koolen, V. Moulton, and J. Weyer-Menkhoff, D Additive and D ultra-additive maps, Gromov's trees, and the Farris transform, Discrete Appl. Math. 146 (2005) 51-73.

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

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

31. M. Farach, S. Kannan, and T.Warnow, A robust model for finding optimal evolutionary trees, Algorithmica 13 (1995) 155-179.

32. J.S. Farris, On the phenetic approach to vertebrate classification, In: Major Patterns in Vertebrate Evolution, M.K. Hecht, P.C. Goody, and B.M. Hecht. Eds., Plenum Press, New York, (1977) pp. 823-850.

33. J.S. Farris, The information content of the phylogenetic system, Systematic Zoology (continued by Syst. Biol.) 28 (1979) 483-519.

34. J.S. Farris, A.G. Kluge, and M.J. Eckardt, A numerical approach to phylogenetic systematics, Systematic Zoology (continued by Syst. Biol.) 19 (1970) 172-189.

35. J. Felsenstein, Inferring Phylogenies, Sinauer Associates Sunderland, Mass., USA, 2004.

36. M. Gromov, Hyperbolic groups, In: Essays in Group Theory, Math. Sci. Res. Inst. Publ., Vol. 8, Springer, New York, (1987) pp. 75-263.

37. E. Haeckel, Generelle Morphologie der Organismen, 1866.

38. J.A. Hartigan, Clustering Algorithms, JohnWiley & Sons, New York-London-Sydney, 1975.

39. J. Isbell, Six theorems about injective metric spaces, Comment. Math. Helv. 39 (1964) 65-76.

40. N. Jardine, Towards a general theory of clustering, Biometrics 25 (1969) 609-610.

41. L.C. Klotz and R.L. Blanken, A practical method for calculating evolutionary trees from sequence data, J. Theoret. Biol. 91 (1981) 261-272.

42. J. Koolen, V. Moulton, and U. Toenges, A classication of the six-point prime metrics, Europ. J. Combin. 21 (2000) 815-829.

43. P.J. Lockhart, A.E. Meyer, and D. Penny, Testing the phylogeny of swordtail fishes using split decomposition and spectral analysis, J. Mol. Evol. 41 (1995) 666-674.

44. K. Menger, Géométrie Général, Mém. des Sci. Math. 124, Gauthier-Villars, Paris, 1954.

45. A. Parker-Rhodes and R. Needham, A reduction method for non-arithmetic data, and its application to thesauric translation, In: Information Processing: Proceedings of the International Conference on Information Processing, Paris, (1960) pp. 321-325.

46. N. Saitou and M. Nei, The neighbor-joining method: a new method for reconstructing phylogenetic trees, Mol. Biol. Evol. 4 (1987) 406-425.

47. C. Semple and M. Steel, Tree representations of non-symmetric, group-valued proximities, Adv. Appl. Math. 23 (1999) 300-321.

48. C. Semple and M. Steel, Phylogenetics, Oxford Lecture Series in Mathematics and its Applications, 24, Oxford University Press, Oxford, 2003.

49. M. Steel, Recovering a tree from the leaf colourations it generates under a Markov model, Appl. Math. Lett. 7 (1994) 19-24.

50. G. Young and A.S. Householder, Discussion of a set of points in terms of their mutual distances, Psychometrica 3 (1938) 19-22.

51. http://www.math.tu-berlin.de/polymake/.

52. The following web pages contain interesting material regarding Ray, Quirinus, de Tournefort, and Linnaeus, respectively: www.ucmp.berkeley.edu/history/ray.html, es.rice.edu/ES/humsoc/Galileo/Catalog/Files/bachmann.html, es.rice.edu/ES/humsoc/Galileo/Catalog/Files/tournfrt.html, www.ucmp.berkeley.edu/history/linnaeus.html.