DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación
Artículo científico (JournalArticle)
A learning search algorithm for the Restricted Longest Common Subsequence problem
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., The research of M. Djukanović is partially supported by the Ministry for Scientific and Technological Development and Higher Education of the Republic of Srpska, B&H in the course of the bilateral research project between B&H and Slovenia entitled “Theoretical and computational aspects of some graph problems with the application to graph network information spreading” under project no. 1259084 and the project “Application of deep learning in improving the efficiency of optimization algorithms” under project no. 1259114. A. Kartelj was supported by grant 451-03-47/2023-01/200104 funded by the Ministry of Science Technological Development and Innovations of the Republic of Serbia. J. Reixach and C. Blum are supported by grants TED2021-129319B-I00 and PID2022-136787NB-I00 funded by MCIN/AEI/10.13039/501100011033. A. Nikolikj and T. Eftimov acknowledge the support of the Slovenian Research and Innovation Agency through program grant P2-0098, project grants No. J2-4460 and No. GC-0001, BI-BA/24-25-006, and young researcher grant No. PR-12897 to AN. This work is also funded by the European Union under Grant Agreement 101187010 (HE ERA Chair AutoLearn-SI). The authors would like to acknowledge the use of the Computing Cluster Unit of the Institute of Logic and Computation at the Vienna University of Technology for this research project., Peer reviewed
Proyecto:
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023 TED2021-129319B-I00
,
AEI / HE PID2022-136787NB-I00
,
EC 101187010
DOI: http://hdl.handle.net/10261/392190, https://api.elsevier.com/content/abstract/scopus_id/105003991779
HANDLE: http://hdl.handle.net/10261/392190, https://api.elsevier.com/content/abstract/scopus_id/105003991779