Heuristics for the Minimum Common String Partition problem

  • 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

Abstract


The large number of available data related to computational biology makes studies necessary in search of better analyzes and tools. A problem that arises in this field is called Minimum Common String Partition problem (MCSP). This work presents two heuristics within a time-controlled environment. For that, we run experiments with artificial and realistic instances to evaluate the performance of such heuristics. By the results of the experiments, we see that one of the heuristics is promising, although its results do not surpass those of the "state of the art".

Keywords: heuristics algorithms, computational biology, heuristics

References

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.
Published
2022-07-31
How to Cite

Select a Format
S., Wallesson C.; A., Paulo Henrique M.; D., Fábio C. S.; C., Emanuel F.; S., Criston P.. Heuristics for the Minimum Common String Partition problem. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.