TY - JOUR
T1 - Permutation patterns in genome rearrangement problems
T2 - The reversal model
AU - Cerbai, Giulio
AU - Ferrari, Luca
N1 - Publisher Copyright:
© 2019 Elsevier B.V.
PY - 2020/5/31
Y1 - 2020/5/31
N2 - In the context of the genome rearrangement problem, we analyze two well known models, namely the reversal and the prefix reversal models, by exploiting the connection with the notion of permutation patterns. More specifically, for any k, we provide a characterization of the set of permutations having distance less than or equal to k from the identity (which is known to be a permutation class) in terms of what we call generating peg permutations and we describe some properties of its basis, which allow us to compute such a basis for small values of k.
AB - In the context of the genome rearrangement problem, we analyze two well known models, namely the reversal and the prefix reversal models, by exploiting the connection with the notion of permutation patterns. More specifically, for any k, we provide a characterization of the set of permutations having distance less than or equal to k from the identity (which is known to be a permutation class) in terms of what we call generating peg permutations and we describe some properties of its basis, which allow us to compute such a basis for small values of k.
UR - http://www.scopus.com/inward/record.url?scp=85074482687&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2019.10.012
DO - 10.1016/j.dam.2019.10.012
M3 - Article
AN - SCOPUS:85074482687
SN - 0166-218X
VL - 279
SP - 34
EP - 48
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -