Molecular Clock Fork Phylogenies: Closed Form Analytic Maximum Likelihood Solutions
Maximum likelihood (ML) is increasingly used as an optimality criterion for selecting evolutionary trees (Felsenstein, 1981, J. Mol. Evol. 17:368–376), but finding the global optimum is a hard computational task. Because no general analytic solution is known, numeric techniques such as hill climbing or expectation maximization (EM) are used in order to find optimal parameters for a given tree. So far, analytic solutions were derived only for the simplest model—three-taxa, two-state characters, under a molecular clock. Quoting Ziheng Yang (2000, Proc. R. Soc. B 267:109–119), who initiated the analytic approach,“this seems to be the simplest case, but has many of the conceptual and statistical complexities involved in phylogenetic estimation.”In this work, we give general analytic solutions for a family of trees withfour-taxa, two-state characters, under a molecular clock. The change from three to four taxa incurs a major increase in the complexity of the underlying algebraic system, and requires novel techniques and approaches. We start by presenting the general maximum likelihood problem on phylogenetic trees as a constrained optimization problem, and the resulting system of polynomial equations. In full generality, it is infeasible to solve this system, therefore specialized tools for the molecular clock case are developed. Four-taxa rooted trees have two topologies—thefork(two subtrees with two leaves each) and thecomb(one subtree with three leaves, the other with a single leaf). We combine the ultrametric properties of molecular clock fork trees with the Hadamard conjugation (Hendy and Penny, 1993, J. Classif. 10:5–24) to derive a number of topology dependent identities. Employing these identities, we substantially simplify the system of polynomial equations for the fork. We finally employ symbolic algebra software to obtainclosed formanalytic solutions (expressed parametrically in the input data). In general, four-taxa trees can have multiple ML points (Steel, 1994, Syst. Biol. 43:560–564; Chor et al., 2000, MBE 17:1529–1541). In contrast, we can now prove that each fork topology has aunique(local and global) ML point. [Analytic solutions; Hadamard conjugation; maximum likelihood; molecular clock; phylogenetic reconstruction; symbolic algebra software; systems of polynomial equations.]
No Reference information available - sign in for access.
No Citation information available - sign in for access.
No Supplementary Data.
No Article Media
Document Type: Research Article
Affiliations: 1: School of Computer Science, Tel-Aviv University, Tel-Aviv, Israel 2: Computer Science Department, Technion, Haifa, Israel
Publication date: December 1, 2004