The Combinatorics of Tandem Duplication Trees - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Systematic Biology Year : 2003

The Combinatorics of Tandem Duplication Trees


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.]


Other [cs.OH]
Fichier principal
Vignette du fichier
D109.PDF (158 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-00192006 , version 1 (26-11-2007)



Olivier Gascuel, Michael D. Hendy, Alain Jean-Marie, Robert Mclachlan. The Combinatorics of Tandem Duplication Trees. Systematic Biology, 2003, 52, pp.110-118. ⟨10.1080/10635150390132821⟩. ⟨lirmm-00192006⟩
175 View
386 Download



Gmail Facebook X LinkedIn More