FLORE (FLOrence REsearch) è il repository istituzionale ad accesso pieno e aperto dell'Università degli Studi di Firenze.
Raccoglie, documenta e conserva le informazioni sulla produzione scientifica dell'Università e costituisce l'Anagrafe della ricerca dell'Ateneo.
EnglishIn 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 |
http://hdl.handle.net/2158/393527
Copyright © 2022