### Abstract

Original language | English |
---|---|

Pages (from-to) | 239-262 |

Number of pages | 24 |

Journal | Journal of Heuristics |

Volume | 18 |

Issue number | 2 |

DOIs | |

Publication status | Published - Apr 2012 |

### Fingerprint

### Keywords

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

### Cite this

*Journal of Heuristics*,

*18*(2), 239-262. https://doi.org/10.1007/s10732-011-9177-z

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

Research output: Contribution to journal › Article

*Journal of Heuristics*, vol. 18, no. 2, pp. 239-262. https://doi.org/10.1007/s10732-011-9177-z

}

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 -