A polynomial time approximation scheme for inferring evolutionary trees from quartet topologies and its application

Inferring evolutionary trees has long been a challenging problem for both b iologists and computer scientists. In recent years research has concentrate d on the quartet method paradigm for inferring evolutionary trees. Quartet methods proceed by first inferring the evolutionary history for every set o f four species (resulting in a set Q of inferred quartet topologies) and th en recombining these inferred quartet topologies to form an evolutionary tr ee. This paper presents two results on the quartet method paradigm. The fir st is a polynomial time approximation scheme (PTAS) for recombining the inf erred quartet topologies optimally. This is an important result since, to d ate, there have been no polynomial time algorithms with performance guarant ees for quartet methods. To achieve this result the natural denseness of th e 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 gu arantees. This result has particular significance since quartet methods are usually very sensitive to errors in the data. It is shown how quartet clea ning can dramatically increase the accuracy of quartet methods.