Change search
ReferencesLink to record
Permanent link

Direct link
Ancestral maximum likelihood of evolutionary trees is hard
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
Show others and affiliations
2004 (English)In: Journal of Bioinformatics and Computational Biology, ISSN 0219-7200, Vol. 2, no 2, 257-271 p.Article in journal (Refereed) Published
Abstract [en]

Maximum likelihood (ML) (Felsenstein, 1981) 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.

Place, publisher, year, edition, pages
2004. Vol. 2, no 2, 257-271 p.
Keyword [en]
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-61187DOI: 10.1142/S0219720004000557ISI: 000188697400016ScopusID: 2-s2.0-4043184290OAI: diva2:478697
QC 20120117Available from: 2012-01-16 Created: 2012-01-16 Last updated: 2012-01-17Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Lagergren, Jens
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
Journal of Bioinformatics and Computational Biology
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 30 hits
ReferencesLink to record
Permanent link

Direct link