Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10346566 | Computers & Operations Research | 2011 | 8 Pages |
Abstract
The Closest String Problem (CSP) is an NP-hard problem, which arises in computational molecular biology and coding theory. This class of problems is to find a string that minimizes the maximum Hamming distance to a given set of strings. In this paper, we present an exact algorithm called Distance First Algorithm (DFA) for three strings of CSP with alphabet size two. For the general CSP, we design a polynomial heuristic which is a combination of our proposed approximation algorithm LDDA ([10] Liu Xiaolan, Fu Keqiang, Shao Renxiang. Largest distance decreasing algorithm for the Closest String Problem. Journal of Information & Computational Science 2004; 1(2): 287-92) and local search strategies. Numerical results show that the proposed heuristic may obtain a nearly optimal value in a reasonable time for small and large-scale instances of the CSP.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Xiaolan Liu, Shenghan Liu, Zhifeng Hao, Holger Mauch,