Los algoritmos de alineamiento podrían ubicarse dentro de la familia de algoritmos útiles para la manipulación de cadenas de caracteres (Gusfield, 1997), pero aquí vamos a verlos siempre dentro del contexto biológico.
Los algoritmos de alineamiento en nuestro contexto normalmente usan matrices de pesos o sustitución para evaluar el emparejamiento de letras o monómeros de las secuencias. Para alineamientos de ADN, como hay sólo 4 nucleótidos, se usa una matriz 4x4, que contiene un valor para cada posible emparejamiento de nucleótidos.
|
Además de estas matrices necesitamos un convenio para evaluar de manera adecuada la apertura de gaps en las secuencias que estamos alineando.
Los algoritmos de alineamiento pueden verse como algoritmos de búsqueda, que tratan de encontrar valores óptimos de funciones objetivo que combinan las puntuaciones de las parejas de letras alineadas y el coste de abrir gaps dentro de las secuencias.