# A Learning Search Algorithm for the Restricted Longest Common Subsequence Problem

arXiv: https://arxiv.org/abs/2410.12031 · HTML: https://mlsanity.com/paper/2410.12031/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 49 references that are in the map.
- First posted on arXiv 15 Oct 2024.

## Builds on (most cited first, 6 of 6)

- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Parallax: Sparsity-aware Data Parallel Training of Deep Neural Networks](https://mlsanity.com/paper/1808.02621/) (2018)
- [Explanation of Machine Learning Models Using Shapley Additive Explanation and Application for Real Data in Hospital](https://mlsanity.com/paper/2112.11071/) (2021)
- [A Hybrid Evolutionary Algorithm Based on Solution Merging for the Longest Arc-Preserving Common Subsequence Problem](https://mlsanity.com/paper/1702.00318/) (2017)

## Built on by (most cited first, 2 of 2)

- [Graph Instance Landscapes: When Structural Similarity Does (Not) Reflect Shortest-Path Performance](https://mlsanity.com/paper/2606.18267/) (2026)
- [Neuro-Evolved Heuristics for Variable Gapped Common Subsequence Identification](https://mlsanity.com/paper/2608.00888/) (2026)

## Abstract (arXiv)

This paper addresses the Restricted Longest Common Subsequence (RLCS) problem, an extension of the well-known Longest Common Subsequence (LCS) problem. This problem has significant applications in bioinformatics, particularly for identifying similarities and discovering mutual patterns and important motifs among DNA, RNA, and protein sequences. Building on recent advancements in solving this problem through a general search framework, this paper introduces two novel heuristic approaches designed to enhance the search process by steering it towards promising regions in the search space. The first heuristic employs a probabilistic model to evaluate partial solutions during the search process. The second heuristic is based on a neural network model trained offline using a genetic algorithm. A key aspect of this approach is extracting problem-specific features of partial solutions and the complete problem instance. An effective hybrid method, referred to as the learning beam search, is developed by combining the trained neural network model with a beam search framework. An important contribution of this paper is found in the generation of real-world instances where scientific abstracts serve as input strings, and a set of frequently occurring academic words from the literature are used as restricted patterns. Comprehensive experimental evaluations demonstrate the effectiveness of the proposed approaches in solving the RLCS problem. Finally, an empirical explainability analysis is applied to the obtained results. In this way, key feature combinations and their respective contributions to the success or failure of the algorithms across different problem types are identified.