Advanced search
Start date
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Sorting permutations by prefix and suffix rearrangements

Full text
Lintzmayer, Carla Negri ; Fertin, Guillaume ; Dias, Zanoni
Total Authors: 3
Document type: Journal article
Web of Science Citations: 3

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. (AU)

FAPESP's process: 14/19401-8 - Genome rearrangement algorithms
Grantee:Zanoni Dias
Support type: Regular Research Grants
FAPESP's process: 13/01172-0 - The sorting permutations problem using prefix and suffix operations
Grantee:Carla Negri Lintzmayer
Support type: Scholarships in Brazil - Doctorate (Direct)
FAPESP's process: 13/08293-7 - CCES - Center for Computational Engineering and Sciences
Grantee:Munir Salomao Skaf
Support type: Research Grants - Research, Innovation and Dissemination Centers - RIDC
FAPESP's process: 16/14132-4 - One and two-dimensional bin packing with conflicts and unloading restrictions
Grantee:Carla Negri Lintzmayer
Support type: Scholarships in Brazil - Post-Doctorate
FAPESP's process: 14/20738-7 - Sorting permutations by prefix reversals and suffix reversals
Grantee:Carla Negri Lintzmayer
Support type: Scholarships abroad - Research Internship - Doctorate (Direct)
FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
Grantee:Flávio Keidi Miyazawa
Support type: Research Projects - Thematic Grants