dc.creatorGalvao
dc.creatorGustavo Rodrigues; Lee
dc.creatorOrlando; Dias
dc.creatorZanoni
dc.date2015-Mar
dc.date2016-06-07T13:21:02Z
dc.date2016-06-07T13:21:02Z
dc.date.accessioned2018-03-29T01:40:57Z
dc.date.available2018-03-29T01:40:57Z
dc.identifier
dc.identifierSorting Signed Permutations By Short Operations. Biomed Central Ltd, v. 10, p. Mar-2015.
dc.identifier1748-7188
dc.identifierWOS:000353469900001
dc.identifier10.1186/s13015-015-0040-x
dc.identifierhttp://almob.biomedcentral.com/articles/10.1186/s13015-015-0040-x
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/243006
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1306704
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.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
dc.descriptionBackground: During evolution, global mutations may alter the order and the orientation of the genes in a genome. Such mutations are referred to as rearrangement events, or simply operations. In unichromosomal genomes, the most common operations are reversals, which are responsible for reversing the order and orientation of a sequence of genes, and transpositions, which are responsible for switching the location of two contiguous portions of a genome. The problem of computing the minimum sequence of operations that transforms one genome into another - which is equivalent to the problem of sorting a permutation into the identity permutation - is a well-studied problem that finds application in comparative genomics. There are a number of works concerning this problem in the literature, but they generally do not take into account the length of the operations (i.e. the number of genes affected by the operations). Since it has been observed that short operations are prevalent in the evolution of some species, algorithms that efficiently solve this problem in the special case of short operations are of interest. Results: In this paper, we investigate the problem of sorting a signed permutation by short operations. More precisely, we study four flavors of this problem: (i) the problem of sorting a signed permutation by reversals of length at most 2; (ii) the problem of sorting a signed permutation by reversals of length at most 3; (iii) the problem of sorting a signed permutation by reversals and transpositions of length at most 2; and (iv) the problem of sorting a signed permutation by reversals and transpositions of length at most 3. We present polynomial-time solutions for problems (i) and (iii), a 5-approximation for problem (ii), and a 3-approximation for problem (iv). Moreover, we show that the expected approximation ratio of the 5-approximation algorithm is not greater than 3 for random signed permutations with more than 12 elements. Finally, we present experimental results that show that the approximation ratios of the approximation algorithms cannot be smaller than 3. In particular, this means that the approximation ratio of the 3-approximation algorithm is tight.
dc.description10
dc.description
dc.description
dc.description
dc.description
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.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
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.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
dc.descriptionFAPESP [2014/04718-6]
dc.descriptionCNPq [303947/2008-0, 477692/2012-5]
dc.descriptionCNPq [477692/2012-5, 306730/2012-0, 483370/2013-4]
dc.descriptionFAPESP [2013/08293-7]
dc.description
dc.description
dc.description
dc.languageen
dc.publisherBIOMED CENTRAL LTD
dc.publisher
dc.publisherLONDON
dc.relationAlgorithms for Molecular Biology
dc.rightsaberto
dc.sourceWOS
dc.subjectLength-weighted Reversals
dc.subject1.375-approximation Algorithm
dc.subjectGenome Rearrangements
dc.subjectBlock-moves
dc.subjectTranspositions
dc.subjectInversions
dc.titleSorting Signed Permutations By Short Operations
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución