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) and Bouvel and Rossin (2009). 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.
Posets and permutations in the duplication-loss model: minimal permutations with d descets / M. Bouvel; E. Pergola. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 411 (26-28):(2010), pp. 2487-2501. [10.1016/j.tcs.2010.03.008]
Posets and permutations in the duplication-loss model: minimal permutations with d descets
PERGOLA, ELISA
2010
Abstract
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) and Bouvel and Rossin (2009). 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.File | Dimensione | Formato | |
---|---|---|---|
TCS10.pdf
Accesso chiuso
Tipologia:
Versione finale referata (Postprint, Accepted manuscript)
Licenza:
DRM non definito
Dimensione
928.53 kB
Formato
Adobe PDF
|
928.53 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.