© 2004 Society of Systematic Biologists
Molecular Clock Fork Phylogenies: Closed Form Analytic Maximum Likelihood Solutions
1 School of Computer Science, Tel-Aviv University Tel-Aviv 39040 Israel; E-mail: benny{at}cs.tau.ac.il (B.C.)
2 Computer Science Department Technion Haifa 32000, Israel; E-mail: ssagi{at}math.berkeley.edu (s.s.)
Edited by Nick Goldman: Associate Editor
 |
Abstract |
|---|
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 with four-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—the fork (two subtrees with two leaves each) and the comb (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 obtain closed form analytic 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 a unique (local and global) ML point.
Keywords: Analytic solutions; Hadamard conjugation; maximum likelihood; molecular clock; phylogenetic reconstruction; symbolic algebra software; systems of polynomial equations
Received November 19, 2003; Revised February 8, 2004; Accepted July 15, 2004
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  B. Chor, M. D. Hendy, and S. Snir Maximum Likelihood Jukes-Cantor Triplets: Analytic Solutions Mol. Biol. Evol., March 1, 2006; 23(3): 626 - 632. [Abstract] [Full Text] [PDF]
|
|