1. A hyper-heuristic for the Longest Common Subsequence problem
- Author
-
Tabataba, Farzaneh Sadat and Mousavi, Sayyed Rasoul
- Subjects
- *
FIELD programmable gate arrays , *DATA compression , *BIOINFORMATICS , *ALGORITHMS , *POLYNOMIALS , *PROBLEM solving - Abstract
Abstract: 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. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF