ALINHAMENTOS LOCAIS E SEMI-GLOBAIS Katia Guimarães

ALINHAMENTOS LOCAIS E SEMI-GLOBAIS

Katia Guimarães

katia@cin.ufpe.br 2

Montagem de Fragmentos

Dadas duas cadeias de comprimentos similares, identificar “boas similaridades” entre o início de uma e o final da outra, ou vice-versa. Ex: - - - - - - - - CAGCACTTGGATTAGAC TACCTGCGCAGCG - TTG - - - - - - - - -

Teremos 7 matches, 1 mismatch e 17 spaces.

katia@cin.ufpe.br 3

Tentando Alinhamento Global

Considerando toda a cadeia (ALINH. GLOBAL): TA - C - CTGCGCAGCGTGG - CAGCACT - TGGA – TTAGAC

Teremos 7 matches, 7 mismatches e 5 spacesLevando a um score global de –3.

katia@cin.ufpe.br 4

Alinhamento Semi-global

- - - - - - - - CAGCACTTGGATTAGAC TACCTGCGCAGCG - TTG - - - - - - - - -

Se não considerarmos os custos dos gaps iniciais e finais, este alinhamento teria apenas: 7 matches, 1 mismatch e 1 space,dando um score de 11.

katia@cin.ufpe.br 5

Achando o alinhamento semi-global

Para não computar o custo dos espaços iniciais em s, o que precisamos fazer?

Ex: s = - - - - - - - - CAGCA t = TACCTGCGCAGCG

katia@cin.ufpe.br 6

Achando o alinhamento semi-global

Para não computar os espaços iniciais em s,precisamos não computar o custo dos gaps iniciais.Ex: s = - - - - - - - - CAGCA t = TACCTGCGCAGCG

Como obter este efeito na tabela?

katia@cin.ufpe.br 7

Achando o alinhamento semi-global

Ex: s = - - - - - - - - CAGCA t = TACCTGCGCAGCG

Para não computar as inserções no início do alinhamento, incializaremos a primeiralinha com zeros.

katia@cin.ufpe.br 8

Achando o alinhamento semi-global

Para não computar os espaços após o último caracter de t, ignoramos o sufixo de s que casa com aqueles espaços.

Ex: s = CAGCACTTGGATTAGAC t = CAGCG - TTG - - - - - - - - -

Como obter este efeito na tabela?

katia@cin.ufpe.br 9

Achando o alinhamento semi-global

Ex: s = CAGCACTTGGATTAGAC t = CAGCG - TTG - - - - - - - - -

Note que depois que t termina, o score vai apenas diminuindo.

katia@cin.ufpe.br 10

Achando o alinhamento semi-global

Ou seja, não devemos nos preocupar com a continuação do alinhamento depois que a cadeia t termina (última coluna).

Logo, devemos tomar o maior valor na última coluna de M, isto é: sim(s, t) = máx i =1..m M[i, n]

katia@cin.ufpe.br 11

Achando o alinhamento semi-global

De maneira similar, poderíamos ter o alinhamento semi-global começando com remoções. Ex: s = TACCTGCGCAGCG t = - - - - - - - - CAGCA

Para não computar as remoções no início do alinhamento, incializaremos a primeiracoluna com zeros.

katia@cin.ufpe.br 12

Achando o alinhamento semi-global

E ao final não podemos nos preocupar

com as inserções no final. Ex:

Ex: s = CAGCACTTG - - - - - - - - -

t = CAGCG - TTGTACCTGCG

Para focar no final de s olhamos o maior valor da última linha.

katia@cin.ufpe.br 13

Achando o alinhamento semi-global

Ou seja, não devemos nos preocupar com a continuação do alinhamento depois que a cadeia s termina (última linha).

Logo, devemos tomar o maior valor na última linha de M, isto é: sim(s, t) = máxj=1..n M[m, j]

katia@cin.ufpe.br 14

Achando o alinhamento semi-global

Considerando este maior valor na última linha de M: sim(s, t) = máxj=1..n M[m, j]

Para conseguir o alinhamento é só começar a busca numa célula (m, k) da matriz, onde k é tal que sim(s, t) = M[m, k].

katia@cin.ufpe.br 15

Alinhamento Local

Dadas duas seqüências s e t, identificaro alinhamento de melhor score entre umsubstring de s e um substring de t.

O algoritmo será o mesmo que usamos para alinhamento global, com algumas alterações.

katia@cin.ufpe.br 16

Alinhamentos Locais

Ainda teremos uma matriz (m+1) (n+1)mas cada entrada (i, j) vai conter o maior score de um alinhamento entre um sufixo de s[1..i] e um sufixo de t[1..j].

Para isso, a primeira linha e a primeira coluna vão ser inicializadas com zeros.

katia@cin.ufpe.br 17

Observação

Para qualquer entrada (i, j) há sempre o alinhamento entre os sufixos vazios de s[1..i] e de t[1..j], que tem score zero.

Portanto, este array terá todas as entradas maiores ou iguais a zero.

katia@cin.ufpe.br 18

Usaremos ainda Programação Dinâmica

M (i, j) = max M (i, j-1) - 2 (último passo = I) M (i-1, j-1) + p(i,j) (último passo = S/M) M (i-1, j) - 2 (último passo =R) 0 (alinhamento vazio)

katia@cin.ufpe.br 19

No final ...

Encontrar a maior entrada em todo o array. Este será o score de um alinhamento local ótimo.

O alinhamento é obtido a partir dali, seguindo de volta, e parando quando não houver aresta saindo (ou seja, onde o score for zero).

katia@cin.ufpe.br 20

Alinhamento Local - Exemplo

C A G C A C T C A T 0 0 0 0 0 0 0 0 0 0 0 T 0 0 0 0 0 0 0 1 0 0 1 C 0 1 0 0 1 0 1 0 2 0 0 C 0 1 0 0 1 0 1 0 1 1 0 A 0 0 2 0 0 2 0 0 0 2 0 G 0 0 0 3 1 0 1 0 0 0 1 C 0 1 0 1 4 2 1 0 1 0 0 T 0 0 0 0 2 3 1 2 0 0 1 C 0 1 0 0 1 1 4 2 3 1 0 G 0 0 0 1 0 0 2 3 1 2 0

katia@cin.ufpe.br 21

Alinhamento Local - Exemplo C A G C A C T C A T . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . : G 0 0 0 3 1 0 1 0 0 0 1 C 0 1 0 1 4 2 1 0 1 0 0 T 0 0 0 0 2 3 1 2 0 0 1 C 0 1 0 0 1 1 4 2 3 1 0 G 0 0 0 1 0 0 2 3 1 2 0

CAGCACTCAT TCCAGCTCG -

katia@cin.ufpe.br 22

Alinhamento Local - Exemplo

C A G C A C T C A T . . .

T 0 0 . . . CAGCACTCAT C 0 1 0 . . . TCCAGCTCG C 0 1 0 0 . . . A 0 0 2 0 0 2 0 0 0 2 0 G 0 0 0 3 1 0 1 0 0 0 1 C 0 1 0 1 4 2 1 0 1 0 0 T 0 0 0 0 2 3 1 2 0 0 1 C 0 1 0 0 1 1 4 2 3 1 0 G 0 0 0 1 0 0 2 3 1 2 0

katia@cin.ufpe.br 23

Achando o alinhamento semi-global

INICIALIZAÇÃO.

Para não penalizar por gaps no início das cadeias, ao invés de penalizar com (i . g) ou (j . g), inicializamos a primeira linha e a primeira coluna com zeros.