Skip to Main content Skip to Navigation
Journal articles

The Combinatorics of Tandem Duplication Trees

Olivier Gascuel 1 Michael Hendy 2, 3 Alain Jean-Marie 4 Robert Mclachlan 3
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
4 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We developed a recurrence relation that counts the number of tandem duplication trees (either rooted or unrooted) that are consistent with a set of n tandemly repeated sequences generated under the standard unequal recombination (or crossover) model of tandem duplications. The number of rooted duplication trees is exactly twice the number of unrooted trees, which means that on average only two positions for a root on a duplication tree are possible. Using the recurrence, we tabulated these numbers for small values of n. We also developed an asymptotic formula that for large n provides estimates for these numbers. These numbers give a priori probabilities for phylogenies of the repeated sequences to be duplication trees. This work extends earlier studies where exhaustive counts of the numbers for small n were obtained. One application showed the significance of finding that most maximum-parsimony trees constructed from repeat sequences from human immunoglobins and T-cell receptors were tandem duplication trees. Those findings provided strong support to the proposed mechanisms of tandem gene duplication. The recurrence relation also suggests efficient algorithms to recognize duplication trees and to generate random duplication trees for simulation.We present a linear-time recognition algorithm. [Asymptotic enumeration; random generation; recognition; recursion; tandem duplication trees.]
Document type :
Journal articles
Complete list of metadatas

Cited literature [6 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00192006
Contributor : Christine Carvalho de Matos <>
Submitted on : Monday, November 26, 2007 - 1:44:46 PM
Last modification on : Monday, October 19, 2020 - 4:12:02 PM
Long-term archiving on: : Monday, April 12, 2010 - 5:09:00 AM

File

D109.PDF
Files produced by the author(s)

Identifiers

Collections

Citation

Olivier Gascuel, Michael Hendy, Alain Jean-Marie, Robert Mclachlan. The Combinatorics of Tandem Duplication Trees. Systematic Biology, Oxford University Press (OUP), 2003, 52, pp.110-118. ⟨10.1080/10635150390132821⟩. ⟨lirmm-00192006⟩

Share

Metrics

Record views

273

Files downloads

303