Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Sorting permutations by prefix and suffix rearrangements

Texto completo
Autor(es):
Lintzmayer, Carla Negri ; Fertin, Guillaume ; Dias, Zanoni
Número total de Autores: 3
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY; v. 15, n. 1 FEB 2017.
Citações Web of Science: 3
Resumo

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. (AU)

Processo FAPESP: 14/19401-8 - Algoritmos para rearranjos de genomas
Beneficiário:Zanoni Dias
Linha de fomento: Auxílio à Pesquisa - Regular
Processo FAPESP: 13/01172-0 - O problema da ordenação de permutações usando operações de prefixo e sufixo
Beneficiário:Carla Negri Lintzmayer
Linha de fomento: Bolsas no Brasil - Doutorado Direto
Processo FAPESP: 13/08293-7 - CECC - Centro de Engenharia e Ciências Computacionais
Beneficiário:Munir Salomao Skaf
Linha de fomento: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
Beneficiário:Flávio Keidi Miyazawa
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 14/20738-7 - Ordenação de permutações por reversões de prefixo e reversões de sufixo
Beneficiário:Carla Negri Lintzmayer
Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - Doutorado Direto
Processo FAPESP: 16/14132-4 - Empacotamentos uni e bidimensionais com restrições de conflitos e remoções
Beneficiário:Carla Negri Lintzmayer
Linha de fomento: Bolsas no Brasil - Pós-Doutorado