31
Alinhamento Global de Seqüências Katia Guimarães

Alinhamento Global de Seqüências Katia Guimarães

Embed Size (px)

Citation preview

Page 1: Alinhamento Global de Seqüências Katia Guimarães

Alinhamento Global de Seqüências

Katia Guimarães

Page 2: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 2

Alinhamento de Seqüências

Problema: Dadas duas seqüências sobre o mesmo alfabeto, com aproximadamente o mesmo tamanho, encontrar o melhor alinhamento entre estas duas seqüências.

Page 3: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 3

Alinhamento de Seqüências

O melhor alinhamento entre duas seqüências: G A - C G G A T T A G G A T C G G A AT A G é dado por um score que é a soma dos valores associados a cada posição, de acordo com o critério pré-definido.

Page 4: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 4

Alinhamento de Seqüências

O score que é a soma dos valores associados a cada posição, de acordo com o grau de similaridade entre os elementos correspondentes.

Ex: match +1 mismatch -1 space -2

Page 5: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 5

Score de um Alinhamento

Ex: match +1 (good) mismatch -1 (bad) space -2 (worse)

G A - C G G A T T A G G A T C G G A AT A G

score = 9 ·1+ 1·(-1) + 1·(-2) = 6

Page 6: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 6

Programação Dinâmica

O número de possíveis alinhamentos éexponencial no tamanho das seqüências. (Logo, não podemos experimentar todos.)

Abordagem alternativa: Sejam s e t duas seqüências, com |s|=m e |t|=n, construir uma matriz (m+1) x (n+1), onde M(i, j) contém a similaridade entre s[1..i] e t[1..j].

Page 7: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 7

Programação Dinâmica

Esta é uma abordagem indutiva, onde são definidos os scores para as seqüências menores, e a partir dessas, novos scores são computados os scores de cadeias maiores.Ex: G A - C A T T G G A T C A AT G G custa -2; GA custa -4; G G custa +1; G GA custa -1;

Page 8: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 8

Programação Dinâmica

1a. linha e1a. coluna fáceis de computar: G A C A T T G 0 -2 -4 -6 -8 -10 -12 -14 G -2 A -4 T -6 C -8 A -10 A -12 T -14 G -16

Page 9: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 9

Programação Dinâmica

Dado que eu sei computar os scores dos melhores alinhamentos entre prefixos de s e t com tamanhos menores que i e j, respectivamente, como eu posso calcular omelhor alinhamento de s[1..i] com t[1..j]?

Page 10: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 10

Programação Dinâmica

O score do melhor alinhamento será calculado em função do último passo deuma transformação de s[1..i] em t[1..j].

Um passo pode ser I (inserção), R (remoção), S (substituição) ou M (match)

Page 11: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 11

Programação Dinâmica

1. Se do último passo for I (inserção): Ex: G A G C A T T C G A - C A A T C G Solução: Alinhe s[1..i] com t[1..j-1] e case um espaço com t[j]. 1 .................................. i s: G A G C A T T C t: G A - C A A T C G 1 ................................ j-1 j

Page 12: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 12

Programação Dinâmica

2. Se do último passo for M (match) ou S (substituição):

Solução: Alinhe s[1..i-1] com t[1..j-1] e case s[i] com t[j].

1 ........................... i-1 i s: G A G C A T T C t: G A - C A A T C 1 ........................... j-1 j

Page 13: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 13

Programação Dinâmica

3. Se do último passo for R (remoção):

Solução: Alinhe s[1..i-1] com t[1..j] e case s[i] com um espaço.

1 ................................. i-1 i s: G A G C A T T C G t: G A - C A A T C 1 ........................... j-1 j

Page 14: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 14

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)

onde p(i,j) = +1 se s[i] = t[j] (M) -1 se s[i] t[j] (S)

Page 15: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 15

Computando a Matriz M

I-2

-2-1 +1S M R

i-1, j-1

i, j-1

i-1, j

i, j

Page 16: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 16

Computando a Matriz M

0

-2

-4

-6

1

-3

-8

-1

-2

-1

0

-4

-4 -6

-3

-2

-1

-1

A

A

A

A

C

CG

-2

-5

Page 17: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 17

