{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:03:43Z","timestamp":1725455023664},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642331213"},{"type":"electronic","value":"9783642331220"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33122-0_15","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T10:43:09Z","timestamp":1346150589000},"page":"190-200","source":"Crossref","is-referenced-by-count":0,"title":["Improved Lower Bounds on the Compatibility of Quartets, Triplets, and Multi-state Characters"],"prefix":"10.1007","author":[{"given":"Brad","family":"Shutters","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sudheer","family":"Vakati","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Fern\u00e1ndez-Baca","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"15_CR1","doi-asserted-by":"publisher","first-page":"1216","DOI":"10.1137\/S0097539793244587","volume":"23","author":"R. Agarwala","year":"1994","unstructured":"Agarwala, R., Fern\u00e1ndez-Baca, D.: A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed. SIAM Journal on Computing\u00a023(6), 1216\u20131224 (1994)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"15_CR2","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/0210030","volume":"10","author":"A.V. Aho","year":"1981","unstructured":"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\u00a010(3), 405\u2013421 (1981)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/3-540-55719-9_80","volume-title":"Automata, Languages and Programming","author":"H. Bodlaender","year":"1992","unstructured":"Bodlaender, H., Fellows, M., Warnow, T.: Two Strikes against Perfect Phylogeny. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol.\u00a0623, pp. 273\u2013283. Springer, Heidelberg (1992)"},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1006\/aama.1995.1020","volume":"16","author":"D. Bryant","year":"1995","unstructured":"Bryant, D., Steel, M.: Extension operations on sets of leaf-labelled trees. Advances in Applied Mathematics\u00a016, 425\u2013453 (1995)","journal-title":"Advances in Applied Mathematics"},{"key":"15_CR5","unstructured":"Buneman, P.: The recovery of trees from measurements of dissimilarity. In: Mathematics in the Archeological and Historical Sciences, pp. 387\u2013395. Edinburgh University Press (1971)"},{"issue":"2","key":"15_CR6","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1111\/j.2044-8317.1981.tb00626.x","volume":"34","author":"H. Colonius","year":"1981","unstructured":"Colonius, H., Schulze, H.H.: Tree structures for proximity data. British Journal of Mathematical and Statistical Psychology\u00a034(2), 167\u2013180 (1981)","journal-title":"British Journal of Mathematical and Statistical Psychology"},{"key":"15_CR7","unstructured":"Dekker, M.C.H.: Reconstruction Methods for Derivation Trees. Master\u2019s thesis, Vrije Universiteit, Amsterdam, Netherlands (1986)"},{"issue":"16","key":"15_CR8","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/j.ipl.2012.06.001","volume":"112","author":"M. Dietrich","year":"2012","unstructured":"Dietrich, M., McCartin, C., Semple, C.: Bounding the maximum size of a minimal definitive set of quartets. Information Processing Letters\u00a0112(16), 651\u2013655 (2012)","journal-title":"Information Processing Letters"},{"issue":"3","key":"15_CR9","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0893-9659(92)90026-6","volume":"5","author":"A. Dress","year":"1992","unstructured":"Dress, A., Steel, M.: Convex tree realizations of partitions. Applied Mathematics Letters\u00a05(3), 3\u20136 (1992)","journal-title":"Applied Mathematics Letters"},{"issue":"1-2","key":"15_CR10","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0025-5564(76)90035-3","volume":"29","author":"G.F. Estabrook","year":"1976","unstructured":"Estabrook, G.F., Johnson, J., McMorris, F.R.: A mathematical foundation for the analysis of cladistic character compatibility. Mathematical Biosciences\u00a029(1-2), 181\u2013187 (1976)","journal-title":"Mathematical Biosciences"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Fern\u00e1ndez-Baca, D.: The Perfect Phylogeny Problem. In: Steiner Trees in Industry, pp. 203\u2013234. Kluwer (2001)","DOI":"10.1007\/978-1-4613-0255-1_6"},{"key":"15_CR12","unstructured":"Fitch, W.M.: Toward finding the tree of maximum parsimony. In: Proceedings of the 8th International Conference on Numerical Taxonomy, pp. 189\u2013230 (1975)"},{"issue":"978","key":"15_CR13","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1086\/283157","volume":"111","author":"W.M. Fitch","year":"1977","unstructured":"Fitch, W.M.: On the problem of discovering the most parsimonious tree. The American Naturalist\u00a0111(978), 223\u2013257 (1977)","journal-title":"The American Naturalist"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Gr\u00fcnewald, 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)","DOI":"10.1093\/oso\/9780199208227.003.0008"},{"issue":"1","key":"15_CR15","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1002\/net.3230210104","volume":"21","author":"D. Gusfield","year":"1991","unstructured":"Gusfield, D.: Efficient algorithms for inferring evolutionary trees. Networks\u00a021(1), 19\u201328 (1991)","journal-title":"Networks"},{"key":"15_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/978-3-642-23038-7_11","volume-title":"Algorithms in Bioinformatics","author":"M. Habib","year":"2011","unstructured":"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.\u00a06833, pp. 116\u2013127. Springer, Heidelberg (2011)"},{"issue":"4","key":"15_CR17","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/S0097539791222171","volume":"23","author":"S. Kannan","year":"1994","unstructured":"Kannan, S., Warnow, T.: Inferring Evolutionary History From DNA Sequences. SIAM Journal on Computing\u00a023(4), 713\u2013737 (1994)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"15_CR18","doi-asserted-by":"publisher","first-page":"1749","DOI":"10.1137\/S0097539794279067","volume":"26","author":"S. Kannan","year":"1997","unstructured":"Kannan, S., Warnow, T.: A fast algorithm for the computation and enumeration of perfect phylogenies. SIAM Journal on Computing\u00a026(6), 1749\u20131763 (1997)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"15_CR19","doi-asserted-by":"publisher","first-page":"1144","DOI":"10.1137\/090776305","volume":"25","author":"F. Lam","year":"2011","unstructured":"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\u00a025(3), 1144\u20131175 (2011)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"Meacham, C.A.: Theoretical and computational considerations of the compatibility of qualitative taxonomic characters. In: Numerical Taxonomy. Nato ASI Series, vol.\u00a0G1, Springer (1983)","DOI":"10.1007\/978-3-642-69024-2_34"},{"key":"15_CR21","unstructured":"Semple, C., Steel, M.: Phylogenetics. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press (2003)"},{"issue":"9","key":"15_CR22","doi-asserted-by":"publisher","first-page":"1226","DOI":"10.1016\/j.aml.2012.02.060","volume":"25","author":"B. Shutters","year":"2012","unstructured":"Shutters, B., Fern\u00e1ndez-Baca, D.: A simple characterization of the minimal obstruction sets for three-state perfect phylogenies. Applied Mathematics Letters\u00a025(9), 1226\u20131229 (2012)","journal-title":"Applied Mathematics Letters"},{"key":"15_CR23","unstructured":"Steel, M.: Personal communications (2012)"},{"issue":"1","key":"15_CR24","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF02618470","volume":"9","author":"M. Steel","year":"1992","unstructured":"Steel, M.: The complexity of reconstructing trees from qualitative characters and subtrees. Journal of Classification\u00a09(1), 91\u2013116 (1992)","journal-title":"Journal of Classification"}],"container-title":["Lecture Notes in Computer Science","Algorithms in Bioinformatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33122-0_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,28]],"date-time":"2024-04-28T19:26:41Z","timestamp":1714332401000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33122-0_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642331213","9783642331220"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33122-0_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}