The closest string problem (CSP) consists in finding a string t with minimum Hamming distance from the strings of a given finite input set. To overcome its NP-hardness, we propose a simulated annealing approach along with a new heuristic for finding a good initial solution for the problem, which allows one to speed up sensibly the convergence of the algorithm. To assess its effectiveness and robustness, we extensively compared our approach with the integer-programming (IP) exact solution, and with other heuristic approaches present in the literature, both on artificial and real instances. Experimental results show that our approach allows one to locate good solutions for the problem, that are close to the optimum found by the IP formulation and outperforms other heuristic methods for the CSP.

A Combined Greedy-Walk Heuristic and Simulated Annealing Approach for the Closest String Problem

CANTONE, Domenico;
2014

Abstract

The closest string problem (CSP) consists in finding a string t with minimum Hamming distance from the strings of a given finite input set. To overcome its NP-hardness, we propose a simulated annealing approach along with a new heuristic for finding a good initial solution for the problem, which allows one to speed up sensibly the convergence of the algorithm. To assess its effectiveness and robustness, we extensively compared our approach with the integer-programming (IP) exact solution, and with other heuristic approaches present in the literature, both on artificial and real instances. Experimental results show that our approach allows one to locate good solutions for the problem, that are close to the optimum found by the IP formulation and outperforms other heuristic methods for the CSP.
bioinformatics; closest string problem; computational biology; heuristics; NP-hard problems; simulated-annealing
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.11769/15875
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact