Exact algorithm and heuristic for the Closest String Problem

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.

Introduction

For many problems in computational biology, there is a need to compare and find common features in sequences. In this paper, we study one such problem, known as the Closest String Problem (CSP). The CSP has many important applications not only in computational biology, but also in other areas such as coding theory. In coding theory, the objective is to find sequences of characters which are closest to some given set of strings. This is useful in determining the best way of encoding a set of messages [1].

Let $A=\{a_1,\dots ,a_{|A|}\}$ be a finite set of characters, from which strings can be constructed. Let A^m denote the set of all strings over A with length m. Then the CSP can be defined as follows: given a finite set of strings $S=\{s^1,s^2,\dots ,s^n\}$, each of which is in A^m, find a center string t of length m, such that for every string sⁱ in S, $d_H(s^i,t)\le d$. By $d_H(s^i,t)$ we mean the Hamming distance between sⁱ and t.

The CSP has been widely studied in recent years. It has been proved that CSP is NP-hard. However, if the distance d is fixed, the exact solution to the problem can be found in polynomial time [2]. For the general case where d is variable, there have proposed some approximation algorithms; for example, Gasieniec et al. [3] and Lanctot et al. [4] develop independently a 4/3-approximation algorithm, and Li et al. [5] presents a polynomial time approximation scheme (PTAS). These algorithms all need to solve an integer linear programming, so solving large-size instances of the CSP may take a long time. Meneses et al. [6], [7] have shown empirically the practical use of integer programming techniques to solve moderate-size instances of the CSP. By moderate-size instances we mean instances with 10–30 strings each of which is 300–800 characters long. However, real-world instances are much larger and more difficult. Gomes et al. [8] propose a heuristic (Algorithm 1 in [8]) and implement the sequential and parallel versions of the algorithm. Later Gomes et al. [9] propose a slightly different version of the heuristic in [8] (Algorithm 1 in [9]) and run it on a parallel machine with 28 nodes for large-scale instances of the CSP.

In this paper, we present an exact algorithm called Distance First Algorithm (DFA) for the special case of CSP with n=3 strings and alphabet size |A|=2. Also, we design a polynomial heuristic that is a combination of our proposed approximation algorithm LDDA [10] and local search strategies [6]. The computational experiments show that the proposed heuristic is effective in solving small and large-scale instances of the CSP.

This paper is organized as follows. In Section 2, we introduce the integer programming formulation of CSP. Section 3 describes the exact algorithm for the special case of CSP with n=3 strings and alphabet size |A|=2 and gives its proof. Section 4 describes the proposed heuristic for solving small and large-scale instances of the CSP. Section 5 reports the numerical results of the proposed heuristic. Finally, some concluding remarks are given in Section 6.