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.
411 (26-28)
2487
2501
M. Bouvel; E. Pergola
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2158/393527
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 10
social impact