This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Meneses, C. N. Articles by Pardalos, P. M. Search for Related Content

Optimal Solutions for the Closest-String Problem via Integer Programming

Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, Gainesville, Florida 32611, USA
School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0205, USA
Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, Gainesville, Florida 32611, USA
Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, Gainesville, Florida 32611, USA
claudio{at}ufl.edu
zhaosong{at}isye.gatech.edu
oliveira{at}ufl.edu
pardalos{at}ufl.edu

In this paper we study the closest-string problem (CSP), which can be defined as follows: Given a finite set = {s¹, s², ..., sⁿ} of strings, each string with length m, find a center string t of length m minimizing d, such that for every string sⁱ , d_H(t, sⁱ) d. By d_H(t, sⁱ) we mean the Hamming distance between t and sⁱ. This is an NP-hard problem, with applications in molecular biology and coding theory. Even though there are good approximation algorithms for this problem, and exact algorithms for instances with d constant, there are no studies trying to solve it exactly for the general case. In this paper we propose three integer-programming (IP) formulations and a heuristic, which is used to provide upper bounds on the value of an optimal solution. We report computational results of a branch-and-bound algorithm based on one of the IP formulations, and of the heuristic, executed over randomly generated instances. These results show that it is possible to solve CSP instances of moderate size to optimality.

Key words: closest-string problem; computational biology; mathematical programming; branch-and-bound algorithms
History: received February 2004; revised March 2004; accepted April 2004.