Combinatorial Approaches for the Closest String Problem

Abstract

The closest string problem (CSP) 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 an NP-hard problem. The main aim of this work is to propose exact methods for this problem, for this purpose, we characterize special cases for this problem with emphasis in the number of strings. Until now our contribution is: linear-time algorithms for CSP with up to three strings and for four binary strings, in addition to an heuristic greedy algorithm and a recursive exact algorithm for CSP for the general case. Furthermore, for each proposed algorithm formal proofs will be presented, also numerical experiments will show the effectiveness of the proposed algorithms.