Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/329635
Type: Artigo
Title: Sorting Permutations By Prefix And Suffix Rearrangements
Author: Lintzmayer
Carla Negri; Fertin
Guillaume; Dias
Zanoni
Abstract: Some interesting combinatorial problems have been motivated by genome rearrangements, which are mutations that affect large portions of a genome. When we represent genomes as permutations, the goal is to transform a given permutation into the identity permutation with the minimum number of rearrangements. When they affect segments from the beginning (respectively end) of the permutation, they are called prefix (respectively suffix) rearrangements. This paper presents results for rearrangement problems that involve prefix and suffix versions of reversals and transpositions considering unsigned and signed permutations. We give 2- approximation and (2 +lambda)-approximation algorithms for these problems, where lambda is a constant divided by the number of breakpoints (pairs of consecutive elements that should not be consecutive in the identity permutation) in the input permutation. We also give bounds for the diameters concerning these problems and provide ways of improving the practical results of our algorithms.
Subject: Permutations
Sorting
Reversals
Transpositions
Prefix
Suffix
Approximation Algorithms
Diameter
Editor: Imperial College Press
London
Rights: fechado
Identifier DOI: 10.1142/S0219720017500020
Address: http://www.worldscientific.com/doi/abs/10.1142/S0219720017500020
Date Issue: 2017
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
000397104400008.pdf1.46 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.