title: Dynamic programming procedure for searching optimal models to estimate substitution rates based on the maximum-likelihood method.
abstract: The substitution rate in a gene can provide valuable information for understanding its functionality and evolution. A widely used method to estimate substitution rates is the maximum-likelihood method implemented in the CODEML program in the PAML package. A limited number of branch models, chosen based on a priori information or an interest in a particular lineage(s), are tested, whereas a large number of potential models are neglected. A complementary approach is also needed to test all or a large number of possible models to search for the globally optional model(s) of maximum likelihood. However, the computational time for this search even in a small number of sequences becomes impractically long. Thus, it is desirable to explore the most probable spaces to search for the optimal models. Using dynamic programming techniques, we developed a simple computational method for searching the most probable optimal branch-specific models in a practically feasible computational time. We propose three search methods to find the optimal models, which explored O(n) (method 1) to O(n(2)) (method 2 and method 3) models when the given phylogeny has n branches. In addition, we derived a formula to calculate the number of all possible models, revealing the complexity of finding the optimal branch-specific model. We show that in a reanalysis of over 50 previously published studies, the vast majority obtained better models with significantly higher likelihoods than the conventional hypothesis model methods.
authors.affiliation: National Key Laboratory of Crop Genetic Improvement and National Center of Plant Gene Research Wuhan, Huazhong Agricultural University, Wuhan 430070, China.
authors.forename: Chengjun
authors.initials: C
authors.lastname: Zhang
authors.forename: Jia
authors.initials: J
authors.lastname: Wang
authors.forename: Weibo
authors.initials: W
authors.lastname: Xie
authors.forename: Gang
authors.initials: G
authors.lastname: Zhou
authors.forename: Manyuan
authors.initials: M
authors.lastname: Long
authors.forename: Qifa
authors.initials: Q
authors.lastname: Zhang
mesh_terms: D000465:Algorithms; D000818:Animals; D003198:Computer Simulation; D030541:Databases, Genetic; D019143:Evolution, Molecular; D016013:Likelihood Functions; D008957:Models, Genetic; D009113:Muramidase / Q000235:genetics; D010802:Phylogeny; D011323:Primates / Q000235:genetics; D012641:Selection, Genetic; D012984:Software
chemical_list: D009113:Muramidase