eCite Digital Repository

The Min/Max Squeeze: Guaranteeing a Minimal Tree for Population Data


Holland, BR and Huber, KT and Penny, D and Moulton, V, The Min/Max Squeeze: Guaranteeing a Minimal Tree for Population Data, Molecular Biology and Evolution, 22, (2) pp. 235-242. ISSN 0737-4038 (2005) [Refereed Article]

Restricted - Request a copy

Copyright Statement

Copyright 2005 Society for Molecular Biology and Evolution

DOI: doi:10.1093/molbev/msi010


We report that for population data, where sequences are very similar to one another, it is often possible to use a two-pronged (MinMax Squeeze) approach to prove that a tree is the shortest possible under the parsimony criterion. Such population data can be in a range where parsimony is a maximum likelihood estimator. This is in sharp contrast to the case with species data, where sequences are much further apart and the problem of guaranteeing an optimal phylogenetic tree is known to be computationally prohibitive for realistic numbers of species, irrespective of whether likelihood or parsimony is the optimality criterion. The Squeeze uses both an upper bound (the length of the shortest tree known) and a lower bound derived from partitions of the columns (the length of the shortest tree possible). If the two bounds meet, the shortest known tree is thus proven to be a shortest possible tree. The implementation is first tested on simulated data sets and then applied to 53 complete human mitochondrial genomes. The shortest possible trees for those data have several significant improvements from the published tree. Namely, a pair of Australian lineages comes deeper in the tree (in agreement with archaeological data), and the non-African part of the tree shows greater agreement with the geographical distribution of lineages.

Item Details

Item Type:Refereed Article
Keywords:lower bounds parsimony phylogeny estimation human mtDNA
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:62961
Year Published:2005
Web of Science® Times Cited:10
Deposited By:Mathematics
Deposited On:2010-03-31
Last Modified:2010-04-30

Repository Staff Only: item control page