An improved heuristic for the far from most strings problem

Seyed Rasoul Mousavi, Maryam Babaei, Manizheh Montazerian

Research output: Contribution to journalArticle

14 Citations (Scopus)

Abstract

The Far From Most Strings Problem (FFMSP) asks for a string that is far from as many as possible of a given set of strings. All the input and the output strings are of the same length, and two strings are far if their Hamming distance is greater than or equal to a given threshold. FFMSP belongs to the class of sequence consensus problems which have applications in molecular biology, amongst others. FFMSP is NP-hard. It does not admit a constant-ratio approximation either, unless P=NP. In the last few years, heuristic and metaheuristic algorithms have been proposed for the problem, which use local search and require a heuristic, also called an evaluation function, to evaluate candidate solutions during local search. The heuristic function used, for this purpose, in these algorithms is the problem’s objective function. However, since many candidate solutions can be of the same objective value, the resulting search landscape includes many points which correspond to local maxima. In this paper, we devise a new heuristic function to evaluate candidate solutions. We then incorporate the proposed heuristic function within a Greedy Randomized Adaptive Search Procedure (GRASP), a metaheuristic originally proposed for the problem by Festa. The resulting algorithm outperforms state-of-the-art with respect to solution quality, in some cases by orders of magnitude, on both random and real data in our experiments. The results indicate that the number of local optima is considerably reduced using the proposed heuristic.
Original languageEnglish
Pages (from-to)239-262
Number of pages24
JournalJournal of Heuristics
Volume18
Issue number2
DOIs
Publication statusPublished - Apr 2012

Keywords

  • Bioinformatics
  • Evaluation functions
  • Far from most strings problem
  • Heuristic functions
  • Local optima
  • Matheuristic
  • Metaheuristics
  • Sequence consensus

Fingerprint Dive into the research topics of 'An improved heuristic for the far from most strings problem'. Together they form a unique fingerprint.

  • Cite this