Descripción:
El comportamiento de una molécula de ARN depende directamente de sus estructuras secundarias y terciarias. Sin embargo, se ha demostrado que la predicción de estructuras secundarias con pseudonudos arbitrarios es un problema NP-completo. En esta tesis se presenta el problema de la predicción de estructuras secundarias de ARN a través del estudio de tres algoritmos basados en la técnica de programación dinámica. Los algoritmos de Nussinov y Zuker predicen estructuras secundarias sin pseudonudos, mientras que el algoritmo de Akutsu lo hace con pseudonudos simples. También presentamos una metaheurística que utiliza un algoritmo genético para producir subestructuras cuasi-óptimas que a su vez permiten la predicción de estructuras secundarias con pseudonudos simples. También presentamos un análisis experimental de los cuatro algoritmos implementados utilizando instancias públicas de estructuras de ARN provistas por las bases de datos RNA STRAND y PseudoBase ++. Finalmente, se presenta un prototipo de sistema con el cual se puede obtener la estructura secundaria para una secuencia de ARN provista por el usuario. El prototipo cuanta con la implementación de los cuatro algoritmos estudiados en la presente tesis.