Artículos de revistas
Sorting Permutations By Prefix And Suffix Rearrangements
Registro en:
Journal Of Bioinformatics And Computational Biology . Imperial College Press , v. 15, p. , 2017.
0219-7200
1757-6334
WOS:000397104400008
10.1142/S0219720017500020
Autor
Lintzmayer
Carla Negri; Fertin
Guillaume; Dias
Zanoni
Institución
Resumen
Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) 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. 15 1 Sao Paulo Research Foundation FAPESP [2013/01172-0, 2014/20738-7, 2014/19401-8, 2013/08293-7, 2015/11937-9, 2016/14132-4] National Counsel of Technological and Scientific Development CNPq [477692/2012-5, 483370/2013-4] Brazilian Federal Agency Evaluation of Graduate Education French Committee Scientific Cooperation with Brazil COFECUB [831/15] Capes Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)