TY - JOUR

T1 - Optimal solutions for the closest-string problem via integer programming

AU - Meneses, Cláudio N.

AU - Lu, Zhaosong

AU - Oliveira, Carlos A.S.

AU - Pardalos, Panos M.

N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.

PY - 2004/9

Y1 - 2004/9

N2 - In this paper we study the closest-string problem (CSP), which can be defined as follows: Given a finite set ℒ = [s1, s 2,...,sn} of strings, each string with length m, find a center string t of length m minimizing d, such that for every string s i ∈ ℒ, dH(t, si) ≤ d. By d H(t, si) we mean the Hamming distance between t and s i. 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.

AB - In this paper we study the closest-string problem (CSP), which can be defined as follows: Given a finite set ℒ = [s1, s 2,...,sn} of strings, each string with length m, find a center string t of length m minimizing d, such that for every string s i ∈ ℒ, dH(t, si) ≤ d. By d H(t, si) we mean the Hamming distance between t and s i. 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.

KW - Branch-and-bound algorithms

KW - Closest-string problem

KW - Computational biology

KW - Mathematical programming

UR - http://www.scopus.com/inward/record.url?scp=10044284095&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=10044284095&partnerID=8YFLogxK

U2 - 10.1287/ijoc.1040.0090

DO - 10.1287/ijoc.1040.0090

M3 - Article

AN - SCOPUS:10044284095

VL - 16

SP - 419

EP - 429

JO - ORSA journal on computing

JF - ORSA journal on computing

SN - 0899-1499

IS - 4

ER -