A Subdivision Approach to Maximum Parsimony

Trevor C. Bruen^{1} and David Bryant^{2}

tbruen@math.berkeley.edu

d.bryant@auckland.ac.nz

Annals of Combinatorics 12 (1) p.45-51 March, 2008

Abstract:

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.
References:

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.