| 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 |