Alinhamento de sequencias

Métodos de alinhamento de
sequências biológicas
Marcelo Falsarella Carazzolle
Resumo
- Introdução
- Alinhamentos ótimos
- Global
- Local (Smith-Waterman)
- Semi global
- Matrizes de alinhamento (BLOSUM)
- Alinhamentos heurísticos
- BLAST
-PHI-BLAST, PSI-BLAST, MEGABLAST e BLAST2SEQS
Introdução
?
- Uma forma rápida de agregar alguma informação sobre uma
sequência desconhecida é compará-la com um banco de dados de
sequências com funções conhecidas
- Esta comparação é feita através de alinhamentos par a par entre
as sequências. Isto é, se o banco de dados possuir 1000 sequências
conhecidas serão realizados 1000 alinhamentos
- Tipicamente são usados os bancos de dados mundiais (NCBI,
EMBL)
Fonte: http://www3.ebi.ac.uk/Services/DBStats/
- Atualmente uma busca nesses bancos faz 100,000,000 de
alinhamentos
- Existem vários programas de alinhamentos com diferentes metodologias,
sendo que o mais utilizado é o BLAST
Relevância biológica
- Essencialmente esses alinhamentos devem tentar indicar uma
homologia entre as sequências (ou pelos menos terem uma
similaridade estatisticamente significante)
- Similaridade x Homologia
- identidade = número que indica a quantidade de nucleotídeos
alinhados
- similaridade = é uma medida que considera a probabilidade
do alinhamento ter ocorrido por acaso (e-value). Considera
todos os outros possíveis alinhamentos
- homologia = similaridade entre sequências que dividem a
mesma ancestralidade. Possui um significado evolutivo
10
1
0.1
0.01
E-value
value
0.001
0.0001
0.00001 = 1 x 10-5 = 1e-5
1e-10
1e-50
1e-100
1e-180
0
Probabilidade do alinhamento ocorrer por acaso
E-value x probabilidade
Quanto maior o banco de dados, maior o e-value
Outras aplicações de alinhamentos
- Reconstrução
da sequência consensu a partir de sobreposições
de fragmentos de sequências (montagens de sequências de
DNA)
- Alinhamento entre sequências de ESTs e DNA genômico
- Comparação entre proteínas e DNA
- Construção de mapas físicos
- Comparação entre genomas
- ...
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
Exemplo :
Gap = -2
Match = 1
Mismatch = -1
- Gaps representam as inserções e deleções entre as sequências
- O melhor alinhamento entre duas sequências é aquele que
maximiza o score :
- Score = #Matchs * (1) + #Mismatch * (-1) + #Gaps * (-2)
= 24 – 4 – 10 = 10
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
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
Programação dinâmica
- Motivação
: gerar e testar o score de todos os possíveis alinhamentos
é exponencial no tamanho das seqüências (nn ), 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 : programação dinâmica. Com programação
dinâmica o tempo de processamento e memória ficam quadráticos
(n2):
- 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
Alinhamento global
- Alinhamento de GACATTG com GATCAATG
1a linha e 1a coluna da matriz são fáceis de computar:
- G A C A T T G
G
A
T
C
A
A
T
G
0
-2
-4
-6
-8
-10
-12
-14
-16
-2
G
-
-4 -6 -8 -10 -12 -14
GA
- -
Lembre-se, penalidade
de 1 gap = -2 e de dois
gaps = -4
http://bioweb.pasteur.fr/seqanal/interfaces/stretcher-simple.html
-
G
A
T
C
A
A
T
G
- Para
0
-2
-4
-6
-8
-10
-12
-14
-16
G
A
C A T T G
-2
-4
-6
-8
-10 -12 -14
[i,j]=p(i,j)
um elemento da matriz [i,j] qualquer, temos p(i,j) = 1 se for
um match e p(i,j) = -1 se for um mismatch.
-
G
A
T
C
A
A
T
G
-O
0
-2
-4
-6
-8
-10
-12
-14
-16
G
A
C A T T G
-2
-4
-6
-8
-10 -12 -14
[i-1,j-1] [i-1,j]
[i,j-1] [i,j] = max([i-1,j] - 2,
[i-1,j-1] + p(i,j),
[i,j-1] - 2)
valor de [i,j] é definido exclusivamente pelos elementos [i-1,j-1]
(diagonal), [i,j-1] (esquerda) e [i-1,j] (acima).
- Construindo o alinhamento
A
G
C
0
-2
-4
-6
A
-2
1
-1
-3
A
-4
-1
0
-2
A
-6
-3
-2
-1
C
-8
-5
-4
-1
No alinhamento global o alinhamento deve ser construído a partir
do extremo da matriz
Alinhamento local (Smith-Waterman)
http://bioweb.pasteur.fr/seqanal/interfaces/water.html
G
A
T
C
A
A
T
G
- No
-
G
A
C A T T G
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
[i-1,j-1] [i-1,j]
[i,j-1] [i,j] = max([i-1,j] - 2,
[i-1,j-1] + p(i,j),
[i,j-1] – 2,
0 zero)
alinhamento local a primeira linha e coluna são inicializadas com
zeros e os valores [i,j] da matriz inteira nunca ficam menores que zero
No alinhamento local o alinhamento deve ser construído partir do
maior score da matriz e para quando encontrar um score=0
Alinhamento semi-global
- Não penaliza espaços nas extremidades do
alinhamento.
- Exemplo CAGCA –CTTGGATTCTCGC
|| | | | |
- - - CAGCGTGG - - - - - - - - No global teríamos,
CAGCA – CTTGGATTCTCGC
CAGC - - - - - - G - T - - - - - - Qual dos dois alinhamentos é mais
interessante ?
- No
alinhamento semi-global a primeira linha e coluna são
inicializadas com zeros. O resto é igual ao alinhamento global
- A abordagem de programação dinâmica é importante pois garante o melhor
alinhamento entre duas seguências, mas ainda temos um problema :
- Lembram-se disso : se o alinhamento de 2 sequências de 100 pb leva 1
segundo, o alinhamento de sequências de 10 Mpb (genoma de
Saccharomyces) leva 377 anos
- A abordagem alternativa é conhecida como o método de k-tuplas, no qual
não é garantido encontrar o alinhamento ótimo (heurística) mas é
significantemente mais rápido. Com esse método os conceitos de alinhamento
discutidos acima foram modificados dando origem aos programas de
alinhamento local :
- BLAST (Basic Local Align Sequence Tool) : Nucleic Acid Research 25
(1990), 3389
- FASTA : PNAS 85 (1988), 2444-2448
- Basicamente este método identifica uma série de palavras curtas em uma das
sequências (word size) e depois realiza uma busca exata por essas palavras nas
sequências a serem comparadas, filtrando assim os possíveis candidatos.
Alinhando proteínas
- Alinhamento proteína-proteína
- Alinhamento nucleotídeo-proteína
- Alinhamento proteína-nucleotídeo
- Alinhamento nucleotídeo-nucleotídeo (feito em proteínas)
Matrizes de substituição
- BLOSUM (BLOcks of amino acid SUbstitution Matrix )
- I e V => Hidrofóbicos
- D e W => D (carga negativa) e W (aromático)
- C => pontes de sulfeto (estrutural)
A matriz foi construída a partir de alinhamentos
múltiplos globais de 504 grupos de proteínas
-
- BLOSUM 62 : grupos com similaridade >62%
- BLOSUM 80 : grupos com similaridade >80%
- BLOSUM 45 : grupos com similaridade >45%
Query Length
Substitution Matrix
<35
PAM-30
35-50
PAM-70
50-85
BLOSUM-80
>85
BLOSUM-62
PNAS 89 (1992), 10915-19919
BLAST
• Basic Local Alignment Search Tool
• Algoritmo BLAST (Alstchul et al.; 1990 – J. Biol., 215, 403410)
• Implementações: NCBI BLAST e WU-BLAST
• Acesso via web / local (linux)
• Consulta de seqüências em BDs biológicos (nt ou proteínas)
• Alinhamento – sobreposição de trechos semelhante de duas
seqüências (seqs). BLAST traz pontuação e mostra
alinhamentos.
• Similaridade – grau de semelhança de seqs num alinhamento.
• Homologia – genes com ancestral comum
• BDs – nucleotídeos, proteínas, domínios,
genomas específicos, dados particulares
• Blastp – prot / prot (distantes)
• Blastn – nt / nt (próximos)
• Blastx – nt trad / prot (novas seqs)
• Tblastn – prot / nt trad (regiões não anotadas)
• Tblastx – nt trad / nt trad
Query
BD
Compara Programa
nt
nt
nt
blastn
nt (trad)
aa
aa
blastx
aa
aa
aa
blastp
aa
nt (trad)
aa
tblastn
nt (trad) nt (trad)
aa
tblastx
Query = formato da seq de entrada.
BD = formato das seqs do BD.
nt (trad) = seq em nt traduzida pelo programa.
Compara = o que é comparado, nucleotídeos (nt) ou aminoácidos (aa).
Programa = um dos cinco principais tipos de blast.
BLAST interface
BLASTp
http://www.ncbi.nlm.nih.gov/blast/
Limita a região da sequência
que será usada na consulta
Pode ser usado um arquivo com várias
sequências gravadas no formato fasta
Pode ser colocado várias sequências ao mesmo tempo ou
vários GI’s (genbank identifier)
Filtro por organismo, use o banco de
taxonomia do NCBI para ver a forma
correta de escrever o organismo
Banco de dados de proteínas do NCBI
Filtros mais elaborados usando as opções
avançadas de busca do NCBI :
protease NOT hiv1[organism] => retornará
apenas resultados com proteases que não sejam
do organismo HIV 1
Banco de dados de proteínas curadas
pelo EBI
Banco de dados de proteínas com a
estrutura tridimensional conhecida
Número máximo de sequências alinhadas
E-value de corte
Número de bases que serão
utilizados para formar as k-tuplas
Altera as penalidades de criação e
extensão de gaps no alinhamento
Mascara regiões de repetição
Link
Corte 1e-5
1
64
query
subject
1
71
134
BLASTx – diferenças importantes
Diferentes códigos genéticos para diferentes organismos
A mudança no
frame de leitura
gera a quebra do
alinhamento
formando
dois
HSP´s
(high
scoring pair)
91
1
63
95
243
query
subject
1
11
10
60
BLAST local
• Pode ser instalado localmente
• Bancos de dados próprios e atualizações
• Facilidades
–
–
–
–
–
Velocidade de buscas
Maleabilidade
Automatização
Dados locais
Independe de internet
PHI-BLAST
-É
um blastp com a opção de passar uma outra sequência curta ou
um padrão servindo como um vínculo para a consulta
N - Qualquer nucleotídeo
N(3) - Uma sequência de três nucleotídeos
N(2,4) - Uma sequência de 2,3 ou 4
nucleotídeos
[AC] - pode ser um A ou um C
{AG} - não pode ser nem A e nem G
Ex :
[CG](5)TG{A}N(1,5)C
PSI-BLAST
-É
um blastp interativo no qual a matriz (BLOSUM), após a primeira
interação, é refeita com base nos alinhamentos entre as proteínas
resultantes da consulta :
- uma posicão conservada no alinhamento recebe um score
alto e uma posição não conservada um score baixo
- É útil para encontrar membros distantes de famílias de proteínas
BL2SEQS
- Faz um alinhamento de uma sequência contra a outra (blastn/blastx/blastp/tblastx/tblastn)
- http://www.ncbi.nlm.nih.gov/BLAST/bl2seq/wblast2.cgi
Spliced alignments
http://mobyle.pasteur.fr/cgi-bin/MobylePortal/portal.py?form=est2genome
Alinhamento de genomas
http://asap.ahabs.wisc.edu/mauve/
FIM