Skip Navigation

This Article
Right arrow FREE Full Text (Print PDF) Freely available
Right arrow FREE Full Text (Screen PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Elemento, O.
Right arrow Articles by Gascuel, O.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Elemento, O.
Right arrow Articles by Gascuel, O.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Bioinformatics Vol. 18 no. 90002 2002
Pages S92-S99
© 2002 Oxford University Press

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

Olivier Elemento 1,2 and Olivier Gascuel 2

1 Département d'Informatique Fondamentale et Applications, LIRMM, 161 rue Ada, 34392, Montpellier
2 IMGT, the international ImMunoGeneTics database http://imgt.cines.fr, Laboratoire d'ImmunoGéenétique Moléculaire (LIGM), Université Montpellier II, UPR CNRS 1142, 141, rue de la Cardonille, 34396, Montpellier cedex 5, France

Received on April 8, 2002 ; accepted on June 15, 2002

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(n5), where n is the number of observed repeated sequences. Through a series of algorithmic refinements, we improve its complexity to O(n4) 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/

Contact: gascuel{at}lirmm.fr


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.