A GRASP algorithm for the Closest String Problem using a probability-based heuristic

Sayyed Rasoul Mousavi, Navid Nasr Esfahani

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


The Closest String Problem (CSP) is the problem of finding a string whose Hamming distance from the members of a given set of strings of the same length is minimal. It has applications, among others, in bioinformatics and in coding theory. Several approximation and (meta)heuristic algorithms have been proposed for the problem to achieve 'good' but not necessarily optimal solutions within a reasonable time. In this paper, a new algorithm for the problem is proposed, based on a Greedy Randomized Adaptive Search Procedure (GRASP) and a novel probabilistic heuristic function. The algorithm is compared with three recently proposed algorithms for CSP, outperforming all of them by achieving solutions of higher quality within a few seconds in most of the experimental cases.

Original languageEnglish
Pages (from-to)238-248
Number of pages11
JournalComputers and Operations Research
Issue number2
Early online date2 Apr 2011
Publication statusPublished - Feb 2012
Externally publishedYes


  • Bioinformatics
  • Closest String Problem
  • Matheuristic
  • Metaheuristic
  • Sequence consensus

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research


Dive into the research topics of 'A GRASP algorithm for the Closest String Problem using a probability-based heuristic'. Together they form a unique fingerprint.

Cite this