AN EXACT METHOD IN DYNAMIC PROGRAMMING FOR THE CLOSEST STRING PROBLEM

The Closest String Problem (CSP) that arises in computational molecular biology, coding theory and web searching is to find a string that minimizes the maximum Hamming distance from a given set of strings, the CSP is NP-hard problem. Several approximation and exact algorithms have been proposed for the problem to achieve optimal solutions using Mixed Integer Linear Programming. This paper proposes a new algorithm for the problem, based on dynamic programming. The algorithm is compared with an integer programming formulation for CSP. Furthermore, computational experiments in comparison tables will show the effectiveness of the proposed algorithm.