Reconocimiento de patrones

En este trabajo se plantea resolver los siguientes problemas mediante el uso de árboles de sufijos:

1. El problema de la búsqueda exacta de patrones (el problema clásico de RP), esto es, encontrar cuántas veces está un patrón P está en un texto T.
2. El problema de la subcadena común más larga, conocido como el problema LCS, esto es, encontrar la subcadena más larga que está en dos cadenas dadas S1 y S2.
3. El problema de la contaminación del ADN, esto es, dada una cadena S, compuesta por la combinación de varias subcadenas conocidas de ADN, encontrar todas las subcadenas de S que están en T y que tienen longitud mayor que cierto valor l. Si se encuentran esas subcadenas, diremos que la muestra T está contaminada.

Para estos problemas se dan los siguientes ficheros:

PROBLEMA 1: Búsqueda exacta de patrones.

PATRÓN	Comodín	TEXTO	Alfabeto
ST1-Pattern1.txt	No	ST1-Text1.txt	Binario
ST1-Pattern2.txt	No	ST1-Text2.txt	Adn
ST1-Pattern3.txt	Sí, carácter="0"	ST1-Text3.txt	Adn

PROBLEMA 2: Subcadena común más larga. Se trata de encontrar la LCS entre las cadenas String1 y String2 y String3 y String4, dadas en los ficheros de más abajo.

CADENA 1	CADENA 2	Alfabeto
ST1-LCS-String1.txt	ST1-LCS-String2.txt	Adn
ST1-LCS-String3.txt	ST1-LCS-String4.txt	Adn

PROBLEMA 3: Búsqueda de contaminación de Adn. El umbral de reconocimiento de contaminación es l=30. Queremos buscar contaminación de Adn en dos muestras String1 y String2 sacando la base de datos de posibles contaminantes de la cadena Source.

Fichero	Descripción	Alfabeto
ST1-Contamination-Source.txt	Base de datos de contaminantes	Adn
ST1-Contamination-String1.txt	String1	Adn
ST1-Contamination-String2.txt	String2	Adn