Resumen de Algoritmos, estructuras y heurísticos para minería de cadenas
TÍTULO DE LA TESIS: ALGORITMOS, ESTRUCTURAS Y HEURÍSTICOS PARA MINERÍA DE CADENAS RESUMEN: El descubrimiento de factores interesantes a partir de cadenas de gran longitud es un problema con diversas aplicaciones, como la minería de Biosecuencias.
En esta tesis se analiza la complejidad de cadenas respecto al número de factores frecuentes. Se determina la cota máxima de factores frecuentes en una cadena y la reducción de la complejidad al evitar factores solapados. Se aporta una nueva solución general para el problema de exclusión de factores. Se define el "grafo de solapamientos de subcadenas'", que permite obtener una representación visual de la complejidad de una cadena.
El segundo conjunto de aportaciones se centra en la definición de algoritmos y métodos, basados en los resultados teóricos, para el análisis y minería de cadenas. Desarrollamos un nuevo algoritmo, SANSPOS, para analizar factores frecuentes en cadenas de gran longitud. Este algoritmo utiliza una estructura de datos arbórea, SP-Trie, y una estrategia de posicionamiento basada en la definición de "matrices de posicionamiento". Gracias al uso de este tipo de matrices podemos incorporar, en el algoritmo SANSPOS, heurísticas de poda, para el árbol SP-Trie, con un coste computacional mínimo.
Por último, diseñamos un nuevo marco de trabajo para la selección de medidas del interés apropiadas para la minería de cadenas. Este marco se basa en la obtención de un modelo, mediante algoritmos de aprendizaje automático, para clasificar factores según su interés.
