A hyper-heuristic for the Longest Common Subsequence problem

Farzaneh Sadat Tabataba, Sayyed Rasoul Mousavi

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


The Longest Common Subsequence Problem is the problem of finding a longest string that is a subsequence of every member of a given set of strings. It has applications in FPGA circuit minimization, data compression, and bioinformatics, among others. The problem is NP-hard in its general form, which implies that no exact polynomial-time algorithm currently exists for the problem. Consequently, inexact algorithms have been proposed to obtain good, but not necessarily optimal, solutions in an affordable time. In this paper, a hyper-heuristic algorithm incorporated within a constructive beam search is proposed for the problem. The proposed hyper-heuristic is based on two basic heuristic functions, one of which is new in this paper, and determines dynamically which one to use for a given problem instance. The proposed algorithm is compared with state-of-the-art algorithms on simulated and real biological sequences. Extensive experimental reveals that the proposed hyper-heuristic is superior to the state-of-the-art methods with respect to the solution quality and the running-time.

Original languageEnglish
Pages (from-to)42-54
Number of pages13
JournalComputational Biology and Chemistry
Early online date30 Dec 2011
Publication statusPublished - Feb 2012
Externally publishedYes


  • Heuristic functions
  • Hyper-heuristic algorithms
  • Longest Common Subsequence
  • Sequence analysis
  • Tree search

ASJC Scopus subject areas

  • Structural Biology
  • Biochemistry
  • Organic Chemistry
  • Computational Mathematics


Dive into the research topics of 'A hyper-heuristic for the Longest Common Subsequence problem'. Together they form a unique fingerprint.

Cite this