Abstract
(1) We show that ML under the assumption of molecular clock is still computationally intractable (NP-hard). (2) We show that not only is it computationally intractable to find the exact ML tree, even approximating the logarithm of the ML for any multiplicative factor smaller than 1.00175 is computationally intractable. (3) We develop an algorithm for approximating log-likelihood under the condition that the input sequences are sparse. It employs any approximation algorithm for parsimony, and asymptotically achieves the same approximation ratio. We note that ML reconstruction for sparse inputs is still hard under this condition, and furthermore many real datasets satisfy it.
Keywords
Multiplicative functionLogarithmTree (set theory)MathematicsComputational complexity theoryMaximum likelihoodApproximation algorithmMaximum parsimonyAlgorithmComputer scienceCombinatoricsPhylogenetic treeStatistics
Affiliated Institutions
Related Publications
Improving the efficiency of SPR moves in phylogenetic tree search methods based on maximum likelihood
Abstract Motivation: Maximum likelihood (ML) methods have become very popular for constructing phylogenetic trees from sequence data. However, despite noticeable recent progress...
Does Choice in Model Selection Affect Maximum Likelihood Analysis?
In order to have confidence in model-based phylogenetic analysis, the model of nucleotide substitution adopted must be selected in a statistically rigorous manner. Several model...
Increasing the Efficiency of Searches for the Maximum Likelihood Tree in a Phylogenetic Analysis of up to 150 Nucleotide Sequences
Even when the maximum likelihood (ML) tree is a better estimate of the true phylogenetic tree than those produced by other methods, the result of a poor ML search may be no bett...
RAxML-NG: a fast, scalable and user-friendly tool for maximum likelihood phylogenetic inference
Abstract Motivation Phylogenies are important for fundamental biological research, but also have numerous applications in biotechnology, agriculture and medicine. Finding the op...
MultiPhyl: a high-throughput phylogenomics webserver using distributed computing
With the number of fully sequenced genomes increasing steadily, there is greater interest in performing large-scale phylogenomic analyses from large numbers of individual gene f...
Publication Info
- Year
- 2005
- Type
- article
- Volume
- 21
- Issue
- Suppl 1
- Pages
- i97-i106
- Citations
- 97
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
97
OpenAlex
Cite This
Benny Chor,
Tamir Tuller
(2005).
Maximum likelihood of evolutionary trees: hardness and approximation.
Computer applications in the biosciences
, 21
(Suppl 1)
, i97-i106.
https://doi.org/10.1093/bioinformatics/bti1027
Identifiers
- DOI
- 10.1093/bioinformatics/bti1027