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

Fingerprint

Strings
Heuristics
Hamming distance
Molecular biology
Function evaluation
Metaheuristics
Local Search
Computational complexity
Greedy Randomized Adaptive Search Procedure
Consensus Problem
Evaluate
Molecular Biology
Hamming Distance
Evaluation Function
NP-complete problem
Objective function
Experiments
Output
Approximation
Experiment

Keywords

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

Cite this

An improved heuristic for the far from most strings problem. / Mousavi, Seyed Rasoul; Babaei, Maryam; Montazerian, Manizheh.

In: Journal of Heuristics, Vol. 18, No. 2, 04.2012, p. 239-262.

Research output: Contribution to journalArticle

Mousavi, Seyed Rasoul ; Babaei, Maryam ; Montazerian, Manizheh. / An improved heuristic for the far from most strings problem. In: Journal of Heuristics. 2012 ; Vol. 18, No. 2. pp. 239-262.
@article{889747f5782e4003b7f1378c7721d5cf,
title = "An improved heuristic for the far from most strings problem",
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.",
keywords = "Bioinformatics, Evaluation functions, Far from most strings problem, Heuristic functions, Local optima, Matheuristic, Metaheuristics, Sequence consensus",
author = "Mousavi, {Seyed Rasoul} and Maryam Babaei and Manizheh Montazerian",
year = "2012",
month = "4",
doi = "10.1007/s10732-011-9177-z",
language = "English",
volume = "18",
pages = "239--262",
journal = "Journal of Heuristics",
issn = "1381-1231",
publisher = "Springer",
number = "2",

}

TY - JOUR

T1 - An improved heuristic for the far from most strings problem

AU - Mousavi, Seyed Rasoul

AU - Babaei, Maryam

AU - Montazerian, Manizheh

PY - 2012/4

Y1 - 2012/4

N2 - 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.

AB - 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.

KW - Bioinformatics

KW - Evaluation functions

KW - Far from most strings problem

KW - Heuristic functions

KW - Local optima

KW - Matheuristic

KW - Metaheuristics

KW - Sequence consensus

U2 - 10.1007/s10732-011-9177-z

DO - 10.1007/s10732-011-9177-z

M3 - Article

VL - 18

SP - 239

EP - 262

JO - Journal of Heuristics

JF - Journal of Heuristics

SN - 1381-1231

IS - 2

ER -