As sobreposições podem ser avaliadas com o uso de um algoritmo por nós tratado em [SF 98]. Trata-se de uma adaptação do:
Um algoritmo de programação dinâmica para a resolução do problema encontra-se na Figura 4. Ele devolve dois vetores b e c. O vetor b atua como um log das operações, permitindo reconstruir a máxima subseqüência comum. Já c[i, j] nos dá o comprimento da maior subseqüência entre
e
.
Uma modificação de MaxSC(X, Y) nos dá o algoritmo para a função Sim(X, Y) (vista anteriormente na definição do Problema 2). Tal algoritmo (Figura 5) leva em consideração pequenos erros nas strings de entrada. A função p(xi, yj) compara os dois caracteres xi e yj, retornando 1 caso sejam iguais ou -1 caso contrário. Assim, torna-se possível alinhar nucleotídeos diferentes, penalizando a similaridade entre os fragmentos de DNA toda vez que isso ocorre. Além disso, é possível inserir ``buracos'' nos fragmentos, de modo a maximizar a similaridade. Porém, quando um buraco é inserido, uma penalização g é removida da similaridade.
Este algoritmo, bem como o problema a ele associado, possui várias variantes. Maiores detalhes podem ser encontrados em [MS 94] e [SF 98].