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 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 infinity if k > K, for any value of the parameter K is an element of N boolean OR {infinity}. 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 oil which the duplication-loss operations are performed. (C) 2008 Elsevier B.V. All rights reserved.