<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume10 Issue1" %>
A Novel Insight into the Perfect Phylogeny Problem
S. Grünewald1 and K.T. Huber2
1AllanWilson Centre for Molecular Ecology and Evolution and Department of Mathematics and Statistics, University of Canterbury, Private Bag 4800, Christchurch, New Zealand
2School of Computing Sciences, University of East Anglia, Norwich, NR4 7TJ, United Kingdom
Annals of Combinatorics 10 (1) p.97-109 March, 2006
AMS Subject Classification: 05C05, 92D15

One of the classical problem in computational biology is the character compatibility problem or perfect phylogeny problem. A standard formulation of this problem in terms of two closely related questions is the following. Given a data set consisting of a finite set X and a set R of partitions induced on X by a set of characters. Is R compatible, that is, does there exist an evolutionary tree that represents (in a well-defined sense) the data? If this is the case, is this tree unique? A fundamental result in phylogenetics states that the answer to the former of the two questions is yes precisely if the partition intersection graph IR associated to R can be made chordal by obeying a certain rule.

The main insight from this paper is that the relation graph GR associated to a set R of partitions may provide a key for deciding whether such a chordalization of IR exists. To prove our results, we introduce an extension of the concept of the partition intersection graph associated to R using GR.
Keywords: perfect phylogeny problem, relation graph, compatibility, partition intersection graph, strictly represent, properly represent


1. R. Argawala and D. Fernándes-Baca, A polynomial type algorithm for the perfect phylogeny problem when the number of characters is fixed, SIAM J. Comput. 23 (6) (1994) 1216--1224.

2. H.J. Bandelt, Phylogenetic networks, Verhandl. Naturwiss. Vereins Hamburg 34 (1991) 51--57.

3. H.J. Bandelt, P. Forster, B.C. Sykes, and M.B. Richards, Mitochondrial portraits of human population using median networks, Genetics 141 (1995) 743--753.

4. H.J. Bandelt, K.T. Huber, and V. Moulton, Quasi-median graphs from sets of partitions, Discrete Appl. Math. 122 (2002) 23--35.

5. J.P. Barthélemy, From copair hypergraphs to median graphs with latent vertices, Discrete Math. 76 (1989) 9--28.

6. H. Bodlaender, M. Fellows, and T. Warnow, Two strikes against perfect phylogeny, In: Proceedings of the 19th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Sciences, Springer Verlag, (1992) pp. 273--283.

7. M. Bordewich, K.T. Huber, and C. Semple, Identifying phylogenetic trees, submitted.

8. P. Buneman, A characterization of rigid circuit graphs, Discrete Math. 9 (1974) 205--212.

9. A. Dress, K. Huber, and V. Moulton, Some variations on a theme by Buneman, Ann. Comb. 1 (1997) 339--352.

10. A. Dress, M. Hendy, K. Huber, and V. Moulton, On the number of vertices and edges of the Buneman graph, Ann. Comb. 1 (1997) 329--337.

11. A. Dress, V. Moulton, and M. Steel, Trees, taxonomy, and strongly compatible multi-state characters, Adv. in Appl. Math. 19 (1997) 1--30.

12. A. Dress and M. Steel, Convex tree realizations of partitions, Appl. Math. Lett. 5 (3) (1992) 3--6.

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

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

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

16. K.T. Huber and V. Moulton, The relation graph, Discrete Math. 244 (1-3) (2002) 153--166.

17. K.T. Huber, V. Moulton, P. Lockhart, and A. Dress, Pruned median networks: a technique for reducing the complexity of median networks, Mol. Phylogenet. Evol. 19 (2) (2001) 302--310.

18. K.T. Huber, V. Moulton, and C. Semple, Replacing cliques by stars, Discrete Appl. Math. 143 (2004) 194--203.

19. K.T. Huber, V. Moulton, and M. Steel, Four characters suffice to convexly define a phylogenetic tree, SIAM J. Discrete Math., in press.

20. S. Kannan and T. Warnow, Inferring evolutionary histories from DNA sequences, SIAM J. Comput. 23 (3) (1994) 713--737.

21. F.R. McMorris and C.A. Meacham, Partition intersection graphs, Ars Combin. 16 (B) (1983) 135--138.

22. C.A. Meacham, Theoretical and computational considerations of the compatibility of qualitative taxonomic characters, In: Numerical Taxonomy, NATO ASI Series, Vol. G1, Springer- Verlag, (1983) pp. 304--314.

23. F.R. McMorris, T. Warnow, and T. Wimer, Triangulating vertex-colored graphs, SIAM J. Discrete Math. 7 (1994) 296--306.

24. C. Semple and M. Steel, Tree reconstruction from multi-state characters, Adv. in Appl. Math. 28 (2) (2002) 169--184.

25. C. Semple and M. Steel, A characterization for a set of partial partitions to define an X-tree, Discrete Math. 247 (2002) 169--186.

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

27. M.A. Steel, The complexity of reconstructing trees from qualitative characters and subtrees, J. Classification 9 (1992) 91--116.