A variant of the tandem duplication - random loss model of genome rearrangement

Abstract

In Soda'06, Chaudhuri, Chen, Mihaescu and Rao study algorithmic properties of the tandem duplication - random loss model of genome rearrangement, well-known in evolutionary biology. In their model, the cost of one step of duplication-loss of width k is ${\alpha }^k$ for $\alpha =1$ or $\alpha >=2$. In this paper, we study a variant of this model, where the cost of one step of width $k$ is 1 if $k<=K$ and $\infty$ if $k>K$, for any value of the parameter $KinN$. We first show that permutations obtained after $p$ steps of width $K$ define classes of pattern-avoiding permutations. We also compute the numbers of duplication-loss steps of width $K$ necessary and sufficient to obtain any permutation of $S_n$, in the worst case and on average. In this second part, we may also consider the case $K=K(n)$, a function of the size $n$ of the permutation on which the duplication-loss operations are performed.

Cited by in corpus (6)

• Pattern-avoiding permutations and Brownian excursion Part I: Shapes and fluctuations
• Structure of Random 312-Avoiding Permutations
• Right-jumps and pattern avoiding permutations
• Posets and Permutations in the Duplication-Loss Model: Minimal Permutations with d Descents
• Some Enumeration Problems in the Duplication-Loss Model of Genome Rearrangement
• Permutation patterns in genome rearrangement problems