Finding a maximum likelihood tree is hard

DOI10.1145/1183907.1183909zbMath1326.68146MaRDI QIDQ3455214

Tamir Tuller, Benny Chor

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

maximum likelihood; intractability; maximum parsimony; tree reconstruction; approximate vertex cover

Mathematics Subject Classification ID

62P10: Applications of statistics to biology and medical sciences; meta analysis

05C05: Trees

92D15: Problems related to evolution

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)