eCite Digital Repository

Upper bounds on maximum likelihood for phylogenetic trees


Hendy, MD and Holland, BR, Upper bounds on maximum likelihood for phylogenetic trees, Bioinformatics, 19, (2) pp. ii66-ii72. ISSN 1367-4803 (2003) [Refereed Article]

Restricted - Request a copy

Copyright Statement

The definitive publisher-authenticated version is available online at:

DOI: doi:10.1093/bioinformatics/btg1062


We introduce a mechanism for analytically deriving upper bounds on the maximum likelihood for genetic sequence data on sets of phylogenies. A simple ‘partition’ bound is introduced for general models. Tighter bounds are developed for the simplest model of evolution, the two state symmetric model of nucleotide substitution under the molecular clock. This follows earlier theoretical work which has been restricted to this model by analytic complexity. A weakness of current numerical computation is that reported ‘maximum likelihood’ results cannot be guaranteed, both for a specified tree (because of the possibility of multiple maxima) or over the full tree space (as the computation is intractable for large sets of trees). The bounds we develop here can be used to conclusively eliminate large proportions of tree space in the search for the maximum likelihood tree. This is vital in the development of a branch and bound search strategy for identifying the maximum likelihood tree. We report the results from a simulation study of approximately 106 data sets generated on clock-like trees of five leaves. In each trial a likelihood value of one specific instance of a parameterised tree is compared to the bound determined for each of the 105 possible rooted binary trees. The proportion of trees that are eliminated from the search for the maximum likelihood tree ranged from 92% to almost 98%, indicating a computational speed–up factor of between 12 and 44.

Item Details

Item Type:Refereed Article
Research Division:Mathematical Sciences
Research Group:Applied mathematics
Research Field:Biological mathematics
Objective Division:Expanding Knowledge
Objective Group:Expanding knowledge
Objective Field:Expanding knowledge in the mathematical sciences
UTAS Author:Holland, BR (Professor Barbara Holland)
ID Code:63287
Year Published:2003
Web of Science® Times Cited:4
Deposited By:Mathematics
Deposited On:2010-04-27
Last Modified:2010-05-05

Repository Staff Only: item control page