The combinatorics of tandem duplication

DOI10.1016/J.DAM.2015.05.014zbMATH Open1319.05009arXiv1402.0104OpenAlexW1528552012MaRDI QIDQ494419FDOQ494419

Authors: Luca Penso-Dolfin, Taoyang Wu, Chris D. Greenman 

Publication date: 1 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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 $pro{d}_{k=1}^n(4^k-(2k+1))$. The space of structures arising from tandem duplication thus grows at a super-exponential rate with leading order term $mathcalO(4^{frac12n^2})$.

Full work available at URL: https://arxiv.org/abs/1402.0104

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.

zbMATH Keywords

combinatoricsevolutionposetsrearrangementstandem duplication

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Protein sequences, DNA sequences (92D20) Combinatorics on words (68R15)

Cites Work

• Title not available (Why is that?)
• Automatic Sequences
• Counting linear extensions
• Multidimensional binary search trees used for associative searching
• A variant of the tandem duplication-random loss model of genome rearrangement
• Multinomial convolution polynomials
• On the conductance of order Markov chains
• Tandem cyclic alignment
• A SURVEY ON ALGORITHMIC ASPECTS OF TANDEM REPEATS EVOLUTION
• Title not available (Why is that?)
• Modeling the evolution space of breakage fusion bridge cycles with a stochastic folding process
• Posets and permutations in the duplication-loss model: minimal permutations with \(d\) descents

Cited In (9)

• Reconstructing the duplication history of tandemly repeated sequences
• From biopolymer duplication to membrane duplication and beyond
• 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)