Constructing Perfect Phylogenies and Proper Triangulations for Three-State Characters

1. Agarwala, R., Fernandez-Baca, D.: A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed. SIAM Journal on Computing 23, 1216–1224 (1994)

   Article  MATH  Google Scholar 

2. Berry, A., Bordat, J.-P., Heggernes, P., Simonet, G., Villanger, Y.: A wide-range algorithm for minimal triangulation from an arbitrary ordering. Journal of Algorithms, 33–66 (2006)

   Google Scholar 

3. Blair, J.R.S., Peyton, B.W.: An introduction to chordal graphs and clique trees. IMA Volumes in Mathematics and its Applications 56, 1–27 (1993)

   Article  MATH  Google Scholar 

4. Bodlaender, H., Fellows, M., Warnow, T.: Two strikes against perfect phylogeny. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol. 623, pp. 273–283. Springer, Heidelberg (1992)

   Chapter  Google Scholar 

5. Buneman, P.: A characterization of rigid circuit graphs. Discrete Math. 9, 205–212 (1974)

   Article  MATH  Google Scholar 

6. Dirac, G.A.: Abh. Math. Sem. Univ. Hamburg (1961)

   Google Scholar 

7. Dress, A., Steel, M.: Convex tree realizations of partitions. Applied Math. Letters 5, 3–6 (1993)

   Article  MATH  Google Scholar 

8. Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol. 57. North-Holland Publishing Co., Amsterdam (2004)

   MATH  Google Scholar 

9. Gusfield, D.: Efficient algorithms for inferring evolutionary trees. Networks 21, 19–28 (1991)

   Article  MATH  Google Scholar 

10. Gusfield, D.: The multi-state perfect phylogeny problem with missing and removable data. J. Computational Biology (preliminary version in Research in Computational Molecular Biology (RECOMB 2009)), 383–399 (2010)

    Google Scholar 

11. Ho, C.W., Lee, R.C.T.: Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs. Inf. Process. Lett. 28, 301–309 (1988)

    Article  MATH  Google Scholar 

12. Kannan, S., Warnow, T.: Inferring evolutionary history from DNA sequences. SIAM J. on Computing 23, 713–737 (1994)

    Article  MATH  Google Scholar 

13. Kannan, S., Warnow, T.: A fast algorithm for the computation and enumeration of perfect phylogenies. SIAM Journal on Computing 26, 1749–1763 (1995)

    Article  MATH  Google Scholar 

14. Kloks, T., Kratsch, D., Spiurad, J.: Treewidth and pathwidth of cocomparability graphs of bounded dimension. Technical Report, Eindhoven University (1993)

    Google Scholar 

15. Lam, F., Gusfield, D., Sridhar, S.: Generalizing the four gamete condition and splits equivalence theorem: Perfect phylogeny on three state characters. To appear in SIAM J. Discrete Mathematics (2011)

    Google Scholar 

16. Parra, A., Scheffler, P.: How to use the minimal separators of a graph for its chordal triangulation. In: Fülöp, Z. (ed.) ICALP 1995. LNCS, vol. 944, pp. 123–134. Springer, Heidelberg (1995)

    Chapter  Google Scholar 

17. Parra, A., Scheffler, P.: Characterizations and algorithmic applications of chordal graph embeddings. Discrete Applied Mathematics, 171–188 (1997)

    Google Scholar 

18. Semple, C., Steel, M.: Phylogenetics. Oxford University Press, Oxford (2003)

    MATH  Google Scholar 

19. Steel, M.A.: The complexity of reconstructing trees from qualitative characters and subtrees. Journal of Classification 9, 91–116 (1992)

    Article  MATH  Google Scholar 

20. Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13, 566–579 (1984)

    Article  MATH  Google Scholar 

Download references