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

*Roch, S.*;

- Subject: Mathematics - Statistics Theory | Quantitative Biology - Populations and Evolution | Computer Science - Computational Complexity | Computer Science - Computational Engineering, Finance, and Science | Mathematics - Probabilityarxiv: Statistics::Computation | Statistics::Methodology

- References (18) 18 references, page 1 of 2
- 1
- 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 No metrics available

- Download from

- Cite this publication