Implementación Hardware de un algoritmo Needleman-Wunsch modificado para el alineamiento de secuencias de ADN

Abstract

El proceso de alineamiento está basado en algoritmos de programación dinámica o heurísticos cuyo objetivo es el de encontrar áreas iguales y diferentes a lo largo de cadenas de moléculas (ADN, ARN). Según el tipo de comparación, los algoritmos son clasificados en locales y globales. Cada tipo genera distintas variables de costo-beneficio sobre el tiempo de computación y memoria usada; sin embargo, las secuencias poseen una gran cantidad de bases o aminoácidos variables entre sectores, lo cual implica un mayor consumo de tiempo y recursos computacionales. Este trabajo presenta la implementación en hardware de un algoritmo de alineamiento basado en programación dinámica: el algoritmo K-band, el cual es una modificación del algoritmo de alineamiento global propuesto por primera vez en 1970 por Saul Needleman y Christian Wunsch. Dicho algoritmo permite el cálculo de la solución óptima para un proceso de alineamiento según una parametrización dada, reduciendo drásticamente a su vez la cantidad de información a procesar y el almacenamiento necesario. La arquitectura hardware del sistema es basada en un arreglo paralelo y es descrita por medio de lenguaje VHDL