Estrategias de Particionamiento Paralelo para el Problema del RNA

Estrategias de Particionamiento Paralelo para el Problema del RNA

Mireya Tovar Vidal
 

Texto completo de la Tesis     

 


Resumen

Las secuencias de RNA se utilizan entre otras cosas para caracterizar microorganismos en biomedicina molecular. Una secuencia de RNA consiste de una lista de bases nucleótidos, la cual se le conoce como la estructura primaria; cuando las bases se enlazan unas con otras se forma lo que se conoce como estructura secundaria. El problema de RNA consiste en encontrar, de todas las estructuras secundarias posibles, aquella que tiene una estructura secundaria estable. Esto conduce a un problema de optimización el cual en el caso general es considerado como un problema exponencial. Sin embargo, existen dos algoritmos debidos a Sankoff, con complejidades en tiempo O(n3 ) y O(n4 ), que resuelven casos especiales del problema general. Estos algoritmos se basan principalmente en el problema de múltiples ciclos y para su solución utilizan la estrategia de programación dinámica. A pesar de la complejidad polinomial de los algoritmos, el tiempo para encontrar estructuras secundarias es considerable para resolver secuencias largas. En este trabajo se realiza un análisis de dependencias de datos y se proponen estrategias de particionamiento paralelo para disminuir el tiempo computacional para secuencias de longitud considerable. Estos algoritmos paralelos se implementaron en dos tipos de arquitecturas paralelas: multiprocesadores (memoria compartida) y multicomputadoras (memoria distribuida). Se diseñaron dos esquemas diferentes de comunicación para memoria distribuida con la finalidad de obtener mejores resultados en tiempo de ejecución (comunicación maestro-esclavo y comunicación local). Se presentan los resultados experimentales obtenidos por estos algoritmos y se indican las ventajas y desventajas de cada arquitectura.