Maximum likelihood on four taxa phylogenetic trees: Analytic solutions

Maximum likelihood (ML) is increasingly used as an opti-mality criterion for selecting evolutionary trees (Felsenstein, 1981), but finding the global optimum is a hard computa-tional task. Because no general analytic solution is known, numeric techniques such as hill climbing or expectation max-imization (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, un-der a molecular clock (MC). Quoting Ziheng Yang (2000), 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 analytic solutions for four taxa, two state characters under a molecular clock. The change from three to four taxa incurs a major increase in the complex-ity of the underlying algebraic system, and requires novel techniques and approaches. We start by presenting the gen-eral 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 MC 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 MC trees with the Hadamard conjugation (Hendy and Penny, 1993) to derive a number of topology dependent identities. Employing these iden-∗Research supported by ISF grant 418/00. †Corresponding author