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]
Titolo: | Posets and permutations in the duplication-loss model: minimal permutations with d descets | |
Autori di Ateneo: | ||
Autori: | M. Bouvel; PERGOLA, ELISA | |
Data di pubblicazione: | 2010 | |
Rivista: | ||
Volume: | 411 (26-28) | |
Pagina iniziale: | 2487 | |
Pagina finale: | 2501 | |
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. | |
Handle: | http://hdl.handle.net/2158/393527 | |
Appare nelle tipologie: | 1a - Articolo su rivista |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
TCS10.pdf | Versione finale referata (Postprint, Accepted manuscript) | DRM non definito | Administrator Richiedi una copia |