Buscar

aula4_ibm1029

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 5 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

1
IBM1029
Introdução à Bioinformática
Aula 4
Profª Drª Silvana Giuliatti
Departamento de Genética – Bloco G
Ramal: 4503
silvana@rge.fmrp.usp.br
Faculdade de Medicina
Departamento de Genética
Alinhamentos de Sequências
Alinhamentos de Sequências
• Objetivo: 
Descobrir informações evolucionárias, 
estruturais e funcionais em sequências de 
proteínas ou DNA.
Alinhamentos:
• pares de sequências
• múltiplas sequências
Similaridade: possuem regiões similares
Homologia: possuem mesmo ancestral
Alinhamentos de Sequências
Gene
(duplicação do gene)
gene cadeia - α gene cadeia - β
sapo α galinha α camundongo α camundongo β galinha β sapo β
ortólogos parálogos ortólogos
homólogos
Alinhamento de Pares de 
Sequências
Compara duas sequências e procura por 
similaridades
Alinhamentos:
• Local: regiões similares constituem uma parte das 
sequências
• Global: similaridade é considerada ao longo de toda 
extensão das sequências.
Alinhamentos de Pares 
de Sequências
LGPSSKQTGKGS-SRIWDN
| | ||| | |
LN-ITKSAGKGAIMRLGDA
----TGKG------
||| 
----AGKG------
Global Local
2
Pode haver mais de um alinhamento possível.
Considere: ACGGACT e ATCGGATCT
Dois possíveis alinhamentosDois possíveis alinhamentos
Alinhamentos de Pares 
de Sequências
A - C - G G - A C T
| | | | |
A T C G G A T - C T
A - C G G - A C T
| | | | | |
A T C G G A T C T
Métodos de Alinhamentos: 
9Matrizes de Pontos: todas as possíveis combinações 
entre as sequencias são encontradas.
9Programação Dinâmica: matematicamente garantida 
para encontrar um alinhamento ótimo (global ou local) entre 
pares de sequênciais.
• Matrizes de Substituição
9Método de palavras ou k- tuplas:
• Alinhamento heurístico: mais rápido que a 
programação dinâmica, mas não garante o alinhamento 
ótimo. É ideal para pesquisa em banco de dados.
Alinhamentos de Pares de
Sequências
Matrizes de Pontos
Matrizes de Pontos
• Descrito pela primeira vez por Gibbs e McIntyre (1970).
• Usado para comparar duas sequências através de um 
possível alinhamento de caracteres entre elas.
• Todos os possíveis alinhamentos são encontrados.
• A detecção de regiões pode ser melhorada através de filtros.
Matrizes de Pontos
1 - Uma sequência é disposta em uma linha e a outra listada em uma 
coluna, uma ao lado da outra.
2 - Um ponto deve ser colocado em cada local onde os caracteres são
iguais.
3 - A diagonal principal revela a similaridade entra as sequências. 
H C G E T F G R W F T P E W
H •
C •
G •
E •
T •
F •
G •
R •
W •
F •
T •
P •
E •
W • 
Matrizes de Pontos
4 - Pode também apresentar regiões de repeats e repeats invertidos fora da 
diagonal principal. Qualquer região similar entre as sequências é revelada 
por uma diagonal.
5 - Pontos isolados representam similaridades aleatórias não relacionadas 
ao alinhamento.
3
Matrizes de Pontos
Programas para Matrizes de Pontos
Dotlet (www.isrec.isb-sib.ch/java/dotlet/Dotlet.html)
• Disponível pela Internet
• Sequências curtas: até 10.000 caracteres
• Todas as plataformas
Dotter (www.cgr.ki.se/cgr/groups/sonnhammer/Dotter.html)
• Sequências até 100.000 caracteres
• Linux, Windows, Unix
EMBOSS (Dottup, Dotmatcher) (www.emboss.org)
• Sequências maiores de 100.000 caracteres
• Unix, Linux
Matrizes de Pontos
Dotlet
Matrizes de Pontos
Dotlet
Matrizes de Pontos
Dotter
Matrizes de Pontos
Dotmatcher
Programação Dinâmica
4
Qual o melhor caminho de Ribeirão Preto a São Paulo?
Os algoritmos de programação dinâmica solucionam os 
problemas de otimização: há várias soluções possíveis, mas 
encontra-se uma solução ótima dividindo o problema original 
em subproblemas e solucionando-os (“problema do caixeiro 
viajante”).
Programação Dinâmica
• É um método de alinhamento de pares de seqüências 
(proteínas ou DNA) que pode levar em conta lacunas (gaps), 
mas com um número de comparação aceitável.
•Proporciona um ótimo alinhamento (mais alta pontuação 
(score) ).
• Limitação: pode ser lento. O número de etapas necessárias 
depende do comprimento das sequências. 
Programação Dinâmica
• Conceito de Score (escore, pontuação): medida 
pela qual os alinhamentos são quantificados.
Considere: ACGGACT e ATCGGATCT
Dois possíveis alinhamentos. Qual é o melhor?
A - C - G G - A C T
| | | | |
A T C G G A T - C T
A - C G G - A C T
| | | | | |
A T C G G A T C T
Alinhamento 1 Alinhamento 2
Programação Dinâmica
Considere o seguinte esquema simples de score:
+ 2 para igualdade (match)
- 1 para desigualdade (mismatch)
- 2 para penalidade (gaps)
Programação Dinâmica
Para o alinhamento 1:
Para o alinhamento 2:
A - C - G G - A C T
| | | | |
A T C G G A T - C T
+2-2+2-2+2-1-2-2+2+2 = 1
A - C G G - A C T
| | | | | |
A T C G G A T C T
+2-2+2+2+2-2-1+2+2 = 7
Programação Dinâmica
As etapas da Programação Dinâmica
a) Escolher um modelo de pontuação
b) Gerar a matriz (determinar os scores)
c) Determinar o alinhamento ótimo (traçar o 
alinhamento a partir do melhor score).
5
Programação Dinâmica
ALINHAMENTO GLOBAL
Algoritmo de Needleman-Wunsch (1970).
Alinhamento permite gaps e ocorre em toda a 
extensão das sequências.
•
Programação Dinâmica
ALINHAMENTO GLOBAL
A matriz de pontuação F(i,j) é construída 
recursivamente.
¾ Inicia com F(0,0) = 0 ( gaps)
¾ Constrói um alinhamento ótimo usando 
soluções prévias de subsequências menores.
¾ Preenche a matriz do canto esquerdo superior 
até o canto direito inferior.
Programação Dinâmica
ALINHAMENTO GLOBAL
a) Considere 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)
Programação Dinâmica
ALINHAMENTO GLOBAL
Condições Iniciais:
F (i, 0) = w x i 
F (0, j) = w x j
b) 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)
F (i, j) = max
Onde w = -2 (gap)
Programação Dinâmica
F(i, j)
F(i-1, j-1)
F(i, j-1)
F(i-1, j)
-2±1
-2
0 1 2 3 4 
- G T A A
0 -
1 C
2 T
3 T
4 A
5 G
6 A
0 - 4-2
- 2
-4
-6
- 8
- 10
- 12
- 8- 6
- 5
- 7
-7
- 9
- 3
- 1 - 3 - 5 - 7
0 - 2 - 4
- 2 - 1 - 3
- 4 - 1 0
- 6 - 3 - 2
- 2- 5- 8

Outros materiais