aula7_ibm1029

Prévia do material em texto

1
IBM1029
Introdução à Bioinformática
Aula 7
Profª Drª Silvana Giuliatti
Departamento de Genética – Bloco G
Ramal: 4503
silvana@rge.fmrp.usp.br
Faculdade de Medicina
Departamento de Genética
Penalidades para Gaps
A maioria dos modelos de alinhamentos de 
sequências utiliza penalidade associadas a gaps nas 
quais o custo de incluir um gap em uma sequência é 
diferente do custo de aumentar um gap já existente.
Penalidades para Gaps
A maioria dos modelos de alinhamentos de 
sequências utiliza penalidade associadas a gaps nas 
quais o custo de incluir um gap em uma sequência é 
diferente do custo de aumentar um gap já existente.
• Penalidade de abertura de um gap (opening
penalty)
• Penalidade de extensão de um gap (extension
penalty)
Penalidades para Gaps
• Modelo Linear
w = g x d
g : comprimento do gap
d : penalidade por abertura do gap = -10
Exemplo: A A A T T T T T T A A A T T T T T T
A - A - A - T - T A A A - - - - T T
wtotal = - (1 x 10) x 4 = -40 wtotal = - (4 x 10) = -40
Penalidades para Gaps
• Modelo “Affine” – Gotoh (1982)
w = d + e (g - 1)
g : comprimento do gap
d : penalidade por abertura do gap = -10
e : penalidade por extensão = -2
Exemplo: A A A T T T T T T A A A T T T T T T
A - A - A - T - T A A A - - - - T T
wtotal = [- 10 -2 (1-1)] x 4 = -40 wtotal = -10 - 2(4 -1) = -16 Onde: M é o score para um alinhamento ótimo entre X e Y, onde o 
alinhamento finaliza com X alinhado com Y; Ix finaliza com X alinhado 
com gap e Iy finaliza com Y alinhado com gap (i =1, ..., m e j =1, ..., n).
M (i - 1, j -1) + s(xi , yj) 
Ix (i - 1, j-1) + s(xi , yj)
Iy (i-1, j - 1) + s(xi , yj)
M (i - 1, j ) + d 
Ix (i - 1, j) + e
M (i , j -1) + d 
Iy (i , j-1) + e
M (i, j) = max
Ix (i, j) = max
Iy (i, j) = max
2
Para M(i,0): score de alinhamento Xi com região de 
gap de comprimento i (i = 1, ..., m).
Para M(0,j): score de alinhamento Yi com região de 
gap de comprimento j (j = 1, ..., n).
M(0,0) = 0
Exemplo: Considere duas sequências:
X: A C G G T A C 
Y: G A G G T 
onde o modelo de pontuação é: s (a, a) = 1 (match)
s (a, b) = -1 (mismatch)
d = -3 (abertura) e = -2 (extensão)
Preenchendo para M(0,j) e M(i,0):
w = d + e (g - 1), sendo g = i ou g = j.
M(0,1) = -3 -2 (1-1) = -3 e assim sucessivamente.
-15C7
-13A6
-11T5
-9G4
-7G3
-5C2
-3A1
-11-9-7-5-30-0
TGGAG-M
543210
O score de um alinhamento ótimo será 
dado por:
Max { M(m, n), Ix(m,n), Iy (m, n)}
e o caminho de volta é traçado pa partir do 
elemento de valor máximo. 
Max {M(7,5), Ix(7,5), Iy(7,5)}
Max {-6, -4, -12}= -4
w = -3 -2 (2-1) = -5
X: A C G G T A C
Y: G A G G T - -
-1 -1 +1 +1 +1 -5 = -4
Penalidades para Gaps
• Não existe teoria que permita calcular a probabilidade 
de um gap, como, por exemplo, uma função da 
distância evolutiva ou de seu comprimento.
• Se a penalidade por gap for muito alta em comparação 
ao scores da matriz, gaps nunca irão aparecer no 
alinhamento.
• Se a penalidade por gap for muito baixa em 
comparação aos scores da matriz, gaps irão aparecer em 
todo lugar ao longo do alinhamento.
• A maioria dos programas sugerem seus valores 
apropriados. 
Programas para Alinhamentos de 
Pares de Sequências
• FASTA
• ALIGN: alinhamento global
algoritmo de Needleman-Wunsch
• LALIGN: alinhamento local
algoritmo de Smith-Waterman
http://fasta.bioch.virginia.edu/
http://veja.igh.cnrs.fr/
3
LALIGN
Matriz PAM250 
penalidade de abertura: -12 
penalidade de extensão: -2
: Pares idênticos
. Pares similares
Programas para Alinhamentos de 
Pares de Sequências
• EMBOSS 
• Needle: alinhamento global
algoritmo de Needleman-Wunsch
• Water: alinhamento local
algoritmo de Smith-Waterman
http://www.hgmp.mrc.ac.uk/Software/EMBOSS/
Alinhamento Global - Needle
Matriz BLOSUM62 | Pares idênticos
penalidade de abertura: -11 : Pares similares
penalidade de extensão: -1 . Pares com similaridade menor
“ “ (espaço) Pares sem relação
Alinhamento Local - Water
Matriz BLOSUM62 | Pares idênticos
penalidade de abertura: -11 : Pares similares
penalidade de extensão: -1 . Pares com similaridade menor
“ “ (espaço) Pares sem relação