An efficient and accurate distance based algorithm to reconstruct tandem duplication trees.

Abstract

The problem of reconstructing the duplication tree of a set of tandemly repeated sequences which are supposed to have arisen through unequal recombination, was first introduced by Fitch (1977, Genetics, 86, 93-104), and has recently received a lot of attention. In this paper, we describe DTSCORE, a fast distance based algorithm to reconstruct tandem duplication trees, which is statistically consistent. As a cousin of the ADDTREE algorithm (Sattath and Tversky, 1977, Psychometrika, 42, 319-345), the raw DTSCORE has a time complexity in O(n(5)), where n is the number of observed repeated sequences. Through a series of algorithmic refinements, we improve its complexity to O(n(4)) in the worst case, but stress that the refined DTSCORE algorithm should perform faster with real data. We assess the topological accuracy of DTSCORE using simulated data sets, and compare it to existing reconstruction methods. The results clearly show that DTSCORE is more accurate than all the other methods we studied. Finally, we report the results of DTSCORE on a real dataset. http://www.lirmm.fr/w3ifa/MAAS/