Ant-CSP: An Ant Colony Optimization Algorithm for the Closest String Problem

Algorithms for sequence analysis are of central importance in computational molecular biology and coding theory. A very interesting problem in this field is the Closest String Problem (CSP) which consists in finding a string t with minimum Hamming distance from all strings in a given finite set. To overcome the NP-hardness of the CSP problem, we propose a new algorithm, called Ant-CSP, based on the Ant Colony Optimization metaheuristic. To assess its effectiveness and robustness, we compared it with two state-of-the-art algorithms for the CSP problem, respectively based on the simulated annealing and the genetic algorithm approaches. Experimental results show that Ant-CSP outperforms both of them in terms of quality of solutions and convergence speed.