In the context of the genome rearrangement problem, we analyze two well known models, namely the block transposition and the prefix block transposition models, by exploiting the connection with the notion of permutation pattern. More specifically, for any k, we provide a characterization of the set of permutations having distance ≤ k from the identity (which is known to be a permutation class) in terms of what we call generating permutations and we describe some properties of its basis, which allow to compute such a basis for small values of k.

Permutation patterns in genome rearrangement problems / Giulio Cerbai, Luca Ferrari. - ELETTRONICO. - 2113:(2018), pp. 124-131. (Intervento presentato al convegno GASCOM 2018 tenutosi a Athens, Greece nel 18-20 June).

Permutation patterns in genome rearrangement problems

CERBAI, GIULIO;Luca Ferrari
2018

Abstract

In the context of the genome rearrangement problem, we analyze two well known models, namely the block transposition and the prefix block transposition models, by exploiting the connection with the notion of permutation pattern. More specifically, for any k, we provide a characterization of the set of permutations having distance ≤ k from the identity (which is known to be a permutation class) in terms of what we call generating permutations and we describe some properties of its basis, which allow to compute such a basis for small values of k.
2018
Random and Exhaustive Generation of Combinatorial Structures 2018.
GASCOM 2018
Athens, Greece
18-20 June
Giulio Cerbai, Luca Ferrari
File in questo prodotto:
File Dimensione Formato  
paper12.pdf

accesso aperto

Descrizione: Articolo principale
Tipologia: Pdf editoriale (Version of record)
Licenza: Open Access
Dimensione 424.66 kB
Formato Adobe PDF
424.66 kB Adobe PDF

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1136556
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact