Secuencias de coincidencia bajo restricciones de eliminación/inserción

Dados dos secuencias finitas, deseamos encontrar las subsecuencias comunes más largas que satisfacen ciertas restricciones de eliminación/inserción. Consideremos dos términos sucesivos en la subsecuencia deseada. La distancia entre sus posiciones debe ser la misma en las dos secuencias originales, excepto por un número limitado de tales pares de términos sucesivos. Needleman y Wunsch propusieron un algoritmo para encontrar las subsecuencias comunes más largas sin restricciones. Esto se mejora desde el punto de vista de la economía computacional. Luego se elabora un algoritmo económico para encontrar subsecuencias que satisfacen las restricciones de eliminación/inserción. Este resultado es útil en el estudio de la homología genética basada en secuencias de nucleótidos o aminoácidos.