{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:53:01Z","timestamp":1725558781058},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540200765"},{"type":"electronic","value":"9783540397632"}],"license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39763-2_16","type":"book-chapter","created":{"date-parts":[[2010,6,25]],"date-time":"2010-06-25T16:49:30Z","timestamp":1277484570000},"page":"202-215","source":"Crossref","is-referenced-by-count":3,"title":["Ancestral Maximum Likelihood of Evolutionary Trees Is Hard"],"prefix":"10.1007","author":[{"given":"Louigi","family":"Addario-Berry","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benny","family":"Chor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mike","family":"Hallett","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Lagergren","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessandro","family":"Panconesi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Todd","family":"Wareham","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"16_CR1","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/BF02458863","volume":"49","author":"W. Day","year":"1987","unstructured":"Day, W.: Computational Complexity of Inferring Phylogenies from Dissimilarity Matrices. Bulletin of Mathematical Biology\u00a049(4), 461\u2013467 (1987)","journal-title":"Bulletin of Mathematical Biology"},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0025-5564(86)90161-6","volume":"81","author":"W. Day","year":"1986","unstructured":"Day, W., Johnson, D., Sankoff, D.: The Computational Complexity of Inferring Rooted Phylogenies by Parsimony. Mathematical Biosciences\u00a081, 33\u201342 (1986)","journal-title":"Mathematical Biosciences"},{"issue":"2","key":"16_CR3","doi-asserted-by":"publisher","first-page":"224","DOI":"10.2307\/2413432","volume":"35","author":"W. Day","year":"1986","unstructured":"Day, W., Sankoff, D.: Computational Complexity of Inferring Phylogenies by Compatability. Systematic Zoology\u00a035(2), 224\u2013299 (1986)","journal-title":"Systematic Zoology"},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/BF01734359","volume":"17","author":"J. Felsenstein","year":"1981","unstructured":"Felsenstein, J.: Evolutionary Trees from DNA Sequences: A Maximum Likelihood Approach. Journal of Molecular Evolution\u00a017, 368\u2013376 (1981)","journal-title":"Journal of Molecular Evolution"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"406","DOI":"10.2307\/2412116","volume":"20","author":"W. Fitch","year":"1971","unstructured":"Fitch, W.: Towards defining the course of evolution: minimum change for a specific tree topology. Systematic Zoology\u00a020, 406\u2013416 (1971)","journal-title":"Systematic Zoology"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0196-8858(82)80004-3","volume":"3","author":"L. Foulds","year":"1982","unstructured":"Foulds, L., Graham, R.: The Steiner problem in phylogeny is NP-complete. Advances in Applied Mathematics\u00a03, 43\u201349 (1982)","journal-title":"Advances in Applied Mathematics"},{"issue":"4","key":"16_CR7","doi-asserted-by":"publisher","first-page":"345","DOI":"10.2307\/2992355","volume":"39","author":"N. Goldman","year":"1990","unstructured":"Goldman, N.: Maximum likelihood inference of phylogenetic trees, with special reference to a Poisson process model of DNA substitution and to parsimony analyses. Systematic Zoology\u00a039(4), 345\u2013361 (1990)","journal-title":"Systematic Zoology"},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0025-5564(82)90125-0","volume":"60","author":"R. Graham","year":"1982","unstructured":"Graham, R., Foulds, L.: Unlikelihood that minimal phylogenies for a realistic biological study can be constructed in reasonable computational time. Mathematical Biosciences\u00a060, 133\u2013142 (1982)","journal-title":"Mathematical Biosciences"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/BF02198858","volume":"42","author":"M. Koshi","year":"1996","unstructured":"Koshi, M., Goldstein, R.: Probabilistic reconstruction of ancestral protein sequences. Journal of Molecular Evolution\u00a042, 313\u2013320 (1996)","journal-title":"Journal of Molecular Evolution"},{"key":"16_CR10","first-page":"1","volume-title":"Statistical Decision Theory and Related Topics","author":"J. Neyman","year":"1971","unstructured":"Neyman, J.: Molecular studies of evolution: A source of novel statistical problems. In: Gupta, S., Jackel, Y. (eds.) Statistical Decision Theory and Related Topics, pp. 1\u201327. Academic Press, New York (1971)"},{"issue":"6","key":"16_CR11","doi-asserted-by":"crossref","first-page":"890","DOI":"10.1093\/oxfordjournals.molbev.a026369","volume":"17","author":"T. Pupko","year":"2000","unstructured":"Pupko, T., Pe\u2019er, I., Shamir, R., Graur, D.: A Fast Algorithm for Joint Reconstruction of Ancestral Amino Acid Sequences. Molecular Biology and Evolution\u00a017(6), 890\u2013896 (2000)","journal-title":"Molecular Biology and Evolution"},{"issue":"8","key":"16_CR12","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1093\/bioinformatics\/18.8.1116","volume":"18","author":"T. Pupko","year":"2002","unstructured":"Pupko, T., Pe\u2019er, I., Hasegawa, M., Graur, D., Friedman, N.: A branch-and-bound algorithm for the inference of ancestral amino-acid sequences when the replacement rate varies among sites: Application to the evolution of five gene families. Bioinformatics\u00a018(8), 1116\u20131123 (2002)","journal-title":"Bioinformatics"},{"key":"16_CR13","first-page":"253","volume-title":"Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison","author":"D. Sankoff","year":"1983","unstructured":"Sankoff, D., Cedergren, R.: Simultaneous comparison of three or more sequences related by a tree. In: Sankoff, D., Kruskal, J. (eds.) Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, pp. 253\u2013263. Addison-Wesley Publishing Company, Reading (1983)"},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02618469","volume":"9","author":"M. Steel","year":"1992","unstructured":"Steel, M.: The complexity of reconstructing trees from qualitative characters and subtrees. Journal of Classification\u00a09, 71\u201390 (1992)","journal-title":"Journal of Classification"},{"key":"16_CR15","first-page":"186","volume-title":"Systematics, Historical Ecology, and North American Freshwater Fishes","author":"D. Swofford","year":"1992","unstructured":"Swofford, D., Maddison, W.: Parsimony, Character-State Reconstructions, and Evolutionary Inferences. In: Mayden, R. (ed.) Systematics, Historical Ecology, and North American Freshwater Fishes, pp. 186\u2013223. Stanford University Press, Stanford (1992)"},{"key":"16_CR16","first-page":"407","volume-title":"Molecular Systematics","author":"D. Swofford","year":"1996","unstructured":"Swofford, D., Olsen, G., Waddell, P., Hillis, D.: Phylogenetic Inference. In: Hillis, D., Moritz, C., Mable, B. (eds.) Molecular Systematics, 2nd edn., pp. 407\u2013514. Sinauer Associates, Sunderland (1996)","edition":"2"},{"key":"16_CR17","unstructured":"Wareham, T.: On the Computational Complexity of Inferring Evolutionary Trees. Technical Report 93-01, Department of Computer Science, Memorial University of Newfoundland (1993)"},{"key":"16_CR18","doi-asserted-by":"crossref","first-page":"1641","DOI":"10.1093\/genetics\/141.4.1641","volume":"141","author":"Z. Yang","year":"1995","unstructured":"Yang, Z., Kumar, S., Nei, M.: A new method of inference of ancestral nucleotide and amino acid sequences. Genetics\u00a0141, 1641\u20131650 (1995)","journal-title":"Genetics"}],"container-title":["Lecture Notes in Computer Science","Algorithms in Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39763-2_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T01:35:52Z","timestamp":1635557752000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39763-2_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540200765","9783540397632"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39763-2_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}