<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume10 Issue1" %>
Mapping Edge Sets to Splits in Trees: the Path Index and Parsimony
Andreas Dress1,2 and Mike Steel3
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 Plank Institute for Mathematics in the Sciences, Leipzig, Germany
3Allan Wilson Centre for Molecular Ecology and Evolution, University of Canterbury, Christchurch, New Zealand
Annals of Combinatorics 10 (1) p.77-96 March, 2006
AMS Subject Classification: 05C05, 05C25, 92D15
Associated to any finite tree, there are simple vector spaces over Z2 and linear transformations between them that relate collections of edge-disjoint paths, sets of leaves of even cardinality, and bipartitions of the leaf set. In this paper, we use this connection to introduce and study an apparently new integer-valued invariant, the `path index' of a tree. In the case of trivalent (or `binary') trees, this index has an interesting recursive description that allows its easy calculation implying in particular that the path index of such a tree never exceeds one quarter of the number of its leaves and coincides with that number exclusively for the (unique!) trivalent tree with four leaves. We then show how our algebraic perspective has some other uses — for example, it relates to Hadamard conjugation first described by Mike Hendy, and it provides a way to study a combinatorial optimization problem considered in phylogenetics called the small maximum parsimony problem.
Keywords: X-trees, paths, maximum parsimony, short exact sequence


1. J. Felsenstein, Inferring Phylogenies, Sinauer Press, 2004.

2. W.M. Fitch, Towards defining the course of evolution: minimum change for a specific tree topology, Syst. Zool. 20 (1971) 406--416.

3. F. Harary, Graph Theory, Addison-Wesley Publishing Company, 1969.

4. J.A. Hartigan, Minimum mutation fits to a given tree, Biometrics 29 (1973) 53--65.

5. M.D. Hendy, The relationship between simple evolutionary tree models and observable sequence data, Syst. Zool. 38 (1989) 310--321.

6. K.T. Huber, Recovering trees from well-separated multi-state characters, Discrete Math. 278 (2004) 151--164.

7. S. Maclane and G. Birkoff, Algebra, 2nd Ed., Macmillan Publishing Co. Inc., New York, 1979.

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

9. M.A. Steel, Distributions on bicoloured evolutionary trees, Ph.D. Thesis, Massey University, Palmerston North, New Zealand, 1989.

10. C. Tuffley and M.A. Steel, Links between maximum likelihood and maximum parsimony under a simple model of site substitution, Bull. Math. Biol. 59 (3) (1997) 581--607.