کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
15208 | 1391 | 2012 | 13 صفحه PDF | دانلود رایگان |

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.
Figure optionsDownload as PowerPoint slideHighlights
► The Longest Common Subsequence (LCS) problem is used in molecular biology to compare DNA or RNA sequences.
► LCS is used to determine homology in macromolecules.
► More similar sequences imply more similarity in structures and functions of bimolecular sequences.
► HH-LCS achieves longer common subsequences than the other algorithms.
► HH-LCS is also remarkably fast.
Journal: Computational Biology and Chemistry - Volume 36, February 2012, Pages 42–54