A New Quartet-based Phylogeny Reconstruction Algorithm

223. B. B. Zhou, M. Tarawneh, D. Chu, P. Wang, C. Wang, A. Y. Zomaya and R. P. Brent, On a new quartet-based phylogeny reconstruction algorithm, Proceedings 2006 International Conference on Bioinformatics and Computational Biology (BIOCOMP06), Las Vegas, USA, June 2006, 87-93.

Preprint: pdf (612K).


Recently we developed a new quarted-based algorithm for phylogenetic analysis [220]. This algorithm constructs a limited number of trees for a given set of DNA or protein sequences and the initial experimental results show that the probability for the correct tree to be included in this small set of trees is very high. In this paper we further extend the idea. We first discuss a revision to the original algorithm to reduce the number of trees generated, while keeping the high probability for the correct tree to be included. We then deal with the issue of how to retrieve the correct tree from the set of generated trees. Our current approach is to calculate the likelihood values of these trees and select a few which have the highest likelihood values. Though the experimental results are comparable to those obtained from currently popular ML-based algorithms, we find that it is common that certain incorrect trees can have likelihood values at least as large as that of the correct tree. A significant implication of this is that even if we are able to find a truly globally optimal tree under the maximum likelihood criterion, this tree is not necessarily the correct phylogenetic tree.

Go to next publication

Return to Richard Brent's index page