Este proyecto se centra en el desarrollo de un sistema de búsqueda de expresiones regulares con un enfoque específico en el contexto de la biología computacional. A través de este README, proporcionaré una visión general de los conceptos fundamentales detrás de la búsqueda de expresiones regulares.
En el ámbito de la biología computacional, las expresiones regulares son fundamentales para analizar secuencias de nucleótidos y proteínas. Aquí hay algunos conceptos clave relacionados con este contexto:
- Genoma: El conjunto completo de material genético de un organismo, que incluye tanto los genes codificantes como el ADN no codificante.
- Nucleótidos: Los bloques de construcción básicos del ADN, representados por las bases nitrogenadas Adenina (A), Timina (T), Guanina (G) y Citosina (C).
- Expansión de Codones: El proceso mediante el cual secuencias de codones específicas se expanden utilizando expresiones regulares para analizar variaciones y mutaciones.
Nótese (que no debería ser sorpresa para nadie) el genoma es inmenso, lo que dificulta esta tarea.
Las expresiones regulares son secuencias de caracteres que conforman un patrón de búsqueda. Permiten especificar patrones complejos y realizar búsquedas eficientes dentro de cadenas de texto.
Las expresiones regulares son patrones utilizados para encontrar una determinada combinación de caracteres dentro de una cadena de texto. Las expresiones regulares proporcionan una manera muy flexible de buscar o reconocer cadenas de texto. Por ejemplo, el grupo formado por las cadenas Handel, Händel y Haendel se describe con el patrón H(a|ä|ae)ndel.
- Wikipedia
- Texto: La cadena en la que se realiza la búsqueda.
- Patrón: El conjunto de caracteres que se está buscando.
- Ocurrencia: Cada vez que el patrón se encuentra en el texto.
Texto: "Pepe Pecas pica papas con un pico, con un pico pica papas Pepe Pecas."
Patrón: "pic"
Ocurrencias: 8
Las expresiones regulares pueden contener operadores que permiten definir patrones más complejos:
- Unión (
|): Representa la opción de uno u otro patrón. - Concatenación (
.): Une dos patrones para formar uno más grande. - Clausura de Kleene (
*): Indica que el patrón anterior puede repetirse cero o más veces.
Patrones:
("pic" o "pec") o ("pep" o "pap")
Expresión Regular:
p.(((i|e).c)|((e|a).p))
En este proyecto, se utiliza la teoría de autómatas para implementar la búsqueda de expresiones regulares. Se comienza con autómatas no deterministas (AFN) y los se les convierte en autómatas finitos deterministas (AFD) para optimizar el proceso de búsqueda. La conversión de un AFN a un AFD implica los siguientes pasos:
-
Construcción del Conjunto de Estados: Se genera un conjunto de estados que representan todas las posibles combinaciones de estados del AFN.
-
Cálculo de Transiciones: Se calculan las transiciones para cada estado del AFD basándose en las transiciones del AFN.
-
Minimización del AFD: Se minimiza el AFD resultante para reducir el número de estados y mejorar la eficiencia del algoritmo.
La conversión de autómatas es un proceso fundamental en la implementación de la búsqueda de expresiones regulares, ya que permite optimizar el rendimiento y la precisión del sistema.
El programa se ejecuta a través de una interfaz de línea de comandos (CLI), lo que permite una interacción sencilla con el usuario. Al ejecutar el programa, se solicitará al usuario que ingrese una expresión regular y una secuencia de texto sobre la cual realizar la búsqueda. El resultado de la búsqueda se mostrará en la consola.
El código proporcionado implementa un sistema de búsqueda de expresiones regulares utilizando la teoría de autómatas. Se ha diseñado para analizar secuencias de nucleótidos y encontrar ocurrencias de patrones específicos dentro de ellas. Para utilizar el código, sigue estos pasos:
- Ejecuta el Main.
- Proporciona una expresión regular como entrada. (los archivos in.txt incluyen ejemplos de entradas)
- Ingresa la secuencia de texto sobre la cual deseas realizar la búsqueda.
- El programa imprimirá las ocurrencias encontradas y resaltará los patrones coincidentes en la secuencia de texto.