Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/243993
Type: Artigo de periódico
Title: Approximation Algorithms For Sorting By Length-weighted Prefix And Suffix Operations
Author: Lintzmayer
Carla Negri; Fertin
Guillaume; Dias
Zanoni
Abstract: The traditional approach for the problems of sorting permutations by rearrangements is to consider that all operations have the same unitary cost. In this case, the goal is to find the minimum number of allowed rearrangements that are needed to sort a given permutation, and numerous efforts have been made over the past years regarding these problems. On the other hand, a long rearrangement (which is in fact a mutation) is more likely to disturb the organism. Therefore, weights based on the length of the segment involved may have an important role in the evolutionary process. In this paper we present the first results regarding problems of sorting permutations by length-weighted operations that consider rearrangement models with prefix and suffix variations of reversals and transpositions, which are the two most common types of genome rearrangements. Our main results are O (lg(2) n)-approximation algorithms for 10 such problems. (C) 2015 Elsevier B.V. All rights reserved.
Subject: Signed Permutations
1.375-approximation Algorithm
2-approximation Algorithm
Reversals
Transpositions
Rearrangement
Bounds
Time
Country: AMSTERDAM
Editor: ELSEVIER SCIENCE BV
Rights: embargo
Identifier DOI: 10.1016/j.tcs.2015.05.039
Address: http://www.sciencedirect.com/science/article/pii/S0304397515004818
Date Issue: 2015
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
wos_000358624500003.pdf678.17 kBAdobe PDFView/Open


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