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

ABSTRACT

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.

REFERENCES

• 1: [1] L. Addario-Berry, B. Chor, M.T. Hallett, J. Lagergren, A. Panconesi, and T. Wareham, "Ancestral Maximum Likelihood of Evolutionary Trees is Hard," J. Bioinformatics and Computational Biology, vol. 2, no. 2, pp. 257- 271, 2004.
• 2: Richa Agarwala , Vineet Bafna , Martin Farach , Mike Paterson , Mikkel Thorup, On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics), SIAM Journal on Computing, v.28 n.3, p.1073-1085, Feb. 1999 [doi>10.1137/S0097539795296334]
• 3: Giorgio Ausiello , M. Protasi , A. Marchetti-Spaccamela , G. Gambosi , P. Crescenzi , V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 4: [4] J. Cavender, "Taxonomy with Confidence," Math. Biosciences, vol. 40, pp. 271-280, 1978.
• 5: [5] B. Chor and T. Tuller, "Maximum Likelihood of Evolutionary Trees is Hard," Proc. Ninth Int'l Conf. Computational Molecular Biology (RECOMB 2005), 2005.
• 6: Andrea E. F. Clementi, Improved non-approximability results for minimum vertex cover with density constraints, Theoretical Computer Science, v.225 n.1-2, p.113-128, Aug. 28, 1999 [doi>10.1016/S0304-3975(97)00226-0]
• 7: [7] W. Day, D. Jonhson, and D. Sankoff, "The Computational Complexity of Inferring Rooted Phylogenies by Parsimony," Math. Biosciences, vol. 81, pp. 33-42, 1986.
• 8: [8] W. Day and D. Sankoff, "The Computational Complexity of Inferring Phylogenies by Compatibility," Systematic Zoology, vol. 35, pp. 224-229, 1986.
• 9: [9] A.W.F. Edwards and L.L. Cavalli-Sforza, "Reconstruction of Evolutionary Trees," Phenetic and Phylogenetic Classification, V.H. Heywood and J. McNeill, eds. Systematics Assoc., London, vol. 6, pp. 67-76, 1964.
• 10: [10] J.S. Farris, "A Probability Model for Inferring Evolutionary Trees," Systematic Zoology, vol. 22, pp. 250-256, 1973.
• 11: [11] J. Felsenstein, "Evolutionary Trees from DNA Sequences: A Maximum Likelihood Approach," J. Molecular Evolution, vol. 17, pp. 368-376, 1981.
• 12: [12] J. Felsenstein, Inferring Phylogenies. Sunderland: Sinauer Assoc., 2004.
• 13: [13] L. Foulds and R. Graham, "The Steiner Problem in Phylogeny is NP-Complete," Advances in Applied Math., vol. 3, pp. 43-49, 1982.
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: [15] J. Neyman, "Molecular Studies of Evolution: A Source of Novel Statistical Problems," Statistical Decision Theory and Related Topics, S.S. Gupta and J. Yackel, eds. New York: Academic Press, pp. 1-27, 1971.
• 16: [16] C. Semple and M. Steel, Phylogenetics. Oxford Univ. Press, 2003.
• 17: [17] C. Tuffley and M. Steel, "Links between Maximum Likelihood and Maximum Parsimony under a Simple Model of Site Substitution," Bull. Math. Biology, vol. 59, no. 3, pp. 581-607, 1997.
• 18: [18] H.T. Wareham, On the Computational Complexity of Inferring Evolutionary Trees, MSc thesis, Technical Report no. 9301, Dept. of Computer Science, Memorial Univ. of Newfoundland 1993.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical
      I.5.3 Clustering
          Subjects: Similarity measures

General Terms:
Algorithms, Design

Keywords:
Analysis of algorithms and problem complexity, probability and statistics, biology and genetics.