|
 ABSTRACT
Maximum likelihood (ML) is an increasingly popular optimality criterion for selecting evolutionary trees [Felsenstein 1981]. Finding optimal ML trees appears to be a very hard computational task, but for tractable cases, ML is the method of choice. In particular, algorithms and heuristics for ML take longer to run than algorithms and heuristics for the second major character based criterion, maximum parsimony (MP). However, while MP has been known to be NP-complete for over 20 years [Foulds and Graham, 1982; Day et al. 1986], such a hardness result for ML has so far eluded researchers in the field.An important work by Tuffley and Steel [1997] proves quantitative relations between the parsimony values of given sequences and the corresponding log likelihood values. However, a direct application of their work would only give an exponential time reduction from MP to ML. Another step in this direction has recently been made by Addario-Berry et al. [2004], who proved that ancestral maximum likelihood (AML) is NP-complete. AML “lies in between” the two problems, having some properties of MP and some properties of ML. Still, the AML proof is not directly applicable to the ML problem.We resolve the question, showing that “regular” ML on phylogenetic trees is indeed intractable. Our reduction follows the vertex cover reductions for MP [Day et al. 1986] and AML [Addario-Berry et al. 2004], but its starting point is an approximation version of vertex cover, known as gap vc. The crux of our work is not the reduction, but its correctness proof. The proof goes through a series of tree modifications, while controlling the likelihood losses at each step, using the bounds of Tuffley and Steel [1997]. The proof can be viewed as correlating the value of any ML solution to an arbitrarily close approximation to vertex cover.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
Addario-Berry, L., Chor, B., Hallett, M., Lagergren, J., Panconesi, A., and Wareham, T. 2004. Ancestral maximum likelihood of evolutionary trees is hard. J. Bioinf. Comput. Biol. 2, 2, 257--271,
|
| |
2
|
|
| |
3
|
Chor, B., Hendy, M. D., Holland, B. R., and Penny, D. 2000. Multiple maxima of likelihood in phylogenetic trees: An analytic approach. Mol. Biol. Evol. 17, 10, 1529--1541.
|
| |
4
|
|
| |
5
|
Day, W. 1987. The computational complexity of inferring phylogenies from dissimilarity matrix. Bull. Math. Biol. 49, 4, 461--467.
|
| |
6
|
Day, W., Johnson, D., and Sankoff, D. 1986. The computational complexity of inferring rooted phylogenies by parsimony. Mathematical Biosciences 81, 33--42.
|
| |
7
|
Day W., and Sankoff, D. 1986. The computational complexity of inferring phylogenies by compatibility. Syst. Zool. 35, 2, 224--229.
|
| |
8
|
Dinur I., and Safra, S. 2005. On the importance of being biased (1.36 hardness of approximating vertex-cover). Ann. Math. 162, 439--485.
|
| |
9
|
Edwards, A. W. F. 1972. Likelihood. Cambridge University Press, Cambridge, UK.
|
| |
10
|
Felsenstein, J. 1981. Evolutionary trees from DNA sequences: A maximum likelihood approach. J. Mol. Evol. 17, 368--376.
|
| |
11
|
Felsenstein, J. 1996. Inferring phylogenies from protein sequences by parsimony, distance, and likelihood methods. Meth. Enzym. 266, 419--427.
|
| |
12
|
Felsenstein, J. 2004. Inferring Phylogenies. Sinauer Associates, Sunderland, MA.
|
| |
13
|
Fitch, W. M. 1971. Toward defining the course of evolution: Minimum change for specified tree topology. Syst. Zool. 20, 406--416.
|
| |
14
|
Foulds, L., and Graham, R. 1982. The Steiner problem in phylogeny is NP-complete. Adv. Appl. Math. 3, 43--49.
|
 |
15
|
|
| |
16
|
Jukes, T. H. and Cantor, C. R. 1969. Evolution of protein molecules. In Mammalian Protein Metabolism. H. N. Munro, Ed. Academic Press, New York, pp. 21--132.
|
| |
17
|
Karpinski, M. 2001. Approximating bounded degree instances of np-hard problems. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA.
|
| |
18
|
Koshi, M., and Goldstein, R. 1996. Probabilistic reconstruction of ancestral nucleotide and amino acid sequences. J. Molec. Evol. 42, 313--320.
|
| |
19
|
Neyman, J. 1971. Molecular studies of evolution: A source of novel statistical problems. In Statistical Decision Theory and Related Topics, S. Gupta and Y. Jackel, Eds. Academic Press, New York, pp. 1--27.
|
| |
20
|
|
| |
21
|
steel, M. 1992. The complexity of reconstructing trees from qualitative characters and subtrees. J. Classif. 9, 71--90.
|
| |
22
|
Steel, M. 1994. The maximum likelihood point for a phlogenetic tree is not unique. Syst. Biol., 43, 560--564,
|
| |
23
|
Steel, M., and Penny, D. 2000. Parsimony, likelihood and the role of models in molecular phylogenetics. Mol. Biol. Evol. 17, 839--850.
|
| |
24
|
Tuffley, C., and Steel, M. 1997. Link between maximum likelihood and maximum parsimony under a simple model of site substitution. Bull. Math. Biol. 59, 3, 581--607.
|
| |
25
|
Wareham, T. 1993. On the computational complexity of inferring evolutional trees. Tech. Rep. 93--01. Dep. Computer Science, Memorial University of Newfoundland.
|
| |
26
|
Yang, Z., Kumar, S., and Nei, M. 1995. A new method of inferring of ancestral nucleotide and amino acid sequences. Genetics 141, 1641--1650.
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.2