<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 2" %>
Split Decomposition over an Abelian Group Part 1: Generalities
Andreas Dress1, 2
1Department for Combinatorics and Geometry, CAS-MPG Partner Institute and Key Lab for Computational Biology, Shanghai Institutes for Biological Sciences, Chinese Academy of Sciences, 320 Yue Yang Road, Shanghai 200031, P.R.China
2Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22 -26, D 04103 Leipzig, Germany
dress@sibs.ac.cn, dress@mis.mpg.de
Annals of Combinatorics 13 (2) pp.199-232 June, 2009
AMS Subject Classification: 05C05, 92D15
Split-decomposition theory deals with relations between $\R$-valued split systems and metrics. Here, we generalize (parts of) this theory, considering group-valued split systems that take their values in an arbitrary abelian group, and replacing metrics by certain, appropriately defined maps (some of which appear to exhibit a decidedly {\em algebraic} flavour). In the second and the third parts of this series of papers, the main results of split-decomposition theory will be established within this conceptual framework.
Keywords: splits, split decomposition, split systems, set systems, group-valued split systems, group-valued set systems, phylogenetic analysis, metrics, bilinear maps, groupoid


1. J. Backelin and A.W.M. Dress, The kernel of the split map, in preparation.

2. J. Backelin and S. Linusson, Parity splits by triple point distances in X-trees, Ann. Combin. 10 (2006) 1–-18.

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

4. H.-J. Bandelt and A.W.M. Dress, A canonical split decomposition theory for metrics on a nite set, Adv. Math. 92 (1) (1992) 47–-105.

5. H.-J. Bandelt and A.W.M. Dress, Reconstructing the shape of a tree from observed dissimilarity data, Adv. Appl. Math. 7 (3) (1986) 309–-343.

6. H.-J. Bandelt and A.W.M. Dress, Split decomposition: a new and useful approach to phylogenetic analysis of distance data, Mol. Phylogenet Evol. 1 (3) (1992) 242-–252.

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

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

9. G.M. Barker, Phylogenetic diversity: a quantitative framework for measurement of priority and achievement in biodiversity conservation, Biol. J. Linnean Soc. 76 (2) (2002) 165–-194.

10. S. B¨ocker and A.W.M. Dress, Recovering symbolically dated, rooted trees from symbolic ultrametrics, Adv. Math. 138 (1) (1998) 105–-125.

11. H. Colonius and H.H. Schultze, Trees constructed from empirical relations, Braunschweiger Berichte aus dem Institut fuer Psychologie 1, Braunschweig, 1977.

12. C. Devauchelle, A. Dress, A. Grossmann, S. Gr¨unewald, and A. Henaut, Constructing Hierarchical set systems, Ann. Combin. 8 (4) (2004) 441–-456.

13. A.W.M. Dress, Split decomposition over an abelian group, part 2: group-valued split systems with weakly compatible support, Discrete Appl. Math. 157 (10) 2349-–2360.

14. A.W.M. Dress, Split decomposition over an abelian group, part 3: group-valued split systems with compatible support, Manuscript.

15. A.W.M. Dress and P. Erd¨os, X-trees and weighted quartet systems, Ann. Combin. 7 (2) (2003) 155–-169.

16. A.W.M. Dress et al., D additive and D ultra-additive maps, Gromov's trees, and the Farris transform, Discrete Appl. Math. 146 (1) (2005) 51–-73.

17. A.W.M. Dress, K. Huber, and V. Moulton, Some uses of the Farris transform in mathematics and phylogenetics —a review, Ann. Combin. 11 (1) (2007) 1-–37.

18. A.W.M. Dress and M.A. Steel, Mapping edge sets to splits in trees: the path index and parsimony, Ann. Combin. 10 (1) (2006) 77–-96.

19. A.W.M. Dress and M.A. Steel, Phylogenetic diversity over an abelian group, 11 (2) (2007) 143–-160.

20. S.N. Evans and T.P. Speed, Invariants of some probability models used in phylogenetic inference, Ann. Statist. 21 (1) (1993) 355-–377.

21. D.P. Faith, Conservation evaluation and phylogenetic diversity, Biol. Conserv. 61 (1) (1992) 1-–10.

22. J.S. Farris, On the phenetic approach to vertebrate classication, 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.

23. J.S. Farris, The information content of the phylogenetic system, Sys. Zool. 28 (4) (1979) 483-–519.

24. J.S. Farris, A.G. Kluge, and M.J. Eckardt, A numerical approach to phylogenetic systematics, Sys. Zool. 19 (2) (1970) 172–-189.

25. J. Felsenstein, Inferring Phylogenies, Sinauer Press, Sunderland, 2004.

26. W.M. Fitch and E. Margoliash, Construction of phylogenetic trees, Science 155 (1967) 279-–284.

27. W.J. Heiser and M. Bennani, Triadic distance models: aximomatization and least squares representation, J. Math. Psych. 41 (2) (1997) 189-–206.

28. S. Joly and Le Calv´e, Three-way distances, J. Classication 12 (2) (1995) 191-–205.

29. B. Korte, L. Lov´asz, and R. Schrader, Greedoids, Algorithms and Combinatorics, Springer-Verlag, Berlin, 1991.

30. L. Pachter and D. Speyer, Reconstructing trees from subtree weights, Appl. Math. Lett. 17 (6) (2004) 615–-621.

31. C. Semple and M.A. Steel, Cyclic permutations and evolutionary trees, Adv. Appl. Math. 32 (4) (2004) 669-–680.

32. C. Semple and M.A. Steel, Phylogenetics, Oxford University Press, Oxford, 2003.

33. M.A. Steel, Phylogenetic diversity and the greedy algorithm, Syst. Biol. 54 (4) (2005) 527-–529.