Algoritmos de emparejamiento de secuencias de ADN
Resumen
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.