Article ID: | iaor20114166 |
Volume: | 21 |
Issue: | 4 |
Start Page Number: | 409 |
End Page Number: | 422 |
Publication Date: | May 2011 |
Journal: | Journal of Combinatorial Optimization |
Authors: | Ma Bin, Zhang Louxin |
Keywords: | estimation, evolutionary algorithms, maximum likelihood estimation |
The marginal maximum likelihood method is a widely‐used method for ancestral state reconstruction. Given an evolution model (a phylogeny tree and the edge mutation rates) and the extant states (states on leaves), the method computes efficiently the most likely ancestral state on the root. However, when the extant states are randomly generated by using the evolutionary model, it is unknown how to efficiently calculate the expected reconstruction accuracy of the marginal maximum likelihood method. In this paper, a fully polynomial time approximation scheme (FPTAS) is presented for the calculation.