Heurísticas para o Problema de Partição de Strings Comuns Mínima

  • Wallesson C. S. UFC
  • Paulo Henrique M. A. UFC
  • Fábio C. S. D. UFC
  • Emanuel F. C. UFC
  • Criston P. S. UFC
DOI: https://doi.org/10.5753/etc.2022.222576

Resumo


O grande número de dados disponíveis relacionados à biologia computacional torna necessários estudos em busca de melhores análises e ferramentas. Um problema que surge neste campo é chamado de problema de Partição de Strings Comuns Mínima (em inglês MCSP). Este trabalho apresenta duas heurísticas dentro de um ambiente controlado por tempo. Para isso, executamos experimentos com instâncias artificiais e realistas para avaliar o desempenho de tais heurísticas. Pelos resultados dos experimentos, vemos que uma das heurísticas é promissora, embora seus resultados não supere o "estado da arte".

Palavras-chave: algoritmos heurísticos, biologia computacional, heurísticas

Referências

C. Blum, J. A. L. and Davidson, P. (2015). Mathematical programming strategies for solving the minimum common string partition problem. European Journal of Operational Research, 242(3):769–777.

Ferdous, S. M. and Rahman, M. S. (2013). Solving the minimum common string partition problem with the help of ants. Mathematics in Computer Science, 11(2):233–249.

M. Crobak, P. K. and J.Sgall (2004). The greedy algorithm for the minimum common string partition problem. ACM Transactions Algorithims, 1(2):250–366.
Publicado
31/07/2022
Como Citar

Selecione um Formato
S., Wallesson C.; A., Paulo Henrique M.; D., Fábio C. S.; C., Emanuel F.; S., Criston P.. Heurísticas para o Problema de Partição de Strings Comuns Mínima. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 9-12. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2022.222576.