Sökning: L773:0219 7200 OR L773:1757 6334
> Chor B >
Ancestral maximum l...
-
Addario-Berry, L
(författare)
Ancestral maximum likelihood of evolutionary trees is hard
- Artikel/kapitelEngelska2004
Förlag, utgivningsår, omfång ...
Nummerbeteckningar
-
LIBRIS-ID:oai:DiVA.org:kth-61187
-
https://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-61187URI
-
https://doi.org/10.1142/S0219720004000557DOI
Kompletterande språkuppgifter
-
Språk:engelska
-
Sammanfattning på:engelska
Ingår i deldatabas
Klassifikation
-
Ämneskategori:ref swepub-contenttype
-
Ämneskategori:art swepub-publicationtype
Anmärkningar
-
QC 20120117
-
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.
Ämnesord och genrebeteckningar
Biuppslag (personer, institutioner, konferenser, titlar ...)
-
Chor, B
(författare)
-
Hallett, M
(författare)
-
Lagergren, JensKTH,Numerisk analys och datalogi, NADA(Swepub:kth)u13fcyg9
(författare)
-
Panconesi, A
(författare)
-
Wareham, T
(författare)
-
KTHNumerisk analys och datalogi, NADA
(creator_code:org_t)
Sammanhörande titlar
-
Ingår i:Journal of Bioinformatics and Computational Biology2:2, s. 257-2710219-72001757-6334
Internetlänk
Hitta via bibliotek
Till lärosätets databas