Estudio comparativo de algoritmos para el problema de la subsecuencia común más larga restringida / Comparative study of algorithms for the constrained longest common subsequence problem

摘要

Esta tesis describe el problema de la subsecuencia común más larga y específicamente una de sus extensiones, el problema de la subsecuencia común más larga restringida. Esta es una de las operaciones de comparación más importantes sobre las secuencias y su aplicación es diversa en muchas áreas, especialmente en la bioinformática. Principalmente esta tesis tiene dos contribuciones, i) el proponer un nuevo algoritmo para solucionar el problema de la subsecuencia común más larga restringida basado en el concepto de dominancia y ii) la realización de una evaluación experimental de los algoritmos más representativos para solucionar el problema de la subsecuencia común más larga restringida incluyéndose el algoritmo propuesto. El trabajo se complementa con una descripción de las técnicas más usuales para solucionar el problema de la subsecuencia común más larga como base para realizar posteriores trabajos en técnicas no aplicadas para solucionar el problema de la subsecuencia común más larga restringida. / Abstract. This thesis focuses on the longest common subsequence problem. Specifically, it focuses on one of its extensions, the constrained longest common subsequence problem (CLCS). The CLCS problem is one of the most important comparison operations on sequences, where its application is diverse in many areas, especially in bioinformatics. This thesis has two main contributions, i) To propose a new algorithm to solve the constrained longest common subsequence problem based on the concept of dominance, and ii) To perform an experimental evaluation of the most representative CLCS algorithms including the proposed algorithm. The work is complemented with a description of the state of the art techniques to solve the longest common subsequence problem. This description will be the basis of further work, which will pretend the development of novel techniques to solve the constrained longest common subsequence problem.