Lenguajes, autómatas y gramáticas

Antecedentes

En este capítulo se hace una revisión sobre lenguajes, autómatas, gramáticas y el proceso

de inferencia gramatical, se muestran las diferentes medidas de información que calcula

WinGramm 2, se muestran los conceptos fundamentales sobre las secuencias biológicas a

analizar y se ejemplifica el uso de la complejidad gramatical en el análisis de

biosecuencias.

2.1 Lenguajes, autómatas y gramáticas

2.1.1 Conceptos preliminares

Un símbolo es un objeto o una entidad abstracta, como una letra o un dígito, base de

nuestra principal forma de comunicación: el lenguaje.

Un alfabeto es un conjunto finito de símbolos. Por ejemplo, el alfabeto romano: {a, b, ...,

z}, el alfabeto binario: {0, 1}. Cualquier objeto puede ser un símbolo en un alfabeto, pero

por simplicidad, se suele usar solamente letras, números u otros caracteres comunes.

Una cadena es una secuencia finita de símbolos tomados de un alfabeto. Por ejemplo aeiou

es una cadena sobre el alfabeto {a, b, ..., z}. Una cadena vacía es una cadena que no

contiene símbolos, y se denota como e. Los datos que una computadora manipula están

modelados matemáticamente por cadenas de símbolos.

La longitud de una cadena está dada por el número de símbolos que ésta contiene. Por

ejemplo, la longitud de la cadena aabb es

UNIVERSIDAD VERACRUZANA

FACULTAD DE FÍSICA E INTELIGENCIA ARTIFICIAL

MAESTRÍA EN INTELIGENCIA ARTIFICIAL

Aplicaciones de la Inteligencia Artificial

al análisis de Biosecuencias

TESIS

Que para obtener el grado de:

Maestro en Inteligencia Artificial

Presenta:

Julio César Sandria Reynoso

Director de tesis:

Dr. Miguel Angel Jiménez Montaño

Xalapa, Veracruz, MÉXICO Agosto 2003

Resumen

En esta tesis se presentan métodos para analizar secuencias biológicas (biosecuencias) así

como otros tipos de secuencias. Las biosecuencias son las secuencias de bases nucleótidas

y aminoácidos formadoras del ADN y las proteínas respectivamente. La enorme cantidad

de secuencias de ADN y proteínas en bases de datos públicas en todo el mundo hace

propicio usar diversas técnicas de inteligencia artificial para su adecuada manipulación y

análisis, como son la minería de datos, el aprendizaje de máquina, el reconocimiento de

patrones y el agrupamiento. Aunque existen ya una gran cantidad de programas para

analizar secuencias basados en diferentes algoritmos, la principal contribución de este

trabajo es el desarrollo de una herramienta de software para sistemas Windows y Linux:

WinGramm 2 y LinGramm 2, basada en el algoritmo Grammar, que calcula la complejidad

gramatical de una secuencia. Grammar es un algoritmo de compactación que encuentra

redundancia en secuencias, mediante el descubrimiento de patrones, a través de un proceso

de inferencia de gramáticas libres del contexto. Se ejemplifica el uso de esta herramienta

aplicándola al análisis de secuencias de ADN, proteínas y cartas en cadena.

Tesis Maestría en Inteligencia Artificial, Universidad Veracruzana Agosto 2003

iv

Agradecimientos

A mi esposa, por su amor y comprensión.

A mis hijos Carolina y Rafael, que le dieron un nuevo sentido a mi vida.

A mi madre, por haberme guiado correctamente hasta que tomé mi propio camino.

Al Dr. Manuel Martínez Morales, porque sin su ayuda no hubiera terminado la maestría.

Al Dr. Jiménez Montaño, Luis Nava, Rusalky y Antero, por las recomendaciones,

comentarios, correcciones, sugerencias y mejoras para el programa WinGramm 2.

A mis profesores de la Maestría en Inteligencia Artificial, que me hicieron

conocer y trabajar en la Ciencia de la Computación.

Julio César Sandria Reynoso. Aplicaciones de la Inteligencia Artificial al análisis de Biosecuencias

v

Contenido

Lista de Figuras.................................................................................................................... vii

Lista de Tablas .................................................................................................................... viii

1 Introducción......................................................................................................................1

1.1 Motivación...............................................................................................................1

1.2 Objetivo de este trabajo ...........................................................................................1

1.3 Contribuciones .........................................................................................................2

1.4 Estructura de la tesis ................................................................................................2

1.5 Versiones del software.............................................................................................2

2 Antecedentes.....................................................................................................................3

2.1 Lenguajes, autómatas y gramáticas .........................................................................3

2.1.1 Conceptos preliminares................................................................................3

2.1.2 Autómatas finitos.........................................................................................4

2.1.3 Clasificación de lenguajes ...........................................................................5

2.1.4 Gramáticas ...................................................................................................5

2.1.5 Gramáticas libres del contexto.....................................................................7

2.2 Inferencia Gramatical ..............................................................................................7

2.3 Medidas de información ..........................................................................................9

2.3.1 Entropía........................................................................................................9

2.3.2 Complejidad gramatical.............................................................................11

2.3.3 Redundancia algorítmica ...........................................................................13

2.3.4 Secuencias subrogadas...............................................................................13

2.3.5

...