Sökning: id:"swepub:oai:DiVA.org:kth-61187" >
Ancestral maximum l...
Ancestral maximum likelihood of evolutionary trees is hard
-
Addario-Berry, L (författare)
-
Chor, B (författare)
-
Hallett, M (författare)
-
visa fler...
-
- Lagergren, Jens (författare)
- KTH,Numerisk analys och datalogi, NADA
-
Panconesi, A (författare)
-
Wareham, T (författare)
-
visa färre...
-
(creator_code:org_t)
- 2004
- 2004
- Engelska.
-
Ingår i: Journal of Bioinformatics and Computational Biology. - 0219-7200 .- 1757-6334. ; 2:2, s. 257-271
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Nyckelord
- AMINO-ACID-SEQUENCES; COMPUTATIONAL-COMPLEXITY; INFERRING PHYLOGENIES; INFERENCE; RECONSTRUCTION; ALGORITHM; PARSIMONY
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas