Pinacho Davidson, Pedro PabloChacón Sartori, CamiloIsla Pino, Martín Ignacio2026-04-282026-04-282025https://repositorio.udec.cl/handle/11594/13977Tesis presentada para optar al título de Ingeniero/a en Civil Informático(a).El problema de la subsecuencia de racha más larga (LRS) es un desafío de optimización combinatoria NP-hard con aplicaciones en bioinformática, particularmente en el reensamblaje de genomas. Esta investigación aborda el LRS mediante el diseño, implementación y evaluación comparativa de diversas estrategias heurísticas y metaheurísticas, con el objetivo de explorar mejoras en la calidad de las soluciones respecto al estado del arte. Entre las técnicas evaluadas, destaca particularmente una propuesta innovadora que combina el algoritmo BRKGA (Biased Random Key Genetic Algorithm) con modelos de lenguaje (LLMs), demostrando que esta integración supera el rendimiento del BRKGA clásico, actualmente considerado el método más robusto para este problema. Los experimentos revelaron que, si bien el BRKGA tradicional mantiene un buen desempeño general, la versión híbrida con LLMs logra mejores resultados, especialmente en instancias complejas con alfabetos de gran tamaño, donde las técnicas convencionales presentan limitaciones. Estos resultados destacan la aplicabilidad de este enfoque en nuevas líneas de investigación para el procesamiento de secuencias genómicas, representando un avance significativo en la resolución eficiente del problema, con implicaciones directas en el campo de la bioinformática.The Longest Run Subsequence (LRS) problem is an NP-hard combinatorial optimization challenge with applications in bioinformatics, particularly in genome reassembly. This research addresses LRS through the design, implementation, and comparative evaluation of various heuristic and metaheuristic strategies, aiming to improve solution quality beyond the current stateof- the-art. Among the evaluated techniques, an innovative approach combining the Biased Random Key Genetic Algorithm (BRKGA) with Large Language Models (LLMs) stands out. This hybrid method demonstrates superior performance compared to classical BRKGA, which is currently the most robust solution for this problem. Experimental results reveal that while traditional BRKGA maintains strong overall performance, the LLM-enhanced hybrid version achieves better outcomes—particularly in complex instances with large alphabets, where conventional techniques face limitations. These findings highlight the applicability of this approach in new research directions for genomic sequence processing, representing a significant advance in efficiently solving the problem, with direct implications for bioinformatics.esCC BY-NC-ND 4.0 DEED Attribution-NonCommercial-NoDerivs 4.0 InternationalBioinformáticaHeurísticaAlgoritmosThesisINDUSTRIA, innovación, infraestructura