Improved Lower Bounds on the Compatibility of Quartets, Triplets, and Multi-state Characters

详细信息    查看全文

• 作者：Brad Shutters (21)
  Sudheer Vakati (21)
  David Fernández-Baca (21)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7534
• 期：1
• 页码：201-213
• 全文大小：213KB
• 参考文献：1. Agarwala, R., Fernández-Baca, D.: A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed. SIAM Journal on Computing?23(6), 1216-224 (1994) CrossRef
  2. Aho, A.V., Sagiv, Y., Szymanski, T.G., Ullman, J.D.: Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM Journal on Computing?10(3), 405-21 (1981) CrossRef
  3. Bodlaender, H., Fellows, M., Warnow, T.: Two Strikes against Perfect Phylogeny. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol.?623, pp. 273-83. Springer, Heidelberg (1992) CrossRef
  4. Bryant, D., Steel, M.: Extension operations on sets of leaf-labelled trees. Advances in Applied Mathematics?16, 425-53 (1995) CrossRef
  5. Buneman, P.: The recovery of trees from measurements of dissimilarity. In: Mathematics in the Archeological and Historical Sciences, pp. 387-95. Edinburgh University Press (1971)
  6. Colonius, H., Schulze, H.H.: Tree structures for proximity data. British Journal of Mathematical and Statistical Psychology?34(2), 167-80 (1981) CrossRef
  7. Dekker, M.C.H.: Reconstruction Methods for Derivation Trees. Master’s thesis, Vrije Universiteit, Amsterdam, Netherlands (1986)
  8. Dietrich, M., McCartin, C., Semple, C.: Bounding the maximum size of a minimal definitive set of quartets. Information Processing Letters?112(16), 651-55 (2012) CrossRef
  9. Dress, A., Steel, M.: Convex tree realizations of partitions. Applied Mathematics Letters?5(3), 3- (1992) CrossRef
  10. Estabrook, G.F., Johnson, J., McMorris, F.R.: A mathematical foundation for the analysis of cladistic character compatibility. Mathematical Biosciences?29(1-2), 181-87 (1976) CrossRef
  11. Fernández-Baca, D.: The Perfect Phylogeny Problem. In: Steiner Trees in Industry, pp. 203-34. Kluwer (2001)
  12. Fitch, W.M.: Toward finding the tree of maximum parsimony. In: Proceedings of the 8th International Conference on Numerical Taxonomy, pp. 189-30 (1975)
  13. Fitch, W.M.: On the problem of discovering the most parsimonious tree. The American Naturalist?111(978), 223-57 (1977) CrossRef
  14. Grünewald, S., Huber, K.T.: Identifying and defining trees. In: Gascuel, O., Steel, M. (eds.) Reconstructing Evolution: New Mathematical and Computational Advances. Oxford University Press (2007)
  15. Gusfield, D.: Efficient algorithms for inferring evolutionary trees. Networks?21(1), 19-8 (1991) CrossRef
  16. Habib, M., To, T.H.: On a Conjecture about Compatibility of Multi-states Characters. In: Przytycka, T.M., Sagot, M.-F. (eds.) WABI 2011. LNCS, vol.?6833, pp. 116-27. Springer, Heidelberg (2011) CrossRef
  17. Kannan, S., Warnow, T.: Inferring Evolutionary History From DNA Sequences. SIAM Journal on Computing?23(4), 713-37 (1994) CrossRef
  18. Kannan, S., Warnow, T.: A fast algorithm for the computation and enumeration of perfect phylogenies. SIAM Journal on Computing?26(6), 1749-763 (1997) CrossRef
  19. Lam, F., Gusfield, D., Sridhar, S.: Generalizing the Splits Equivalence Theorem and Four Gamete Condition: Perfect Phylogeny on Three-State Characters. SIAM Journal on Discrete Mathematics?25(3), 1144-175 (2011) CrossRef
  20. Meacham, C.A.: Theoretical and computational considerations of the compatibility of qualitative taxonomic characters. In: Numerical Taxonomy. Nato ASI Series, vol.?G1, Springer (1983)
  21. Semple, C., Steel, M.: Phylogenetics. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press (2003)
  22. Shutters, B., Fernández-Baca, D.: A simple characterization of the minimal obstruction sets for three-state perfect phylogenies. Applied Mathematics Letters?25(9), 1226-229 (2012) CrossRef
  23. Steel, M.: Personal communications (2012)
  24. Steel, M.: The complexity of reconstructing trees from qualitative characters and subtrees. Journal of Classification?9(1), 91-16 (1992) CrossRef
  
• 作者单位：Brad Shutters (21)
  Sudheer Vakati (21)
  David Fernández-Baca (21)
  
  21. Department of Computer Science, Iowa State University, Ames, IA, 50011, USA
  

文摘

We study a long standing conjecture on the necessary and sufficient conditions for the compatibility of multi-state characters: There exists a function f(r) such that, for any set C of r-state characters, C is compatible if and only if every subset of f(r) characters of C is compatible. We show that for every r?≥-, there exists an incompatible set C of $\lfloor\frac{r}{2}\rfloor\cdot\lceil\frac{r}{2}\rceil + 1$ r-state characters such that every proper subset of C is compatible. Thus, $f(r) \ge \lfloor\frac{r}{2}\rfloor\cdot\lceil\frac{r}{2}\rceil + 1$ for every r?≥-. This improves the previous lower bound of f(r)?≥-em class="a-plus-plus">r given by Meacham (1983), and generalizes the construction showing that f(4)?≥- given by Habib and To (2011). We prove our result via a result on quartet compatibility that may be of independent interest: For every integer n?≥-, there exists an incompatible set Q of $\lfloor\frac{n-2}{2}\rfloor\cdot\lceil\frac{n-2}{2}\rceil + 1$ quartets over n labels such that every proper subset of Q is compatible. We contrast this with a result on the compatibility of triplets: For every n?≥-, if R is an incompatible set of more than n??- triplets over n labels, then some proper subset of R is incompatible. We show this bound is tight by exhibiting, for every n?≥-, a set of n??- triplets over n taxa such that R is incompatible, but every proper subset of R is compatible.