<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 1" %>
A Subdivision Approach to Maximum Parsimony
Trevor C. Bruen1 and David Bryant2
1Department of Mathematics, University of California, Berkeley, CA 94720, USA
2Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand
Annals of Combinatorics 12 (1) p.45-51 March, 2008
AMS Subject Classification:68R10, 68R05, 68Q25, 92D15
Determining an optimal phylogenetic tree using maximum parsimony, also referred to as the Steiner tree problem in phylogenetics, is NP hard. Here we provide a new formulation for this problem which leads to an analytical and linear time solution when the dimensionality (sequence length, or number of characters) is at most two. This new formulation of the problem provides a direct link between the maximum parsimony problem and the maximum compatibility problem via the intersection graph. The solution for the “two character case” has numerous practical applications in phylogenetics, some of which are discussed.
Keywords: maximum parsimony, compatibility, character subdivision, Steiner tree


1. E. Althaus and R. Naujoks, Computing Steiner minimum trees in Hamming metric, In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, ACM, New York, (2006) 172-181.

2. D. Gusfield, Efficient algorithms for inferring evolutionary trees, Networks 21 (1) (1991) 19-28.

3. B.R. Holland, K.T. Huber, D. Penny, and V. Moulton, The minmax squeeze: guaranteeing a minimal tree for population data, Mol. Biol. Evol. 22 (2) (2005) 235-242.

4. J.P. Huelsenbeck and F. Ronquist, MRBAYES: bayesian inference of phylogenetic trees, Bioinform. 17 (8) (2001) 754-755.

5. M. Steel and D. Penny, Maximum parsimony and the phylogenetic information in multistate characters, In: Parsimony, Phylogeny and Genomics, V. Albert Ed., Oxford University Press, (2005) pp. 163-178.

6. L.R. Foulds and R.L. Graham, The steiner problem in phylogeny is NP-complete, Adv. Appl. Math. 3 (1) (1982) 43-49.

7. R. Karp, Reducibility among combinatorial problems, In: Complexity of Computer Computations, R.E. Miller and J.W. Thatcher Eds., Plenum Press, New York, (1972) pp. 85-104.

8. M.R. Garey and D.S. Johnson, Computers and Intractibility, W.H. Freeman & Co., 1979.

9. G.F. Estabrook and F.R. McMorris, When are two qualitative taxonomic characters compatible?, J. Math. Biol. 4 (1977) 195-200.

10. D.F. Robinson and L.R. Foulds, Comparison of phylogenetic trees, Math. Biosci. 53 (1981) 131-147.

11. J. Felsenstein, Evolutionary trees from DNA sequences: a maximum likelihood approach, J. Mol. Evol. 17 (6) (1981) 368-376.

12. T. Bruen, H. Philippe, and D. Bryant, A simple and robust statistical test to detect the presence of recombination, Genetics 172 (2006) 2665-2681.

13. J.H. Camin and R.R. Sokal, A method for deducing branching sequences in phylogeny, Evolution 19 (3) (1965) 311-326.

14. G.F. Estabrook and L. Landrum, A simple test for the possible simultaneous evolutionary divergence of two amino acid positions, Taxon 24 (5/6) (1975) 609-613.

15. D. Penny and M. Hendy, Estimating the reliability of evolutionary trees, Mol. Biol. Evol. 3 (5) (1986) 403-417.

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