A 4 Alinhamento de sequências

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
Bioinformática
ALINHAMENTO DE SEQUÊNCIAS 	PARTE I
*
*
A Vida na Terra
*
*
DNA, RNA, Proteínas
Alinhamento de sequências: Alinhamento de proteínas fornece mais informações do que o alinhamento de DNA.
 - Código genético degenerado (muitas mudanças na 3ª. Posição do 
 codon não muda o AA)
- Muitos aminoácidos compartilham propriedades biofísicas comuns 
 (Ex; Lys e Arg = AA básicos)
- O relacionamento entre aminoácidos (com propriedades biofísicas comuns) pode ser computado num sistema de Escores no alinhamento ;
- A comparação de sequências protéicas pode identificar sequências homólogas a partir de organismos que compartilharam o último ancestral comum a 1 bilhão de anos atrás (1 BAA) (Ex: Glutationa Transferases) *** A comparação de sequências de DNA (~600 MAA).
*
*
- Alinhamento de sequências: Identificação das correspondências entre os pares de resíduos
Dadas duas sequências: 1 a b c d e
 2 a c d e f
 Alinhamento razoável: a b c d e -
 a – c d - f
- Definição de critérios para que um algoritmo possa escolher o MELHOR alinhamento
 Alinhamento sem sentido: - - - - - - - g c t g a a c g
 c t a t a a t c - - - - - - -
 Alinhamento sem lacunas: g c t g a a c g
 c t a t a a t c
 Alinhamento com lacunas: g c t g a - a - - c g
 - - c t - a t a a t c
 E mais um : g c t g – a a - c g
 - c t a t a a t c - 
MELHOR
*
*
1) MONTAGEM DE SEQUENCIAS CURTAS DE DNA e/ou RNA
2) MONTAGEM SEQUENCIAS DE GENOMAS
3) LOCALIZAÇÃO DE SEQUENCIAS EM BANCO DE DADOS
ALINHAMENTO DE SEQUENCIAS
APLICAÇOES:
*
*
1) MONTAGEM DE SEQUENCIAS CURTAS DE RNA
*
*
1-2) MONTAGEM DE SEQUENCIAS CURTAS DE DNA e GENOMAS
Biblioteca de BACs
BAC selecionado
Clones do
BAC selecionado
PROBLEMA 1: a) Ordenar/alinhar os clones sequenciados até refazer o BAC
b) Ordenar/alinhar os BACs até refazer o CROMOSSOMO
*
*
3) LOCALIZAÇÃO DE SEQUENCIAS EM BANCO DE DADOS
>my_contig_sequence
CCACGCGTCCGCACACACCATCCGTCTCCGCAGCAACACACGAAAAGAAAGGAAAGGAAAGGAAAGGAAG
CCATGGCGCCGAGGACGTCGGAGAAGGCGGCGGCACCGTCTGCGGCTGCGACCGGGCTGGCGCTTGGCGT CAGCGGCGGCGGAGGTGTCGGGACACACTTCAGGGGCGTGAGGAAGCGGCCGTGGGGGCGGTACGCGGCG GAGATCCGCGACCCGGCCAAGAAGTGCCGCGTGTGGCTGGGCACGTACGACACCGCCGAGGAGGCGGCTC
ISSO … UM GENE?
BUSCAR SEQUENCIA
ALGUEM SEQUENCIOU ALGO PARECIDO?
CONTENDO
QUAL … A FUNÇÃO DESTA SEQUENCIA?
HOMOLOGIAS
*
*
Significado biológico do alinhamento de sequências
Definindo 3 termos importantes:
identidade -> refere-se à presença do mesmo ac. nucléico (nt) ou aminoácido (aa) na mesma posição em 2 seqs. alinhadas.
similaridade -> é uma medida que considera a probabilidade do alinhamento ter ocorrido por acaso (e-value). Considera todos os outros possíveis alinhamentos. AA com propriedades químicas semelhantes.
homologia -> refere-se a relação evolutiva entre as seqs. Duas sequências homólogas derivam da mesma seq. ancentral.
o alinhamento é muito útil na predição de função, estrutura e inferência filogenética. 
*
*
Relação entre as sequências
*
*
DIFERENTES ESTRATEGIAS PARA A BUSCA DE 	PADROES ENTRE INFORMAÇÕES DO DNA
GENOMA
GENE
PROTEONA
RNA
*
*
Modelos para alinhamentos
-# Alinhamento global
 - útil quando as duas sequências tem tamanhos próximos
 - Exemplo de programa : CLUSTAL
 # Alinhamento local
 - útil para alinhamento entre sequências de tamanhos diferentes 
e também para sequências com apenas alguns trechos e também para sequências com apenas alguns trechos conservados 
 - Exemplo de programa : BLAST E FASTA
# Alinhamento semi-global (ou pontas livres)
 - útil para encontrar sobreposições de fragmentos de sequenciamento
 - Exemplo de programa : PHRAP E CAP3
*
*
VISÃO GERAL - DIFERENÇAS 
*
*
Similar ao alinhamento global, mas ignora espaços nos extremos das seqüências.
Aplicação: Montagem de Fragmentos
Ex:
 --------CAGCACTTGGATTAGAC
 TACCTGCGCAGCG-TGG-------- 
Teremos 6 matches, 2 mismatches e 1 space.
Alinhamento Semi-global 
*
*
Alinhamentos
- A comparação entre sequências de DNA de organismos diferentes é baseada no conceito de que estes organismos originaram-se de um ancestral comum.
- No contexto de evolução as sequências de DNA sofrem mutações. Estas modificações locais entre os nucleotídeos podem ser :
	- Inserções : inserção de uma base ou várias bases na
	sequência;
	- Deleções : deleção de uma base ou mais bases na sequência
	- Substituições : substituição de uma base por outra
