Algoritmos de emparejamiento de secuencias de ADN

Abstract

Las máquinas de secuenciación de ADN (ácido desoxirribonucleico) combinan algoritmos de emparejamiento de búsqueda exacta y aproximada para formar algoritmos de ensamblado de secuencias alineando fragmentos pequeños por etapas, hasta conseguir secuencias completas. En los antecedentes de algoritmos de búsqueda sobre textos existen varios algoritmos, de los cuáles en esta investigación se eligió de búsqueda exacta sin indexación: Knuth-Morris- Pratt, Rabin-Karp, Boyre-Moore y Skip-Search. El desarrollo del tema permitió analizar, describir, experimentar con los algoritmos de emparejamiento sobre secuencias de ADN. El algoritmo Knuth-Morris-Pratt es comparable con un autómata finito, de este modo es análogo a realizar búsquedas utilizando expresiones regulares en cualquier lenguaje de programación. En implementaciones para secuenciadores se utiliza el algoritmo Rabin-Karp con una estrategia de búsqueda off-line (con indexación). Experimentalmente el algoritmo Boyre-Moore es de mejor rendimiento y el algoritmo Rabin-Karp muestra una menor desviación estándar. El algoritmo Skip-Search alcanza un buen rendimiento haciendo uso de una estructura de datos lista-contenedor. Los algoritmos de alineamiento son una generalización de los algoritmos aproximados (permitiendo inexactitud) de emparejamiento de secuencias, se introdujo en el tópico eligiendo el algoritmo Needleman-Wunsch que permite alinear dos secuencias con la estrategia de alineamiento global hallando la puntuación óptima de similitud.