Approximation Algorithms For Sorting By Length-weighted Prefix And Suffix Operations

dc.creatorLintzmayer
dc.creatorCarla Negri; Fertin
dc.creatorGuillaume; Dias
dc.creatorZanoni
dc.date2015-AUG
dc.date2016-06-07T13:34:49Z
dc.date2016-06-07T13:34:49Z
dc.date.accessioned2018-03-29T01:50:25Z
dc.date.available2018-03-29T01:50:25Z
dc.identifier
dc.identifierApproximation Algorithms For Sorting By Length-weighted Prefix And Suffix Operations. Elsevier Science Bv, v. 593, p. 26-41 AUG-2015.
dc.identifier0304-3975
dc.identifierWOS:000358624500003
dc.identifier10.1016/j.tcs.2015.05.039
dc.identifierhttp://www.sciencedirect.com/science/article/pii/S0304397515004818
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/243993
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1307691
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.descriptionThe 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.
dc.description593
dc.description
dc.description
dc.description26
dc.description41
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.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.descriptionFAPESP [2013/01172-0, 2014/20738-7, 2014/19401-8, 2013/08293-7]
dc.descriptionCNPq [477692/2012-5, 483370/2013-4]
dc.descriptionCAPES [831/15]
dc.description
dc.description
dc.description
dc.languageen
dc.publisherELSEVIER SCIENCE BV
dc.publisher
dc.publisherAMSTERDAM
dc.relationTHEORETICAL COMPUTER SCIENCE
dc.rightsembargo
dc.sourceWOS
dc.subjectSigned Permutations
dc.subject1.375-approximation Algorithm
dc.subject2-approximation Algorithm
dc.subjectReversals
dc.subjectTranspositions
dc.subjectRearrangement
dc.subjectBounds
dc.subjectTime
dc.titleApproximation Algorithms For Sorting By Length-weighted Prefix And Suffix Operations
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución