Posets and permutations in the duplication-loss model: Minimal permutations with d descents

In this paper, we are interested in the combinatorial analysis of the whole genome duplication-random loss model of genome rearrangement initiated in Chaudhuri et al. (2006) [9] and Bouvel and Rossin (2009)[8]. In this model, genomes composed of n genes are modeled by permutations of the set of integers {1, 2, ... , n}, that can evolve through duplication-loss steps. It was previously shown that the class of permutations obtained in this model after a given number p of steps is a class of pattern-avoiding permutations of finite basis. The excluded patterns were described as the minimal permutations with d = 2(p) descents, minimal being intended in the sense of the pattern-involvement relation on permutations. Here, we give a local and simpler characterization of the set B-d of minimal permutations with d descents. We also provide a more detailed analysis - characterization, bijection and enumeration - of two particular subsets of B-d, namely the patterns in B-d of size d + 2 and 2d. (C) 2010 Elsevier B.V. All rights reserved.