Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Ancestral maximum likelihood of evolutionary trees is hard
KTH, Tidigare Institutioner, Numerisk analys och datalogi, NADA.
Visa övriga samt affilieringar
2004 (Engelska)Ingår i: Journal of Bioinformatics and Computational Biology, ISSN 0219-7200, Vol. 2, nr 2, 257-271 s.Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
2004. Vol. 2, nr 2, 257-271 s.
Nyckelord [en]
AMINO-ACID-SEQUENCES; COMPUTATIONAL-COMPLEXITY; INFERRING PHYLOGENIES; INFERENCE; RECONSTRUCTION; ALGORITHM; PARSIMONY
Nationell ämneskategori
Data- och informationsvetenskap
Identifikatorer
URN: urn:nbn:se:kth:diva-61187DOI: 10.1142/S0219720004000557ISI: 000188697400016Scopus ID: 2-s2.0-4043184290OAI: oai:DiVA.org:kth-61187DiVA: diva2:478697
Anmärkning
QC 20120117Tillgänglig från: 2012-01-16 Skapad: 2012-01-16 Senast uppdaterad: 2012-01-17Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas

Övriga länkar

Förlagets fulltextScopus

Sök vidare i DiVA

Av författaren/redaktören
Lagergren, Jens
Av organisationen
Numerisk analys och datalogi, NADA
I samma tidskrift
Journal of Bioinformatics and Computational Biology
Data- och informationsvetenskap

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 139 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf