A Short Proof that Phylogenetic Tree Reconstruction by Maximum Likelihood is Hard

Preprint English OPEN
Roch, S.;
  • Subject: Mathematics - Statistics Theory | Quantitative Biology - Populations and Evolution | Computer Science - Computational Complexity | Computer Science - Computational Engineering, Finance, and Science | Mathematics - Probability
    arxiv: Statistics::Computation | Statistics::Methodology

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 exploit... View more
  • References (18)
    18 references, page 1 of 2

    [1] L. Addario-Berry, B. Chor, M. T. Hallett, J. Lagergren, A. Panconesi, and T. Wareham, “Ancestral Maximum Likelihood of Evolutionary Trees is Hard,” Journal of Bioinformatics and Computational Biology, vol. 2, no. 2, pp. 257-271, 2004.

    [2] R. Agarwala, V. Bafna, M. Farach, B. Narayanan, M. Paterson, and M. Thorup, “On the approximability of numerical taxonomy (fitting distances by tree metrics),” SIAM Journal on Computing, vol. 28, pp. 1073-1085, 1999.

    [3] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, Complexity and Approximation, Springer, Berlin, 1999.

    [4] J. Cavender, “Taxonomy with confidence,” Mathematical Biosciences, vol. 40, pp. 271-280, 1978.

    [5] B. Chor and T. Tuller, “Maximum Likelihood of Evolutionary Trees is Hard,” In: Proceedings of the 9th International Conference on Computational Molecular Biology (RECOMB 2005), ACM Press, Cambridge, 2005.

    [6] A. Clementi, and L. Trevisan, “Improved Non-Approximability Results for Minimum Vertex Cover with Density Constraints,” Theor. Comput. Sci., vol. 225, no. 1-2, pp. 113-128, 1999.

    [7] W. Day, D. Jonhson, and D. Sankoff, “The computational complexity of inferring rooted phylogenies by parsimony,” Mathematical Biosciences, vol. 81, pp. 33-42, 1986.

    [8] W. Day and D. Sankoff, “The computational complexity of inferring phylogenies by compatibility,” Systematic Zoology, vol. 35, pp. 224-229, 1986.

    [9] A. W. F. Edwards and L. L. Cavalli-Sforza, “Reconstruction of evolutionary trees,” In: Phenetic and Phylogenetic Classification, eds. V. H. Heywood and J. McNeill, Systematics Association, London, vol. 6, pp. 67-76, 1964.

    [10] J. S. Farris, “A probability model for inferring evolutionary trees,” Systematic Zoology, vol. 22, pp. 250-256, 1973.

  • Metrics
Share - Bookmark