SwePub
Sök i LIBRIS databas

  Utökad sökning

onr:"swepub:oai:DiVA.org:kth-61187"
 

Sökning: onr:"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
  • Tidskriftsartikel (refereegranskat)
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

NATURAL SCIENCES  -- Computer and Information Sciences (hsv//eng)
NATURVETENSKAP  -- Data- och informationsvetenskap (hsv//swe)

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

Sök utanför SwePub

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Stäng

Kopiera och spara länken för att återkomma till aktuell vy