Compar Seqs

Prévia do material em texto

*
*
*
COMPARAÇÃO
 DE SEQÜÊNCIAS
Katia Guimarães
katia@cin.ufep.br
*
*
*
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.
 
katia@cin.ufep.br
*
*
*
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. 
katia@cin.ufep.br
*
*
*
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 
katia@cin.ufep.br
*
*
*
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 
katia@cin.ufep.br
*
*
*
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]. 
katia@cin.ufep.br
*
*
*
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; 
katia@cin.ufep.br
*
*
*
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
katia@cin.ufep.br
*
*
*
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 o
melhor alinhamento de s[1..i] com t[1..j]?
katia@cin.ufep.br
*
*
*
Programação Dinâmica
O score do melhor alinhamento será 
calculado em função do último passo de
uma 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)
katia@cin.ufep.br
*
*
*
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
katia@cin.ufep.br
*
*
*
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
katia@cin.ufep.br
*
*
*
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
katia@cin.ufep.br
*
*
*
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)
katia@cin.ufep.br