Algoritmo M m |s|; n |t|; for i 0 to m do M[i, 0] i · g custo rem. for j 0 to n do M[0, j] j · g custo ins. for i 1 to m do for j 1 to n do M[i, j] max M [i, j-1] + g; M [i-1, j-1] + p(i,j); M [i-1, j] + g return (M[m, n] )

Page 18: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 18

Construindo um Alinhamento Global

Começamos na entrada [m, n] da matriz M e seguimos as setas no sentido reverso, até atingir [0, 0].

Neste processo vamos construindo dois arrays align-s e align-t, que conterão as seqüências s e t com os gaps necessários. (Depois reverteremos estes arrays.)

Page 19: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 19

Construindo o Alinhamento

+10

+13+14

i-1, j-1

i, j-1

i-1, j

i, j

Seguindo uma seta escolhida no sentido reverso:

+14

Page 20: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 20

Construindo Alinhamentos1. Se a seta saindo de [i, j] é horizontal (I), teremos uma coluna com um espaço em s alinhado com o símbolo t[j]. Ex: M[1, 2]: align-s : A - align-t : A G

0

-2 1 -1

-4

A

-2

A G

Page 21: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 21

Construindo Alinhamentos2. Se a seta saindo de [i, j] é vertical (R), então teremos uma coluna com s[i] alinhado com um espaço em t.

Ex: M[2, 1]: align-s : A G align-t : A -

-1-4

0

-2 1A

-2

A

G

Page 22: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 22

Construindo Alinhamentos3. Se a seta saindo de [i, j] é diagonal (M ou S), então teremos uma coluna com s[i] alinhado com t[j] (quer sejam idênticos ou não).

Ex: M[2, 2]: align-s: A G align-t: A A

-1-4

0

-2 1A

-2

A

G 0

-1

-4

A

Page 23: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 23

Algoritmo Align (m, n, len, M)

Entrada: m = |s|, n = |t|, matriz M

Saída: len, align-s e align-t, onde len é o comprimento da seqüência de alinhamento, dada pelos vetores align-s e align-t, que contêm símbolos e espaços. Note que max(m, n) len m + n.

Page 24: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 24

Algoritmo Align (m, n, len, M)

i m; and j n; len 0; while i 0 and j 0 do if M[i, j] = M[i-1, j] + g /* (R) */ then /* símbolo de s com ´-` */ len len + 1; align-s[len] s[i] align-t[len] ´-`; i i-1 else

Page 25: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 25

Algoritmo Align (m, n, len, M)

if M[i, j] = M[i-1, j-1] + p(i, j) (M ou S) then /* alinha s[i] com t[j] */ len len + 1; align-s[len] s[i] align-t[len] t[j]; i i-1; j j-1 else

Page 26: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 26

Algoritmo Align (m, n, len, M)

/* caso: (I), ou seja, M[i, j] = M[i, j-1] + g */ /* alinha t[j] com espaço*/ len len + 1; align-s[len] ´-` align-t[len] t[j] j j-1

Page 27: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 27

Algoritmo Align (m, n, len, M)

/* Após o laço while temos i = 0 ou j = 0. */

/* Alinhar o prefixo restante com ´-` */

/* Inverter os arrays align_s e align_t */

Page 28: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 28

Diversidade de Alinhamentos

Observe que há em geral diversas escolhas para um alinhamento ótimo.

O algoritmo dado dá preferência aos passos na ordem: 1. Vertical (R) 2. Diagonal (S/M) 3. Horizontal (I)

Page 29: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 29

Alinhamento com o Algoritmo Align

Se s = ATAT e t = TATA, obtemos: Align-s = - A T A T Align-t = T A T A -

Mas se a ordem dos IF´s fosse outra, poderíamos obter: Align-s = T A T A - Align-t = - A T A T

Page 30: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 30

Alinhamento com o Algoritmo Align

Se s = AA e t = AAAA, obtemos: Align-s = - - A A Align-t = A A A A

(Há outros 5 alinhamentos ótimos)

Page 31: Alinhamento Global de Seqüências Katia Guimarães

[email protected] 31

Complexidade dos Algoritmos

Algoritmo M: O(m . n )

Algoritmo Align: O(m + n )