An efficient algorithm for the Closest String Problem

• Omar Vilca UFAM
• Rosiane de Freitas UFAM

DOI: https://doi.org/10.5753/etc.2016.9850

Resumo

The closest string problem that arises in computational molecular biology and coding theory is to find a string that minimizes the maximum Hamming distance from a given set of strings, the CSP is NP-hard problem. This article proposes an efficient algorithm for this problem with three strings. The key idea is to apply normalization for the CSP instance. This enables us to decompose the problem in five different cases corresponding to each position of the strings. Furthermore, an optimal solution can be easily obtained in linear time. A formal proof of the algorithm will be presented, also numerical experiments will show the effectiveness of the proposed algorithm.

 

Referências

Frances, M. and Litman, A. (1997). On covering problems of codes. Theory of Computing Systems, 30(2):113–119.

Gramm, J., Niedermeier, R., and Rossmanith, P. (2001). Exact solutions for closest string and related problems. In Proceedings of the 12th International Symposium on Algorithms and Computation, ISAAC ’01, pages 441–453.

Liu, X., Liu, S., Hao, Z., and Mauch, H. (2011). Exact algorithm and heuristic for the closest string problem. Computers & Operations Research, 38(11):1513–1520.

Meneses, C., Lu, Z., Oliveira, C., and Pardalos, P. (2004). Optimal solutions for the closest string problem via integer programming. INFORMS Journal on Computing, 16(4):419–429.

Meneses, C., Oliveira, C., and Pardalos, P. (2005). Optimization techniques for string selection and comparison problems in genomics. Engineering in Medicine and Biology Magazine, IEEE, 24(3):81–87.

Vilca, O. L. (2013). M´etodos para problemas de selec¸ ˜ao de cadeias de caracteres. Master’s thesis, Universidade Federal do ABC, Santo Andr´e, S˜ao Paulo.