Esta aula foi uma continuação da aula passada. Foi apresentado um novo problema de alinhamento, que pode ser solucionado através de pequenas modificações no algoritmo de programação dinâmica discutido na aula passada. O outro tópico da aula discutiu como melhorar o custo espacial do algoritmo.
A comparação semi-global procura a melhor forma de alinhar duas strings inteiras porém, contrariamente à comparação global, a inserção de espaços nas pontas (ou em uma delas, dependendo da instância do problema) da string não deve ser penalizada. Espaços iniciais (aqueles que ocorrem antes do primeiro caracter) e finais (aqueles que ocorrem após o último caracter) são considerados espaços nas pontas da string.
Dadas as seqüências CAGCACTTGGATTCTCGG e CAGCGTGG, um alinhamento global ótimo apresenta, pela esquema de pontuação (+1, -1, -2), uma similaridade de -12. Um desses alinhamentos seria:
CAGCACTTGGATTCTGG CAGC----G--T---GG
O índice de similaridade é ruim, e o alinhamento não diz muito sobre as strings. Utilizando-se a comparação semi-global, é possível chegar ao alinhamento (ótimo segundo a comparação semi-global):
CAGCA-CTTGGATTCTGG ---CAGCGTGG-------
Este alinhamento revela uma informação que os alinhamentos ótimos da comparação global não revelam: a alta similaridade entre a segunda seqüência e um trecho da primeira. Neste caso, o resultado insatisfatório da comparação global deve-se ao fato de que a segunda string é uma subseqüência da primeira, mas não uma substring. Nessa situação, a comparação global dá preferência aos alinhamentos que ressaltam a propriedade de subseqüência, mesmo que a string menor seja completamente retalhada por esses alinhamentos, como no exemplo acima.
A principal motivação para utilizar a comparação semi-global é a comparação envolvendo ao menos uma seqüência sabida incompleta, isto é, conhece-se um trecho da seqüência e sabe-se que ela é maior do que aquele trecho, mas não há informações sobre o resto da seqüência.
Dado que o problema principal (alinhamento de strings) é o mesmo, é de se esperar que o algoritmo que o solucione tenha muito do algoritmo básico. De fato, prova-se que com poucas modificações, é possível adaptar o algoritmo para não penalizar os espaços em cada uma das pontas de cada string. Essas modificações são independentes, possibilitando a implementação de qualquer combinação entre elas.
Para ignorar a influência dos espaços finais no alinhamento, devemos tentar alinhar uma das strings com um prefixo da outra. A matriz construída pelo algoritmo de comparação global é definida de tal forma que a célula (i, j) contém a pontuação do alinhamento das substrings s[1..i] e t[1..j]. Supondo-se que os espaços finais ocorrerão em t, basta procurar pela melhor pontuação na última coluna da matriz. O mesmo raciocínio pode ser aplicado para a situação em que os espaços finais ocorrem em s; neste caso procura-se pela melhor pontuação na última linha da matriz. Um algoritmo que procure a melhor pontuação nos valores da última linha e da última coluna da matriz é capaz de tratar corretamente ambos os casos, pois os espaços finais só podem ocorrer em uma das strings.
Para ignorar a influência dos espaços iniciais, basta inicializar com zeros a fila relevante da matriz (primeira linha para espaços iniciais em s, primeira coluna para espaços iniciais em t, ambas para tratar os dois casos). A justificativa para esta modificação é o próprio significado das pontuações nas células da primeira linha e da primeira coluna da matriz. No algoritmo de comparação global, essas células são inicializadas com g * (i + j)(*), onde g é a penalidade de espaço, pois elas significam o alinhamento de espaços com os i ou j primeiros caracteres da outra string. Este é exatamente o caso que se deseja ignorar.
| Onde ignorar os espaços | Modificação |
| Início da primeira string | Inicializar a primeira linha com zeros |
| Final da primeira string | Procurar a melhor pontuação na última linha |
| Início da segunda string | Inicializar a primeira coluna com zeros |
| Final da segunda string | Procurar a melhor pontuação na última coluna |
Na prática, as strings que são processadas por esse algoritmo são muito grandes. Um exemplo dado em aula citou um cromossomo de 180 MB. Há limites físicos rígidos de espaço, mas não de tempo. Além disso, neste caso tem-se uma redução de O(mn) para O(m + n) no espaço, enquanto o aumento de tempo é um fator multiplicativo constante. Em geral, essa barganha é considerada vantajosa.
Assumindo-se uma ordem row-major de computação, toda a informação necessária para calcular uma linha da matriz encontra-se na linha anterior, e a cada valor novo que é calculado, um outro valor não será mais necessário para cálculo nenhum. Na medida em que o algoritmo vai avançando na linha, as posições que contêm valores que não serão mais utilizados são sobrescritas com valores recém-calculados. Essa idéia simples leva à redução de complexidade espacial mencionada no tópico anterior. O problema é que até então, a matriz inteira era necessária para encontrar um alinhamento ótimo, e agora ela não existe mais.
É possível sim. Isso é feito utilizando a técnica de divisão e conquista da seguinte maneira (assumindo n o comprimento da string t):
A cada chamada recursiva, o algoritmo precisa calcular as similaridades do prefixo e sufixo da substring atual de s com prefixos e sufixos da substring atual de t. Sendo n o comprimento desta última, é necessário calcular 2n + 2 similaridades ao todo (t possui n + 1 prefixos e n + 1 sufixos).
Não existe um esquema de pontuação universal. Conforme visto no exercício 5 da aula passada, diferentes esquemas de pontuação podem levar a diferentes alinhamentos ótimos, mesmo quando é respeitada a relação match > mismatch > gap(*). Os resultados obtidos com um certo esquema de pontuação é que determinam se ele é bom ou ruim para aquele caso. Quanto à similaridade, são necessários outros parâmetros para julgá-la. Uma mesma pontuação pode ser ótima em um caso e péssima em outro, dependendo de outros fatores. De onde vêm as seqüências comparadas? O que é esperado da comparação? Perguntas como estas devem ser respondidas antes que se julgue a similaridade.
As células apenas representam a similaridade entre os prefixos considerados. Elas não dão o alinhamento por si só. O alinhamento é dado por um caminho ao longo das setas, não pelas células.