Longest common substring in Longest Common Subsequence's solution service: A novel hyper-heuristic.

Area of Science:

• Computational Biology
• Computer Science
• Algorithm Development

Background:

• The Longest Common Subsequence (LCS) problem is crucial in areas like computational biology and text editing.
• Existing heuristic algorithms for LCS struggle with diverse string set types and lack efficient classification methods.
• Current hyper-heuristics for LCS are often too slow for real-world applications.

Purpose of the Study:

• To propose a novel hyper-heuristic approach for solving the Longest Common Subsequence (LCS) problem.
• To introduce a new criterion for classifying string sets based on similarity.
• To develop an efficient and fast hyper-heuristic for real-world LCS applications.

Main Methods:

• Developed a general stochastic framework for identifying string set types.
• Introduced the Set Similarity Dichotomizer (S²D) algorithm to classify string sets into two types.
• Proposed a hyper-heuristic that utilizes S²D and string properties to select the optimal heuristic.

Main Results:

• The S²D algorithm achieved 98% accuracy in classifying datasets.
• The proposed hyper-heuristic demonstrated competitive performance against existing methods.
• Outperformed existing hyper-heuristics on uncorrelated datasets in solution quality and runtime.

Conclusions:

• The S²D algorithm provides an effective method for string set classification in LCS problems.
• The novel hyper-heuristic offers an efficient and accurate solution for the LCS problem, especially for uncorrelated datasets.
• Open-source code and datasets are available on GitHub, facilitating further research and application.