A hyper-heuristic for the Longest Common Subsequence problem

作者：Tabataba Farzaneh Sadat^*; Mousavi Sayyed Rasoul

来源：Computational Biology and Chemistry, 2012, 36: 42-54.

DOI：10.1016/j.compbiolchem.2011.12.004

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

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.

• 出版日期2012-2