{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T06:18:08Z","timestamp":1725603488791},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642230370"},{"type":"electronic","value":"9783642230387"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23038-7_11","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T13:06:43Z","timestamp":1314709603000},"page":"116-127","source":"Crossref","is-referenced-by-count":1,"title":["On a Conjecture about Compatibility of Multi-states Characters"],"prefix":"10.1007","author":[{"given":"Michel","family":"Habib","sequence":"first","affiliation":[]},{"given":"Thu-Hien","family":"To","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"doi-asserted-by":"crossref","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 J. Comput.\u00a023(6) (1994)","key":"11_CR1","DOI":"10.1137\/S0097539793244587"},{"issue":"1","key":"11_CR2","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1142\/S0129054196000038","volume":"7","author":"R. Agarwala","year":"1996","unstructured":"Agarwala, R., Fern\u00e1ndez-Baca, D.: Simple algorithms for perfect phylogeny and triangulating colored graphs. Int. J. Found. Comput. Sci.\u00a07(1), 11\u201322 (1996)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01609870","volume":"3","author":"S. B\u00f6cker","year":"1999","unstructured":"B\u00f6cker, S., Dress, A.W.M., Steel, M.A.: Patching up x-trees. Annals of Combinatorics\u00a03, 1\u201312 (1999)","journal-title":"Annals of Combinatorics"},{"key":"11_CR4","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.L. Bodlaender","year":"1992","unstructured":"Bodlaender, H.L., Fellows, M.R., Warnow, T.: Two strikes against perfect phylogeny. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol.\u00a0623, pp. 273\u2013283. Springer, Heidelberg (1992)"},{"key":"11_CR5","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P. Buneman","year":"1974","unstructured":"Buneman, P.: A characterization of rigid circuit graphs. Discrete Mathematics\u00a09, 205\u2013212 (1974)","journal-title":"Discrete Mathematics"},{"issue":"3","key":"11_CR6","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.A.: Convex tree realizations of partitions. Applied Mathematics Letters\u00a05(3), 3\u20136 (1992)","journal-title":"Applied Mathematics Letters"},{"key":"11_CR7","first-page":"189","volume-title":"The Eighth International Conference on Numerical Taxonomy","author":"W.M. Fitch","year":"1975","unstructured":"Fitch, W.M.: Toward finding the tree of maximum parsimony. In: Estabrook, G.F. (ed.) The Eighth International Conference on Numerical Taxonomy, pp. 189\u2013220. W. H. Freeman and Company, San Francisco (1975)"},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1086\/283157","volume":"11","author":"W.M. Fitch","year":"1977","unstructured":"Fitch, W.M.: On the problem of discovering the most parsimonious tree. American Naturalist\u00a011, 223\u2013257 (1977)","journal-title":"American Naturalist"},{"doi-asserted-by":"crossref","unstructured":"Johnson, C., Estabrook, G., McMorris, F.: A mathematical formulation for the analysis of cladistic character compatibility. Math Bioscience\u00a029 (1976)","key":"11_CR9","DOI":"10.1016\/0025-5564(76)90035-3"},{"issue":"3","key":"11_CR10","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1006\/jagm.1995.1047","volume":"19","author":"M.C. Golumbic","year":"1995","unstructured":"Golumbic, M.C., Kaplan, H., Shamir, R.: Graph sandwich problems. J. Algorithms\u00a019(3), 449\u2013473 (1995)","journal-title":"J. Algorithms"},{"key":"11_CR11","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, 19\u201328 (1991)","journal-title":"Networks"},{"issue":"3","key":"11_CR12","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1016\/j.jcss.2004.12.009","volume":"70","author":"D. Gusfield","year":"2005","unstructured":"Gusfield, D.: Optimal, efficient reconstruction of root-unknown phylogenetic networks with constrained and structured recombination. J. Comput. Syst. Sci.\u00a070(3), 381\u2013398 (2005)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"11_CR13","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1089\/cmb.2009.0200","volume":"17","author":"D. Gusfield","year":"2010","unstructured":"Gusfield, D.: The multi-state perfect phylogeny problem with missing and removable data: Solutions via integer-programming and chordal graph theory. J. of Computational Biology\u00a017(3), 383\u2013399 (2010)","journal-title":"J. of Computational Biology"},{"issue":"10","key":"11_CR14","doi-asserted-by":"publisher","first-page":"1247","DOI":"10.1089\/cmb.2006.0137","volume":"14","author":"D. Gusfield","year":"2007","unstructured":"Gusfield, D., Bansal, V., Bafna, V., Song, Y.S.: A decomposition theory for phylogenetic networks and incompatible characters. Journal of Computational Biology\u00a014(10), 1247\u20131272 (2007)","journal-title":"Journal of Computational Biology"},{"issue":"4","key":"11_CR15","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1287\/ijoc.1040.0099","volume":"16","author":"D. Gusfield","year":"2004","unstructured":"Gusfield, D., Eddhu, S., Langley, C.H.: The fine structure of galls in phylogenetic networks. INFORMS Journal on Computing\u00a016(4), 459\u2013469 (2004)","journal-title":"INFORMS Journal on Computing"},{"issue":"1","key":"11_CR16","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1142\/S0219720004000521","volume":"2","author":"D. Gusfield","year":"2004","unstructured":"Gusfield, D., Eddhu, S., Langley, C.H.: Optimal, efficient reconstruction of phylogenetic networks with constrained recombination. J. Bioinformatics and Computational Biology\u00a02(1), 173\u2013214 (2004)","journal-title":"J. Bioinformatics and Computational Biology"},{"key":"11_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/978-3-540-73545-8_8","volume-title":"Computing and Combinatorics","author":"D. Gusfield","year":"2007","unstructured":"Gusfield, D., Frid, Y., Brown, D.: Integer programming formulations and computations solving phylogenetic and population genetic problems with missing or genotypic data. In: Lin, G. (ed.) COCOON 2007. LNCS, vol.\u00a04598, pp. 51\u201364. Springer, Heidelberg (2007)"},{"key":"11_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/978-3-642-21458-5_13","volume-title":"Combinatorial Pattern Matching","author":"M. Habib","year":"2011","unstructured":"Habib, M., Stacho, J.: Unique perfect phylogeny is np-hard. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.\u00a06661, pp. 132\u2013146. Springer, Heidelberg (2011)"},{"issue":"2","key":"11_CR19","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0025-5564(90)90123-G","volume":"98","author":"J. Hein","year":"1990","unstructured":"Hein, J.: Reconstructing evolution of sequences subject to recombination using parsimony. Mathematical Biosciences\u00a098(2), 185\u2013200 (1990)","journal-title":"Mathematical Biosciences"},{"key":"11_CR20","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1137\/S0895480102416696","volume":"18","author":"K.T. Huber","year":"2005","unstructured":"Huber, K.T., Moulton, V., Steel, M.: Four characters suffice to convexly define a phylogenetic tree. SIAM Journal on Discrete Mathematics\u00a018, 835\u2013843 (2005)","journal-title":"SIAM Journal on Discrete Mathematics"},{"doi-asserted-by":"crossref","unstructured":"Kannan, S., Warnow, T.: Inferring evolutionary history from dna sequences. SIAM J. Comput.\u00a023(4) (1994)","key":"11_CR21","DOI":"10.1137\/S0097539791222171"},{"unstructured":"Kannan, S., Warnow, T.: A fast algorithm for the computation and enumeration of perfect phylogenies when the number of character states is fixed. In: SODA, pp. 595\u2013603 (1995)","key":"11_CR22"},{"key":"11_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-3-642-04241-6_18","volume-title":"Algorithms in Bioinformatics","author":"F. Lam","year":"2009","unstructured":"Lam, F., Gusfield, D., Sridhar, S.: Generalizing the four gamete condition and splits equivalence theorem: Perfect phylogeny on three state characters. In: Salzberg, S.L., Warnow, T. (eds.) WABI 2009. LNCS, vol.\u00a05724, pp. 206\u2013219. Springer, Heidelberg (2009)"},{"unstructured":"McMorris, F.R., Warnow, T., Wimer, T.: Triangulating vertex colored graphs. In: SODA, pp. 120\u2013127 (1993)","key":"11_CR24"},{"key":"11_CR25","series-title":"NATO ASI","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1007\/978-3-642-69024-2_34","volume-title":"Numerical Taxonomy","author":"C.A. Meacham","year":"1983","unstructured":"Meacham, C.A.: Theoretical and computational considerations of the compatibility of qualitative taxonomic characters. In: Felsenstein, J. (ed.) Numerical Taxonomy. NATO ASI, vol.\u00a0G1, pp. 304\u2013314. Springer, Heidelberg (1983)"},{"key":"11_CR26","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"C. Semple","year":"2003","unstructured":"Semple, C., Steel, M.: Phylogenetics. Oxford University Press, Oxford (2003)"},{"key":"11_CR27","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1006\/aama.2001.0772","volume":"28","author":"C. Semple","year":"2002","unstructured":"Semple, C., Steel, M.: Tree reconstruction from multi-state characters. Advances in Applied Mathematics\u00a028, 169\u2013184 (2002)","journal-title":"Advances in Applied Mathematics"},{"key":"11_CR28","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, 91\u2013116 (1992)","journal-title":"Journal of Classification"},{"issue":"1","key":"11_CR29","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1089\/106652701300099119","volume":"8","author":"L. Wang","year":"2001","unstructured":"Wang, L., Zhang, K., Zhang, L.: Perfect phylogenetic networks with recombination. Journal of Computational Biology\u00a08(1), 69\u201378 (2001)","journal-title":"Journal of Computational Biology"}],"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-23038-7_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,10]],"date-time":"2024-04-10T18:29:20Z","timestamp":1712773760000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23038-7_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642230370","9783642230387"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23038-7_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}