Busca avançada
Ano de início
Entree


Heuristics for the Sorting Signed Permutations by Reversals and Transpositions Problem

Texto completo
Autor(es):
Brito, Klairton Lima ; Oliveira, Andre Rodrigues ; Dias, Ulisses ; Dias, Zanoni ; Jansson, J ; MartinVide, C ; VegaRodriguez, MA
Número total de Autores: 7
Tipo de documento: Artigo Científico
Fonte: ALGORITHMS FOR COMPUTATIONAL BIOLOGY (ALCOB 2018); v. 10849, p. 11-pg., 2018-01-01.
Resumo

We present two heuristics, Sliding Window and Look Ahead, to improve solutions for the Sorting Signed Permutations by Reversals and Transpositions Problem. To assess the heuristics, we implemented algorithms described in the literature to provide initial solutions. Despite the fact that we addressed a specific problem, both heuristics can be applied to many others within the area of genome rearrangement. When time is a crucial factor, Sliding Window is a better choice because it runs in linear time and improves the initial solutions in 76.4% of cases. If the quality of the solution is a priority, Look Ahead should be preferred because it improves the initial solutions in 97.6% of cases, but it runs in O(n(3) x alg(n)), where alg(n) is the complexity of the algorithm given as input. By using these heuristics one may find a good tradeoff between running time and solution improvement. (AU)

Processo FAPESP: 14/19401-8 - Algoritmos para rearranjos de genomas
Beneficiário:Zanoni Dias
Modalidade de apoio: Auxílio à Pesquisa - Regular
Processo FAPESP: 13/08293-7 - CECC - Centro de Engenharia e Ciências Computacionais
Beneficiário:Munir Salomao Skaf
Modalidade de apoio: 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
Modalidade de apoio: Auxílio à Pesquisa - Temático