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.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.