Abstract: Tandem duplication is an evolutionary process whereby a segment of DNA is replicated and proximally inserted. The different configurations that can arise from this process give rise to some interesting combinatorial questions. Firstly, we introduce an algebraic formalism to represent this process as a word producing automaton. The number of words arising from n tandem duplications can then be recursively derived. Secondly, each single word accounts for multiple evolutions. With the aid of a bi-coloured 2d- tree, a Hasse diagram corresponding to a partially ordered set is constructed, from which we can count the number of evolutions corresponding to a given word. Thirdly, we implement some subtree prune and graft operations on this structure to show that the total number of possible evolutions arising from n tandem duplications is . The space of structures arising from tandem duplication thus grows at a super-exponential rate with leading order term .
Recommendations
- Capacity and Expressiveness of Genomic Tandem Duplication
- Reconstructing the duplication history of tandemly repeated sequences
- A diffusion model for the fate of tandem gene duplicates in diploids
- Tandem Duplications, Segmental Duplications and Deletions, and Their Applications
- scientific article; zbMATH DE number 1945157
- A variant of the tandem duplication-random loss model of genome rearrangement
- Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats
- Approximation algorithms for reconstructing the duplication history of tandem repeats
- Combinatorics of genome rearrangements.
Cites work
- scientific article; zbMATH DE number 1226895 (Why is no real title available?)
- scientific article; zbMATH DE number 1865935 (Why is no real title available?)
- A SURVEY ON ALGORITHMIC ASPECTS OF TANDEM REPEATS EVOLUTION
- A variant of the tandem duplication-random loss model of genome rearrangement
- Automatic Sequences
- Counting linear extensions
- Modeling the evolution space of breakage fusion bridge cycles with a stochastic folding process
- Multidimensional binary search trees used for associative searching
- Multinomial convolution polynomials
- On the conductance of order Markov chains
- Posets and permutations in the duplication-loss model: minimal permutations with \(d\) descents
- Tandem cyclic alignment
Cited in
(9)- From biopolymer duplication to membrane duplication and beyond
- Reconstructing the duplication history of tandemly repeated sequences
- The complexity of genome rearrangement combinatorics under the infinite sites model
- Deciding the confusability of words under tandem repeats in linear time
- The Tandem Duplication Distance Is NP-Hard
- Finding all sorting tandem duplication random loss operations
- Duplication in DNA Sequences
- Finding All Sorting Tandem Duplication Random Loss Operations
- Combinatorics of chromosomal rearrangements based on synteny blocks and synteny packs
This page was built for publication: The combinatorics of tandem duplication
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494419)
