O Problema

Considere as seguintes seqüências de DNA: GACGGAATAG e GATCGGAATAG. Não se pode deixar de notar a extrema semelhança entre elas, que fica mais evidente se as colocamos alinhadas como se segue:

CA_CGGATTAG GATCGGAATAG

As únicas diferenças são um ``T'' a mais na segunda seqüência e uma troca de ``A'' por ``T'' na quarta posição da direita para a esquerda. Note que foi necessário um buraco na primeira cadeia para que as bases iguais antes e depois do buraco se alinhassem nas duas seqüências. Logo, as cadeias a serem alinhadas não precisam ser necessariamente do mesmo tamanho pois podemos incluir buracos em qualquer das seqüências no alinhamento. A cada coluna do alinhamento entre duas seqüências, podemos atribuir uma pontuação como segue. Cada coluna do alinhamento receberá um certo número de pontos e a pontuação total do alinhamento será a soma dos pontos atribuídos às colunas. Se a coluna tiver duas bases iguais receberá 1 ponto. Se a coluna tiver duas bases diferentes recebera -1 ponto. Por fim, se a coluna possuir uma base e um buraco receberá -2 pontos. O problema será então encontrar o alinhamento que tiver pontuaçãoo máxima. Esta pontuação será chamada de similaridade entre as duas seqüências. Em geral, pode haver mais de um alinhamento com pontuação máxima. O alinhamento do exemplo acima ficaria:

9*1+1*(-1)+1*(-2)=6