A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application
Authors:
- Tao JiangTJTao Jiang
- Paul KearneyPKPaul Kearney
- Ming LiMLMing Li
- 1 January 2001
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 30 (6) , 1942-1961
Abstract
Inferring evolutionary trees has long been a challenging problem for both biologists and computer scientists. In recent years research has concentrated on the quartet method paradigm for inferring evolutionary trees. Quartet methods proceed by first inferring the evolutionary history for every set of four species (resulting in a set Q of inferred quartet topologies) and then recombining these inferred quartet topologies to form an evolutionary tree. This paper presents two results on the quartet method paradigm. The first is a polynomial time approximation scheme (PTAS) for recombining the inferred quartet topologies optimally. This is an important result since, to date, there have been no polynomial time algorithms with performance guarantees for quartet methods. To achieve this result the natural denseness of the set Q is exploited. The second result is a new technique, called quartet cleaning, that detects and corrects errors in the set Q with performance guarantees. This result has particular significance since quartet methods are usually very sensitive to errors in the data. It is shown how quartet cleaning can dramatically increase the accuracy of quartet methods.Keywords
This publication has 12 references indexed in Scilit:
- A new rounding procedure for the assignment problem with applications to dense graph arrangement problems2002
- Constructing big trees from short sequences1997
- Inferring evolutionary trees with strong combinatorial evidence1997
- Quartet Puzzling: A Quartet Maximum-Likelihood Method for Reconstructing Tree TopologiesMolecular Biology and Evolution, 1996
- Human Origins and Analysis of Mitochondrial DNA SequencesScience, 1992
- The complexity of reconstructing trees from qualitative characters and subtreesJournal of Classification, 1992
- Proof verification and hardness of approximation problems1992
- African Populations and the Evolution of Human Mitochondrial DNAScience, 1991
- Numerical Methods for Inferring Evolutionary TreesThe Quarterly Review of Biology, 1982
- Evolutionary trees from DNA sequences: A maximum likelihood approachJournal of Molecular Evolution, 1981