Ancestral maximum likelihood of evolutionary trees is hard.
Maximum likelihood (ML) (Neyman, 1971) is an increasingly popular optimality criterion for selecting evolutionary trees. Finding optimal ML trees appears to be a very hard computational task--in particular, algorithms and heuristics for ML take longer to run than algorithms and heuristics for maximum parsimony (MP). However, while MP has been known to be NP-complete for over 20 years, no such hardness result has been obtained so far for ML. In this work we make a first step in this direction by proving that ancestral maximum likelihood (AML) is NP-complete. The input to this problem is a set of aligned sequences of equal length and the goal is to find a tree and an assignment of ancestral sequences for all of that tree's internal vertices such that the likelihood of generating both the ancestral and contemporary sequences is maximized. Our NP-hardness proof follows that for MP given in (Day, Johnson and Sankoff, 1986) in that we use the same reduction from Vertex Cover; however, the proof of correctness for this reduction relative to AML is different and substantially more involved.
School of Computer Science, McGill University, Montreal, Quebec, Canada. laddar@cs.mcgill.ca
Louigi
L
Addario-Berry
Benny
B
Chor
Mike
M
Hallett
Jens
J
Lagergren
Alessandro
A
Panconesi
Todd
T
Wareham
D000465:Algorithms; D001483:Base Sequence; D019143:Evolution, Molecular; D020869:Gene Expression Profiling / Q000379:methods*; D016013:Likelihood Functions; D008969:Molecular Sequence Data; D010802:Phylogeny; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*