An improved heuristic for the far from most strings problem

Seyed Rasoul Mousavi, Maryam Babaei, Manizheh Montazerian

    Research output: Contribution to journalArticlepeer-review

    19 Citations (Scopus)


    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
    Issue number2
    Publication statusPublished - Apr 2012


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


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

    Cite this