{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:45:48Z","timestamp":1725795948529},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319075655"},{"type":"electronic","value":"9783319075662"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07566-2_9","type":"book-chapter","created":{"date-parts":[[2014,6,12]],"date-time":"2014-06-12T03:50:31Z","timestamp":1402545031000},"page":"79-88","source":"Crossref","is-referenced-by-count":0,"title":["The Worst Case Complexity of Maximum Parsimony"],"prefix":"10.1007","author":[{"given":"Amir","family":"Carmel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Noa","family":"Musa-Lempel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dekel","family":"Tsur","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Ziv-Ukelson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"9_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":"5","key":"9_CR2","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1016\/j.crvi.2005.02.002","volume":"328","author":"O. Bastien","year":"2005","unstructured":"Bastien, O., Roy, S., Mar\u00e9chal, \u00c9.: Construction of non-symmetric substitution matrices derived from proteomes with biased amino acid distributions. Comptes Rendus Biologies\u00a0328(5), 445\u2013453 (2005)","journal-title":"Comptes Rendus Biologies"},{"issue":"12","key":"9_CR3","doi-asserted-by":"publisher","first-page":"1719","DOI":"10.1093\/oxfordjournals.molbev.a025898","volume":"15","author":"M.S. Blouin","year":"1998","unstructured":"Blouin, M.S., Yowell, C.A., Courtney, C.H., Dame, J.B.: Substitution bias, rapid saturation, and the use of mtDNA for nematode systematics. Molecular Biology and Evolution\u00a015(12), 1719\u20131727 (1998)","journal-title":"Molecular Biology and Evolution"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fellows, M.R., Warnow, T.J.: Two strikes against perfect phylogeny. Springer (1992)","DOI":"10.1007\/3-540-55719-9_80"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"Cavalli-Sforza, L.L., Edwards, A.W.: Phylogenetic analysis. Models and estimation procedures. American Journal of Human Genetics 19(3 pt. 1), 233 (1967)","DOI":"10.2307\/2406616"},{"issue":"2","key":"9_CR6","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1093\/sysbio\/35.2.224","volume":"35","author":"W.H. Day","year":"1986","unstructured":"Day, W.H., Sankoff, D.: Computational complexity of inferring phylogenies by compatibility. Systematic Biology\u00a035(2), 224\u2013229 (1986)","journal-title":"Systematic Biology"},{"key":"9_CR7","unstructured":"Felsenstein, J., Felenstein, J.: Inferring phylogenies, vol.\u00a02. Sinauer Associates Sunderland (2004)"},{"issue":"4","key":"9_CR8","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1093\/sysbio\/20.4.406","volume":"20","author":"W.M. Fitch","year":"1971","unstructured":"Fitch, W.M.: Toward defining the course of evolution: minimum change for a specific tree topology. Systematic Biology\u00a020(4), 406\u2013416 (1971)","journal-title":"Systematic Biology"},{"issue":"1","key":"9_CR9","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0196-8858(82)80004-3","volume":"3","author":"L.R. Foulds","year":"1982","unstructured":"Foulds, L.R., Graham, R.L.: The steiner problem in phylogeny is np-complete. Advances in Applied Mathematics\u00a03(1), 43\u201349 (1982)","journal-title":"Advances in Applied Mathematics"},{"issue":"6","key":"9_CR10","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1007\/BF01840889","volume":"18","author":"T. Gojobori","year":"1982","unstructured":"Gojobori, T., Ishii, K., Nei, M.: Estimation of average number of nucleotide substitutions when the rate of substitution varies with nucleotide. J. of Molecular Evolution\u00a018(6), 414\u2013422 (1982)","journal-title":"J. of Molecular Evolution"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Grosswald, E.: Bessel Polynomials (1978)","DOI":"10.1007\/BFb0063135"},{"issue":"2","key":"9_CR12","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0025-5564(82)90027-X","volume":"59","author":"M. Hendy","year":"1982","unstructured":"Hendy, M., Penny, D.: Branch and bound algorithms to determine minimal evolutionary trees. Mathematical Biosciences\u00a059(2), 277\u2013290 (1982)","journal-title":"Mathematical Biosciences"},{"key":"9_CR13","unstructured":"McMorris, F.R., Warnow, T.J., Wimer, T.: Triangulating vertex colored graphs. In: Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 120\u2013127. Society for Industrial and Applied Mathematics (1993)"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"M\u00fcller, T., Rahmann, S., Rehmsmeier, M.: Non-symmetric score matrices and the detection of homologous transmembrane proteins. Bioinformatics 17(suppl. 1), S182\u2013S189 (2001)","DOI":"10.1093\/bioinformatics\/17.suppl_1.S182"},{"key":"9_CR15","unstructured":"Ochiumi, N., Kanazawa, F., Yanagida, M., Horibe, Y.: On the average number of nodes covering a given number of leaves in an unordered binary tree. J. of Combinatorial Mathematics and Combinatorial Computing 76, 3 (2011)"},{"issue":"4","key":"9_CR16","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/S0022-5193(05)80104-3","volume":"142","author":"F. Rodriguez","year":"1990","unstructured":"Rodriguez, F., Oliver, J.L., Marin, A., Medina, J.R.: The general stochastic model of nucleotide substitution. J. of Theoretical Biology\u00a0142(4), 485\u2013501 (1990)","journal-title":"J. of Theoretical Biology"},{"issue":"1","key":"9_CR17","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1137\/0128004","volume":"28","author":"D. Sankoff","year":"1975","unstructured":"Sankoff, D.: Minimal mutation trees of sequences. SIAM Journal on Applied Mathematics\u00a028(1), 35\u201342 (1975)","journal-title":"SIAM Journal on Applied Mathematics"},{"issue":"3","key":"9_CR18","first-page":"269","volume":"1","author":"F. Tajima","year":"1984","unstructured":"Tajima, F., Nei, M.: Estimation of evolutionary distance between nucleotide sequences. Molecular Biology and Evolution\u00a01(3), 269\u2013285 (1984)","journal-title":"Molecular Biology and Evolution"},{"issue":"3","key":"9_CR19","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1093\/genetics\/98.3.641","volume":"98","author":"N. Takahata","year":"1981","unstructured":"Takahata, N., Kimura, M.: A model of evolutionary base substitutions and its application with special reference to rapid change of pseudogenes. Genetics\u00a098(3), 641\u2013657 (1981)","journal-title":"Genetics"},{"issue":"5","key":"9_CR20","first-page":"814","volume":"9","author":"K. Tamura","year":"1992","unstructured":"Tamura, K.: The rate and pattern of nucleotide substitution in drosophila mitochondrial DNA. Molecular Biology and Evolution\u00a09(5), 814\u2013825 (1992)","journal-title":"Molecular Biology and Evolution"},{"issue":"3","key":"9_CR21","first-page":"512","volume":"10","author":"K. Tamura","year":"1993","unstructured":"Tamura, K., Nei, M.: Estimation of the number of nucleotide substitutions in the control region of mitochondrial DNA in humans and chimpanzees. Molecular Biology and Evolution\u00a010(3), 512\u2013526 (1993)","journal-title":"Molecular Biology and Evolution"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07566-2_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T21:11:41Z","timestamp":1649365901000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07566-2_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319075655","9783319075662"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07566-2_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}