{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T14:34:19Z","timestamp":1742394859413},"reference-count":18,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2004,6]]},"abstract":"<jats:p>Maximum likelihood (ML) (Neyman, 1971) is an increasingly popular optimality criterion for selecting evolutionary trees. Finding optimal ML trees appears to be a very hard computational task \u2014 in particular, algorithms and heuristics for ML take longer to run than algorithms and heuristics for maximum parsimony (MP). However, while MP has been known to be NP-complete for over 20 years, no such hardness result has been obtained so far for ML.<\/jats:p><jats:p>In this work we make a first step in this direction by proving that ancestral maximum likelihood (AML) is NP-complete. The input to this problem is a set of aligned sequences of equal length and the goal is to find a tree and an assignment of ancestral sequences for all of that tree's internal vertices such that the likelihood of generating both the ancestral and contemporary sequences is maximized. Our NP-hardness proof follows that for MP given in (Day, Johnson and Sankoff, 1986) in that we use the same reduction from VERTEX COVER; however, the proof of correctness for this reduction relative to AML is different and substantially more involved.<\/jats:p>","DOI":"10.1142\/s0219720004000557","type":"journal-article","created":{"date-parts":[[2004,5,27]],"date-time":"2004-05-27T10:23:24Z","timestamp":1085653404000},"page":"257-271","source":"Crossref","is-referenced-by-count":15,"title":["ANCESTRAL MAXIMUM LIKELIHOOD OF EVOLUTIONARY TREES IS HARD"],"prefix":"10.1142","volume":"02","author":[{"given":"LOUIGI","family":"ADDARIO-BERRY","sequence":"first","affiliation":[{"name":"School of Computer Science, McGill University, Montreal, Quebec, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BENNY","family":"CHOR","sequence":"additional","affiliation":[{"name":"School of Computer Science, Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MIKE","family":"HALLETT","sequence":"additional","affiliation":[{"name":"McGill Centre for Bioinformatics, School of Computer Science, McGill University, Montreal, Quebec, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JENS","family":"LAGERGREN","sequence":"additional","affiliation":[{"name":"Stockholm Bioinformatics Center and Department of Numerical Analysis and Computer Science, KTH Royal Institute of Technology Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALESSANDRO","family":"PANCONESI","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Universit\u00e1 di Roma \"La Sapienza\", Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"TODD","family":"WAREHAM","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Memorial University of Newfoundland, St. John's, Newfoundland, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"crossref","unstructured":"D.\u00a0Swofford, Molecular Systematics, 2nd edn., eds. D.\u00a0Hillis, C.\u00a0Moritz and B.\u00a0Mable (Sinauer Associates, Sunderland, MA, 1996)\u00a0pp. 407\u2013514.","DOI":"10.2307\/1447682"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.2307\/2412116"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01734359"},{"key":"rf4","unstructured":"D.\u00a0Sankoff and R.\u00a0Cedergren, Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, eds. D.\u00a0Sankoff and J.\u00a0Kruskal (Addison-Wesley Publishing Company, Reading, MA, 1983)\u00a0pp. 253\u2013263."},{"key":"rf5","unstructured":"D.\u00a0Swofford and W.\u00a0Maddison, Systematics, Historical Ecology, and North American Freshwater Fishes, ed. R.\u00a0Mayden (Stanford University Press, 1992)\u00a0pp. 186\u2013223."},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-8858(82)80004-3"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(86)90161-6"},{"key":"rf9","doi-asserted-by":"crossref","first-page":"1641","DOI":"10.1093\/genetics\/141.4.1641","volume":"141","author":"Yang Z.","journal-title":"Genetics"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02198858"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-307550-5.50005-8"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1093\/oxfordjournals.molbev.a026369"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/18.8.1116"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02458863"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.2307\/2413432"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02618469"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.2307\/2992355"},{"key":"rf18","unstructured":"P. J.\u00a0Waddell and D.\u00a0Penny, Handbook of Symbolic Computation, eds. A. J.\u00a0Locke and C. R.\u00a0Peters (Clarendon Press, Oxford, 1996)\u00a0pp. 53\u201373."},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1006\/mpev.1997.0405"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720004000557","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,28]],"date-time":"2023-04-28T18:56:49Z","timestamp":1682708209000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720004000557"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,6]]},"references-count":18,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2004,6]]}},"alternative-id":["10.1142\/S0219720004000557"],"URL":"https:\/\/doi.org\/10.1142\/s0219720004000557","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"value":"0219-7200","type":"print"},{"value":"1757-6334","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,6]]}}}