An efficient and accurate distance based algorithm to reconstruct tandem duplication trees - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Bioinformatics Year : 2002

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.SUPPLEMENTARY INFORMATION: http://www.lirmm.fr/w3ifa/MAAS/

Dates and versions

lirmm-00268612 , version 1 (01-04-2008)

Identifiers

Cite

Olivier Elemento, Olivier Gascuel. An efficient and accurate distance based algorithm to reconstruct tandem duplication trees. Bioinformatics, 2002, Proceedings of ECCB'02, 18 (Suppl. 2), pp.92-99. ⟨10.1093/bioinformatics/18.suppl_2.S92⟩. ⟨lirmm-00268612⟩
49 View
0 Download

Altmetric

Share

More