Departamento de Computación

Una molécula de ácido ribonucleico (RNA) consiste en una larga secuencia de subunidades -ribonucleótidos- enlazadas entre ellas. La cadena de subunidades, llamadas bases, es conocida como estructura primaria, pero cuando las bases se enlazan entre sí forman lo que se conoce como estructura secundaria. Se puede obtener una gran cantidad de estructuras secundarias a partir de una sola estructura primaria. El problema del RNA consiste en obtener, de entre todas las combinaciones posibles, aquella estructura secundaria que sea estable, es decir, la que optimiza la liberación de energía. El espacio de búsqueda de este problema crece de manera exponencial, por lo que utilizar un algoritmo de fuerza bruta es infactible. Se tienen dos algoritmos, propuestos por Kruskal y Sankoff, los cuales resuelven este problema en un tiempo computacional razonable, estos algoritmos son identificados por su complejidad computacional, O(n3) y O(n4 ). La diferencia entre estos dos algoritmos radica en el conjunto de soluciones que pueden explorar. A pesar de su complejidad polinomial, ambos algoritmos requieren tiempos de ejecución grandes cuando resuelven el problema del RNA para estructuras primarias largas. Por lo tanto, en esta tesis presentamos un algoritmo paralelo para el algoritmo O(n4), el cual reduce su tiempo de ejecución. Se analizaron las dependencias entre los datos a utilizar por el algoritmo O(n4) para dividir, de manera equitativa, el trabajo computacional en varios procesadores. El buen desempeño de un algoritmo paralelo se logra al reducir los tiempos de comunicación y sincronización.
Puede existir más de una estructura secundaria con la mínima liberación de energía y en biología puede ser importante comparar éstas soluciones. Por lo tanto, un segundo aspecto considerado en esta tesis es, obtener todas las posibles soluciones a partir de una estructura primaria dada. Basados en las tablas de programación dinámica utilizadas en los algoritmos O(n3) y O(n4), se propusieron modificaciones en el proceso de llenado, de tal manera que se almacenara la información requerida para rastrear todas las posibles soluciones.
Se presentan resultados experimentales, los cuales demuestran que los dos aspectos considerados en esta tesis fueron resueltos de manera adecuada. Para el algoritmo paralelo se presentan resultados que muestran un mejor desempeño comparado contra otras estrategias implementadas.