Roch Sebastien
Department of Statistics, University of California, 367 Evans Hall, Berkeley, CA 94720-3860, USA.
IEEE/ACM Trans Comput Biol Bioinform. 2006 Jan-Mar;3(1):92-4. doi: 10.1109/TCBB.2006.4.
Maximum likelihood is one of the most widely used techniques to infer evolutionary histories. Although it is thought to be intractable, a proof of its hardness has been lacking. Here, we give a short proof that computing the maximum likelihood tree is NP-hard by exploiting a connection between likelihood and parsimony observed by Tuffley and Steel.
最大似然法是推断进化历史最广泛使用的技术之一。尽管人们认为它难以处理，但一直缺乏其难度的证明。在此，我们通过利用图夫利和斯蒂尔观察到的似然性与简约性之间的联系，给出一个简短的证明，即计算最大似然树是NP难的。
