An Exact and Polynomial Distance-Based Algorithm to Reconstruct Single Copy Tandem Duplication Trees - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Journal of Discrete Algorithms Année : 2005

An Exact and Polynomial Distance-Based Algorithm to Reconstruct Single Copy Tandem Duplication Trees

Olivier Elemento
  • Fonction : Auteur
  • PersonId : 1295554

Résumé

The problem of reconstructing the duplication tree of a set of tandemly repeated sequences which are supposed to have arisen by unequal recombination, was first introduced by Fitch (1977), and has recently received a lot of attention. In this paper, we place ourselves in a distance framework and deal with the restricted problem of reconstructing single copy duplication trees. We describe an exact and polynomial distance based algorithm for solving this problem, the parsimony version of which has previously been shown to be NP-hard (like most evolutionary tree reconstruction problems). This algorithm is based on the minimum evolution principle, and thus involves selecting the shortest tree as being the correct duplication tree. After presenting the underlying mathematical concepts behind the minimum evolution principle, and some of its benefits (such as statistical consistency), we provide a new recurrence formula to estimate the tree length using ordinary least-squares, given a matrix of pairwise distances between the copies. We then show how this formula naturally forms the dynamic programming framework on which our algorithm is based, and provide an implementation in time and space, where n is the number of copies.
Fichier principal
Vignette du fichier
D593.PDF (161.65 Ko) Télécharger le fichier
Loading...

Dates et versions

lirmm-00105291 , version 1 (11-10-2006)

Identifiants

Citer

Olivier Gascuel, Olivier Elemento. An Exact and Polynomial Distance-Based Algorithm to Reconstruct Single Copy Tandem Duplication Trees. Journal of Discrete Algorithms, 2005, 3, pp.362-374. ⟨10.1016/j.jda.2004.08.013⟩. ⟨lirmm-00105291⟩
76 Consultations
161 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More