Sorting Permutations By Prefix And Suffix Rearrangements

dc.creatorLintzmayer
dc.creatorCarla Negri; Fertin
dc.creatorGuillaume; Dias
dc.creatorZanoni
dc.date2017
dc.datefev
dc.date2017-11-13T13:55:23Z
dc.date2017-11-13T13:55:23Z
dc.date.accessioned2018-03-29T06:08:52Z
dc.date.available2018-03-29T06:08:52Z
dc.identifierJournal Of Bioinformatics And Computational Biology . Imperial College Press , v. 15, p. , 2017.
dc.identifier0219-7200
dc.identifier1757-6334
dc.identifierWOS:000397104400008
dc.identifier10.1142/S0219720017500020
dc.identifierhttp://www.worldscientific.com/doi/abs/10.1142/S0219720017500020
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/329635
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1366660
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionCoordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
dc.descriptionSome 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.
dc.description15
dc.description1
dc.descriptionSao Paulo Research Foundation
dc.descriptionFAPESP [2013/01172-0, 2014/20738-7, 2014/19401-8, 2013/08293-7, 2015/11937-9, 2016/14132-4]
dc.descriptionNational Counsel of Technological and Scientific Development
dc.descriptionCNPq [477692/2012-5, 483370/2013-4]
dc.descriptionBrazilian Federal Agency
dc.descriptionEvaluation of Graduate Education
dc.descriptionFrench Committee
dc.descriptionScientific Cooperation with Brazil
dc.descriptionCOFECUB [831/15]
dc.descriptionCapes
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionCoordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
dc.languageEnglish
dc.publisherImperial College Press
dc.publisherLondon
dc.relationJournal of Bioinformatics and computational Biology
dc.rightsfechado
dc.sourceWOS
dc.subjectPermutations
dc.subjectSorting
dc.subjectReversals
dc.subjectTranspositions
dc.subjectPrefix
dc.subjectSuffix
dc.subjectApproximation Algorithms
dc.subjectDiameter
dc.titleSorting Permutations By Prefix And Suffix Rearrangements
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución