A learning search algorithm for the Restricted Longest Common Subsequence problem

Resumen

Este artículo aborda el problema de Subsecuencia Común Más Larga Restringida (RLCS), una extensión del bien conocido problema de Subsecuencia Común Más Larga (LCS). Este problema tiene aplicaciones significativas en bioinformática, particularmente para identificar similitudes y descubrir patrones mutuos y motivos importantes entre secuencias de ADN, ARN y proteínas. Construyendo sobre avances recientes en resolver este problema a través de un marco general de búsqueda, este artículo introduce dos enfoques heurísticos novedosos diseñados para mejorar el proceso de búsqueda dirigiéndolo hacia regiones prometedoras en el espacio de búsqueda. La primera heurística emplea un modelo probabilístico para evaluar soluciones parciales durante el proceso de búsqueda. La segunda heurística está basada en un modelo de red neuronal entrenado offline usando un algoritmo genético. Un aspecto clave de este enfoque es extraer características específicas del problema de soluciones parciales y la instancia completa del problema. Un método híbrido efectivo, referido como búsqueda en haz con aprendizaje, se desarrolla combinando el modelo de red neuronal entrenado con un marco de búsqueda en haz. Una contribución importante de este artículo se encuentra en la generación de instancias del mundo real donde resúmenes científicos sirven como cadenas de entrada, y un conjunto de palabras académicas frecuentemente ocurrentes de la literatura se usan como patrones restringidos. Evaluaciones experimentales comprensivas demuestran la efectividad de los enfoques propuestos en resolver el problema RLCS. Finalmente, se aplica un análisis empírico de explicabilidad a los resultados obtenidos. De esta manera, se identifican combinaciones de características clave y sus contribuciones respectivas al éxito o fracaso de los algoritmos a través de diferentes tipos de problema.

Citar Esta Publicación

Djukanović, M., Reixach, J., Nikolikj, A., Eftimov, T., Kartelj, A., & Blum, C. (2025). A learning search algorithm for the Restricted Longest Common Subsequence problem. Expert Systems with Applications, 127731.