Finding a maximum likelihood tree is hard

DOI10.1145/1183907.1183909MaRDI QIDQ3455214zbMATH OpenOpenAlexWikidataFDO

Authors Benny Chor, Tamir Tuller

Publication date 4 December 2015

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1183907.1183909

zbMATH Keywords

approximate vertex coverintractabilitymaximum likelihoodmaximum parsimonytree reconstruction

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Applications of statistics to biology and medical sciences; meta analysis (62P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Problems related to evolution (92D15)

Recommendations

• Research in Computational Molecular Biology
• An algorithm for the maximum likelihood problem on evolutionary trees
• scientific article; zbMATH DE number 1088267
• Links between maximum likelihood and maximum parsimony under a simple model of site substitution
• On the complexity of constructing evolutionary trees

Cited in

(15)

• Fast computation of maximum likelihood trees by numerical approximation of amino acid replacement probabilities
• Two further links between MP and ML under the Poisson model.
• Phylogenetic mixtures: concentration of measure in the large-tree limit
• Fishing for minimum evolution trees with neighbor-nets
• Analytic solutions of maximum likelihood on forks of four taxa
• Cases in which ancestral maximum likelihood will be confusingly misleading
• On the maximum parsimony distance between phylogenetic trees
• Is the protein model assignment problem under linked branch lengths NP-hard?
• Complexity of modification problems for best match graphs
• An optimal algorithm for computing all subtree repeats in trees
• Mathematical aspects of phylogenetic groves
• Identifiability and inference of non-parametric rates-across-sites models on large-scale phylo\-genies
• Efficient estimation of the accuracy of the maximum likelihood method for ancestral state reconstruction
• Phylogenetic trees via Hamming distance decomposition tests
• Phase transition in the sample complexity of likelihood-based phylogeny inference

This page was built for publication: Finding a maximum likelihood tree is hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3455214)