aula5_ibm1029

Prévia do material em texto

1
IBM1029
Introdução à Bioinformática
Aula 5
Profª Drª Silvana Giuliatti
Departamento de Genética – Bloco G
Ramal: 4503
silvana@rge.fmrp.usp.br
Faculdade de Medicina
Departamento de Genética
Programação Dinâmica
ALINHAMENTO LOCAL
• Algoritmo de Smith-Waterman (Algoritmo 
Modificado de Needleman-Wunsch) (1981).
• Difere do alinhamento global:
• Inicia-se o alinhamento na célula F(i, j) de mais 
alto valor de score.
• O alinhamento finaliza quando um zero é 
encontrado.
• Uma possibilidade a mais em F (i, j). Valores 
negativos são convertidos a zero.
Programação Dinâmica
ALINHAMENTO LOCAL
Condições Iniciais:
F (i, 0) = 0 
F (0, j) = 0
Para cada posição, F (i, j) será determinado pelo score
máximo na posição (i, j), calculado como segue:
F (i-1, j-1) + s(xi, yj)
F (i-1, j) + w (x alinhado a gap)
F (i, j-1) + w (y alinhado a gap)
0
F (i, j) = max
Programação Dinâmica
ALINHAMENTO LOCAL
Considere as mesmas duas sequências:
X: C T T A G A 
Y: G T A A
onde o modelo de pontuação é:
s (a, a) = 1 (match)
s (a, b) = -1 (mismatch)
s (a, - ) = s (- , b) = -2 (gap)
F (i-1, j-1) + s(xi, yj) = F(0,0) -1= 0 -1 = -1 
F (i-1, j) + w = F(0,1) -2= 0 - 2= - 2
F (i, j-1) + w = F(1,0) -2 = 0 -2 = - 2
0
F (i, j) = max
0 1
- G
0 -
1 C
0 0
0 0
0 1 2 3 4 
- G T A A 
0 -
1 C
2 T
3 T
4 A
5 G
6 A
0 00
0
0 
0 
0
0
0
00
0
0
1
0
0
0 0 0 0
1 0 0
1 0 0
0 2 1
0 0 1
110
Único alinhamento: X: T A 
Y: T A 
+1 +1 = 2
2
Matrizes de Substituição
Um sistema de pontuação deve ser 
biologicamente relevante para produzir um 
alinhamento sensível. 
Matrizes de Substituição para:
• aminoácidos
• nucleotídeos
Matrizes de Substituição:
• PAM 
• BLOSUM
PAM
(Percent Accepted Mutation)
• Margaret Dayhoff (1978)
• substituições de aminoácidos foram 
estimados.
• 1572 mudanças em 71 grupos de 
sequências de proteínas.
• sequências com pelo menos 85% de 
similaridade.
PAM250
Log-odds scores PAM
• Um valor de zero indica que a frequência de 
substituição entre o par de aminoácidos é 
esperada ao acaso (probabilidades iguais).
• Um valor menor que zero indica que a frequência
é menor que o esperado (Ex. -4, significa que o 
alinhamento é mais um acaso do que uma relação 
com ancestral).
• Um valor maior que zero indica que a frequência é 
maior que o esperado (Ex. +10, significa que é 
maior a probabilidade de relação com ancestral).