- Portanto um programa de alinhamento de sequências biológicas tem que considerar essas mutações.
*
*
Métodos de alinhamento de sequências
Alinhamento de pares de seqs.
Matriz de pontos (dot matrix).
Programação dinâmica.
Dicionário de palavras ou k-tuplas (BLAST).
Alinhamento de múltiplas seqs.
*
*
Matriz de pontos (dot plot)
Comparar duas sequências buscando possíveis alinhamentos de caracteres entre as seqs.
*
*
Matriz de pontos (dot plot)
Comparação de sequências genômicas pareadas
*
*
Matriz de pontos (dot plot)
Sequências repetitivas e inversões
*
*
Programação dinâmica
- Motivação : gerar e testar o score de todos os possíveis alinhamentos
- é exponencial no tamanho das seqüências (n^n), onde n é o tamanho das sequências :
- Se o alinhamento de 2 sequências de 100 pb leva 1 segundo,
o alinhamento de duas sequências de 1000 bp levaria trilhões de anos.
- Abordagem alternativa : Com programação dinâmica o tempo de processamento e memória ficam quadráticos (n^2):
- Se o alinhamento de 2 sequências de 100 pb leva 1 segundo, o alinhamento de 2 sequências de 1000 pb leva 100 segundos
- Mas ainda não está bom, pois alinhamento de sequências de 10 Mpb (genoma de Saccharomyces) levaria 377 anos.
*
*
Programação dinâmica (PD)
Método computacional que calcula o melhor alinhamento possível entre sequências 
Principais variáveis do programa:
match
mismatch
gap
*
*
Exemplo de uma Matriz PD
Sequence #1: GAATTCAGTTA; M = 11
Sequence #2: GGATCGA; N = 7
Matriz PD:
				M+1 linhas, N+1 colunas
*
*
Descrição do algoritmo de PD
Si,j = MAX[ Si-1, j-1 + s(ai,bj) (match/mismatch), 
 		 Si,j-1 + w (gap seq #1), 
		 Si-1,j + w (gap seq #2) ]  
Variáveis do programa:
·        s(aibj) = +5 if ai = bj (match score)
·        s(aibj) = -3 if aibj (mismatch score)
·        w = -4 (gap penalty)
S= score
*
*
Alinhamento global 
(Needleman-Wunsch)
Inicialização da 1a. linha e 1a. coluna:
Si,0 = w * i
S0,j = w * j
S1,1 = S0,0 + 5 
*
*
Preenchendo a Matriz PD
(alinhamento global)
S1,1 = MAX[S0,0 + 5, S1,0 - 4, S0,1 - 4] = MAX[5, -8, -8] 
Si,j = MAX[ Si-1, j-1 + s(ai,bj) (match/mismatch), 
 		 Si,j-1 + w (gap seq #1), 
		 Si-1,j + w (gap seq #2) ]  
*
*
Preenchendo a Matriz PD
 (alinhamento global)
S1,2 = MAX[S0,1 -3, S1,1 - 4, S0,2 - 4] = MAX[-4 - 3, 5 – 4, -8 – 4] = MAX[-7, 1, -12] = 1 
Si,j = MAX[ Si-1, j-1 + s(ai,bj) (match/mismatch), 
 		 Si,j-1 + w (gap seq #1), 
		 Si-1,j + w (gap seq #2) ]  
*
*
 Matriz PD preenchida
 (alinhamento global)
Variáveis do programa:
·        s(aibj) = +5 if ai = bj (match score)
·        s(aibj) = -3 if aibj (mismatch score)
·        w = -4 (gap penalty)
Si,j = MAX[ Si-1, j-1 + s(ai,bj) (match/mismatch), 
 		 Si,j-1 + w (gap seq #1), 
		 Si-1,j + w (gap seq #2) ]  
*
*
Trace back
 (alinhamento global)
*
*
Trace back
 (alinhamento global)
G A A T T C A G T T A
| |
| | | |
G G A – T C – G - — A
*
*
Verificando o score de alinhamento
G A A T T C A G T T A
| | | | | |
G G A – T C – G - — A
+ - + - + + - + - - +
5 3 5 4 5 5 4 5 4 4 5
 
5 – 3 + 5 – 4 + 5 + 5 – 4 + 5 – 4 – 4 + 5 = 11
*
*
O melhor alinhamento entre duas seqüências:
G A - C G G A T T A G
G A T C G G A A T A G
é dado por um score que é a soma dos valores associados a cada posição, de acordo com o critério pré-definido.
Maior score é o melhor alinhamento
Alinhamento Global . Algoritmo de Needleman-Wunsch
*
*
Ex: match
+1
mismatch -1
space
-2
O score que é a soma dos valores
associados a cada posição, de acordo
com o grau de similaridade entre os
elementos correspondentes.
Alinhamento Global . Algoritmo de Needleman-Wunsch
*
*
Alinhamento Global - Algoritmo de Needleman-Wunsch
Score do Alinhamento
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
match
mismatch gap
1*9
-1*1
-2*1
*
*
Alinhamento Global - Algoritmo de Needleman-Wunsch
*
*
Alinhamento Global - Algoritmo de Needleman-Wunsch
Score de um Alinhamento
G A - - - - C G G A T T A G
G A TTTT C G G A AT A G
match
mismatch gap open
gap extension
1	* 9
-1	* 1
-2	* 1
-0.5 * 4
score = [(9 *1)+ (1*(-1) )+ (1*(-2)) + 4*(-0.5)]=
*
*
Dúvidas ????