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

In [K. Chaudhuri, K. Chen, R. Mihaescu, S. Rao, On the tandem duplication-random loss model of genome rearrangement, in: SODA, 2006, pp. 564–570], 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 αk for α=1 or α≥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 ∞ if k>K, for any value of the parameter K∈N∪{∞}. 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 Sn, 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.