aula8_ibm1029

Prévia do material em texto

1
IBM1029
Introdução à Bioinformática
Aula 8
Profª Drª Silvana Giuliatti
Departamento de Genética – Bloco G
Ramal: 4503
silvana@rge.fmrp.usp.br
Faculdade de Medicina
Departamento de Genética
Métodos por Palavras
Métodos de Palavras
• Alinham sequências mais rapidamente.
• Procuram por partes curtas idênticas (palavras ou 
k-tuplas).
• Pesquisas em bancos de dados: FASTA e BLAST
• Seguem um método heurístico.
FASTA
Métodos de Palavras
FASTA
• Desenvolvido por Pearson e Lipman (1988).
• Uma sequência de proteína ou DNA com todas as 
sequências num banco de dados.
• Apresenta os alinhamentos locais da sequência
analisada com as sequências do banco.
FASTA
• Algoritmo escrito em linguagem C.
• Mais lento que BLAST.
• Procura por um número k de consecutivas letras 
(aminoácidos ou nucleotídeos): palavras ou k-
tuplas.
2
FASTA
• A sequência de entrada deve estar no formato 
FASTA.
• O algoritmo pode ser dividido em 4 etapas:
a) seleção das 10 melhores regiões.
b) re-classificação das 10 melhores regiões.
c) seleção das seqüências mais semelhantes.
d) alinhamento das seqüências selecionadas.
FASTA
a) Seleção das 10 melhores regiões.
• A sequência de entrada (query) é comparada com cada 
sequência do banco de dados.
• Buscar por identidades de comprimento k:
• 4 - 6 para nucleotídeos
• 1 - 2 para aminoácidos
Exemplo: Considere
Seq. Query: TPDEMLVFYDEIR
Seq. Banco: CSGATPTPDEMLVFYW
e palavra de k = 2.
FASTA
Sequência Query Sequência do Banco
1 2 3 9 7 8 9 10 11 
T P D E M L V Y D E I R F C S G A W C T P T P D E M L V F Y W 
1
2
Tabela Indexada
(“Hashing Table”)
K-tuplas
A cada k-tupla associa-se um índice
3, 9
7-1 = 6 9 -1 = 8 10 – 2 = 8 11 – 9 = 2 11 – 3 = 8
2 3 4 5 6 7 8 9
-SQ +SBHistograma das Diagonais
(frrequência)
FASTA
• Escolher as 10 maiores frequências (10 melhores 
diagonais).
FASTA
b) Re-classificação das 10 melhores regiões.
• Calcular o score das regiões escolhidas usando matriz 
de pontuação.
• São geradas as melhores regiões iniciais (INIT1).
S10
S1
S2
S3
S4
S5
S6
S7
S8
S9
FASTA
c) Seleção das seqüências mais semelhantes.
• O programa checa se as regiões podem ser unidas 
através:
• de suas localizações
• de seus scores
• penalidade por junção (joining penalty)
Regiões mais longas são geradas pela junção das 
INIT1 (score INTN: soma dos scores - gaps)
3
FASTA
S1
S4
S5
S6
S1
S4
S5
S6
Penalidade por junção (j)
S4+S1+S6+S5 - 3j
O score depois é recalculado, gerando o score OPT através 
de um alinhamento por programação dinâmica.
FASTA
d) Alinhamento das seqüências selecionadas.
• Todas as sequências do banco passam pelas 
etapas 1-3.
• As sequências com um score superior a um dado 
valor são selecionadas para a etapa 4, onde cada 
sequência do banco é alinhada com a sequência
de entrada usando uma modificação do método 
descrito por Needleman-Wunsch e Smith-
Waterman.
FASTA
Significância dos Alinhamentos
• Teste de Significância – Monte Carlo
• Calcula-se o score S para o alinhamento das sequências
X e Y (sequência Query e sequência do banco de 
dados).
• Repete-se o processo N vezes (geralmente, N = 100)
• Aleatoriamente, reordena X e calcula score do alinhamento 
com a sequência original Y.
• Aleatoriamente, reordena Y e calcula score do 
alinhamento com a sequência original X.
Se o score do alinhamento, S, for muito maior que os scores
dos alinhamentos aleatórios, então o alinhamento é significante.
FASTA
Z- Score
Z – score = Score – média = S - µ
Desvio-padrão σ
µ
Z
Distribuição 
Normal
Z
Menos 
significante
Mais 
significante
FASTA
A Distribuição do “Valor Extremo”
• O score médio segue a distribuição normal.
• O melhor score segue a distribuição do valor 
extremo.
Distribuição do 
Valor Extremo
( Distribuição de 
Gumbel)
moda
P( S > x ) = 1 – exp(-ke-λx)
FASTA
Estimando os parâmetros de FASTA
• Usa regressão linear para os scores obtidos e calcula um 
valor de z-score normalizado.
S = a + b ln (n)
onde , n é o comprimento da sequência do banco.
• Estima valores de K e λ, e usa os valores estimados para 
calcular o valor esperado E.
• A distribuição de Z é aproximada pela distribuição de 
extremos. 
• Normalizando para média de 50 e desvio-padrão de 10:
Z’(S) = 50 + 10 z
4
FASTA
O Valor Esperado 
E(Z>x) = D x P(Z>x)
onde , D é o número de sequências no banco de dados.
FASTA apresenta:
- o valor normalizado Z´-score
- O número de scores OPT (ótimos) 
- O número de scores esperados.
“=“: curva aproximada para o alinhamento observado.
‘*”: curva aproximada para o alinhamento esperado.
FASTA
A Saída do FASTA
http://fasta.bioch.virginia.edu/fasta
: Identidade
. Substituição conservativa
identidade
Subs. conservativa
Gaps
FASTA
FASTA: compara uma sequência de entrada (proteína ou DNA) 
com um banco de dados (proteínas ou DNA).
TFASTA: compara uma sequência de entrada (proteína) a um
banco de dados de DNA (depois de traduzir o banco nos 6 
frames).
FASTF/TFASTF e FASTS/TFASTS:compara fragmentos curtos 
de peptídeos com um banco de dados de proteína 
(FASTF/FASTS) ou um banco de dados de DNA traduzido 
(TFASTF/TFASTS). 
• FASTF: eletroforese
• FASTS: espectrometria de massa
BLAST
Métodos de Palavras
BLAST
Basic Local Aligment Sequence Tool
• Desenvolvido por Altschul et al. (1990).
5
Métodos de Palavras
BLAST
Basic Local Aligment Sequence Tool
• Alinhamento de uma sequência de proteína ou DNA com 
todas as sequências num banco de dados.
• Apresenta os alinhamentos locais da sequência analisada 
com as sequências do banco.
• Mais rápido que FASTA.
• Algoritmo escrito em linguagem C.
• Procura por um número k de consecutivas letras 
(aminoácidos ou nucletídeos): palavras ou k-tuplas.
BLAST
• Procura por palavras que são mais significantes
• A significância é incorporada ao algoritmo através de 
matrizes de pontuação.
• Buscar por identidades de comprimento k:
• 11 para nucleotídeos
• 3 para aminoácidos
BLAST
• O algoritmo pode ser dividido em 4 etapas:
a) montagem da lista de palavras.
b) procura pelas palavras em cada sequência do 
banco.
c) extensão.
d) alinhamento das seqüências.
BLAST
a) Montagem da lista de palavras.
• Extrair palavras da sequência de entrada e fazer uma lista 
de palavras relacionadas.
Exemplo:
Query: PQGASGDAASEQTPQLA
PQG
QGA
GAS
...
Conjunto W
de palavras
BLAST
P Q G score
palavra P Q G 7 5 6 18
sinônimos P E G 7 2 6 15
P R G 7 1 6 14
P S G 7 0 6 13
P Q A 7 5 0 12
... ... ...
BLOSUM62
valor de corte (threshold) = 13
“high scoring words”
BLAST
b) Procura por cada palavra do conjunto de W e seus 
sinônimos em cada sequência do banco.
• Cada palavra de alto score (high scoring word) será uma 
“semente” para gerar possíveis alinhamentos.
lista
Sequência do banco de dados
6
BLAST
Exemplo: Suponha
1 2 3 4 5 6 7 8 9 10 11 12 13 
Q: Q Q G P H U I Q E G Q Q G
V: QQG
HV: {palavra} = {QQG, QEG} 
Então:
PV: {posição}= {1,11}
Suponha que a sequência do banco seja:
D: PKLMMQQGKQEG
BLAST
Então, os alinhamentos serão:
QQGPHUIQEGQQG palavra: QQG posição: 1
PKLMMQQGKQEG posição’: 6
QQGPHUIQEGQQG palavra: QQG posição: 1
PKLMMQQGKQEG posição’: 10
QQGPHUIQEGQQG palavra: QQG posição: 11
PKLMMQQGKQEG posição’: 6
QQGPHUIQEGQQG palavra: QQG posição: 11
PKLMMQQGKQEG posição’:10
BLAST
c) Extensão
• Para cada palavra encontrada na sequência é realizada 
uma extensão em ambas as direções.
Exemplo:
Extensão apenas para uma direção.
Match = +1
Mismatch = -1
Não é permitido gaps.
Valor limite (drop off score): X= 5
BLAST
query: P Q G L I M A C S G V H D C S R T P G Q R D A K L N M S E
banco: P Q G L I M R W S G V H D S R H H P Q Y Y A K L N C A G T
score: 1 2 3 4 5 6 5 4 5 6 7 8 9 8 7 6 5 6 5 4 3 ...
X: 0 0 0 0 0 0 1 2 1 0 0 0 0 1 2 3 4 3 4 5 
A sequência mais longa obtida com a extensao é
chamada de HSP ( high-scoring segment pair)
BLAST
d) Alinhamento das seqüências
• Determina se cada HSP é estatisticamente 
significante.
Suponha um HSP encontrado para um 
score limite S numa região de comprimento L em 
duas sequências Q e D.
Então, a probabilidade de duas sequências
aleatórias Q´e D´com score S numa região L é 
calculada. O comprimento de Q é o mesmo de 
Q´e de D é o mesmo que o de D´. 
BLAST
Suponha duas sequências de DNA 
aleatórias, alinhadas. Considere a probabilidade de 
obter 6 pares de idênticos.
A probabilidade de obter um par idêntico, por 
exemplo A/A, é: P(A) e P(A) = ¼ x ¼ .
Mas, há 4 possíveis pares idênticos: A/A, C/C, G/G
T/T.
7
BLAST
Então, a probabilidade de obter 1 par idêntico é:
4 x (¼ x ¼) = ¼
E a probabilidade de obter 6 pares idênticos é:
(1/4)6 = 2,4 x 10-4
A probabilidade de obter a mais longa sequência de 
pares idênticos (match) é dada por:
R = log1/p(n) (Lei de Erdös & Rényi)
Exemplo: Para uma sequência de 2 moedas, atiradas 100 
vezes.
CaCoCaCoCa...
CoCaCaCoCa...
p = 0,5 
Então, R = log 2(100) = 6,65
BLAST
Se duas sequências aleatórias de comprimentos m e n 
são alinhadas, a lei pode ser aplicada:
R= log1/p(mxn). 
A probabilidade E de obter um score x maior ou igual ao score de 
limite S entre uma sequência query e uma squência do banco de dados.
E (x>S) = K m n e-λ S 
Onde , m e n são os comprimentos das duas sequências, K e λ são 
parâmetros que são calculados com base no sistema de pontuação e S é o 
valor de limite para o HSP.
Depois de determinar se HSP é estatisticamente 
significante, faz o alinhamento dos melhores 
segmentos.
BLAST
A equação diz que o número de alinhamentos esperados por acaso durante a 
pesquisa com o banco de dados é uma função do tamanho do banco (espaço da pesquisa), 
mxn, do score S normalizado, λS, e de uma constante K.
E (x>S) = K m n e-λ S 
Onde , m é o numero de bases da sequência query, n é o múnero de 
bases no banco de dados e K é um valor de ajuste.
- A relação entre o valor esperado e o espaço da 
pesquisa é linear, ou seja, o banco aumentar o valor 
aumenta ;
- A relação entre o valor esperado e o score é 
exponencial, ou seja, pequenas alterações no banco 
levam a grandes diferenças no valor.
BLAST
O BLAST apresenta em seus resultados dois scores: Bit 
score e Evalue.
A) Bit Score
O Bit score é dado pelo normalização do score S.
Bit score Sbit’ = -λ S - ln K
ln 2
B) Evalue
O Evalue correspondente ao bit score S’.
E = mn 2-Sbit’
BLAST
O BLAST apresenta o E-value e não o valor de P por ser 
mais fácil para se entender a diferença entre os valores, por 
exemplo, entre E-value de 5 e 10 do que entre P de 0,993 e 
0,99995. Entrentanto, se for necessário, o valor de P é 
calculado como segue:
C) P-value
A probabilidade de encontrar pelo menos um 
HSP, é dada por:
P-value = 1 – e-E
BLAST
Score (S)
Score Normalizado (S´)
E-value (E)
P-value (P)
S´= -λ S - ln K
E = mn e-S’
P =1 – e-E
E = K m n e-λ S
Bit-Score
E = mn 2-Sbit’
-λ S – lnK
Bit score Sbit’ = 
ln 2
8
BLAST
Twilight zone: nessa região, nada é garantido sobre o significado das similaridades 
observadas. Homologia ou não, nunca é garantida nessa área. 
Interpretação do Valor Esperado: Evalue
• E<10-100 ⇒ valor muito baixo. Genes homólogos ou idênticos.
• E<10-3 ⇒ valor moderado. Genes podem estar relacionados.
• E>1 ⇒ valor alto. Prováveis genes sem relação.
• 0,5 < E < 1 ⇒ Região duvidosa - “Twilight zone”
Métodos de Palavras
BLAST2 - gapped
• Desenvolvido por Altschul et al. (1997).
• Refinamentos no algoritmo:
• Método 2-hits (two-hits): necessita de 2 hits, sem “overlapping”, 
dentro de uma distância A entre eles, antes da extensao ser 
iniciada.
• Alinhamento com gaps (gapped-BLAST): necessita de 2 hits, sem 
overlapping, dentro de uma distancia A entre eles para iniciar uma 
extensao sem gaps entre eles. Se o HSP gerado tiver um score
acima de um determinado valor, entao uma extensão com gaps é 
iniciada.
BLAST
A Saída do BLAST
www.ncbi.nlm.nih.gov/BLAST/
• Gráfico: mostra onde a sequência de entrada é similar às outras 
sequências.
• Lista de hits: o número de sequências similares à sequência de 
entrada pontuada pela similaridade.
• Alinhamentos: cada alinhamento entre a sequência de entrada e 
cada hit reportado.
• Parâmetros: lista de parâmetros usados pela pesquisa.
Métodos de Palavras
• Gráfico
• A sequência de entrada fica no topo.
• Cada barra representa a parte da sequência similar à 
sequência de entrada.
• Barras vermelhas: indicam as sequências mais similares.
• Barras rosas: indicam matches que são bons, mas não os
“melhores”.
• Barras verdes: são os piores entre os “melhores e bons”.
• Barras pretas: são os ruins (twilight zone)
Bons
Métodos de Palavras
Escala de
similaridade
Ordem decrescente 
de similaridade
Barras interrompidas: alinhamentos originários de extensão de hits diferentes.
• Lista de Hits
Contém:
• Nome e número de acesso da sequências (hiperlink)
• Descrição: analisar o interesse no hit encontrado.
• Score bit: medida de significância estatística do alinhamento.
Quanto + alto o score bit
+ similares são as sequências
• Valor esperado (expectation value): Evalue
Proporciona a medida mais importante de significância estatística.
Quanto + baixo o Evalue
+ similares são as sequências
+ confiança de esse hit seja realmente homólogo à 
sequência de entrada
9
descrição
Métodos de Palavras
• Alinhamentos
Em cada alinhamento pode-se encontrar:
• Identidade em porcentagem: um valor substituto para o 
Evalue.
• Mais de 25% é bom.
• Os positivos fornecem uma medida da fração de resíduos 
que são idênticos ou similares.
• Os gaps mostram resíduos que não foram alinhados.
• Comprimento do alinhamento.
• Sequência de entrada (query) 
Métodos de Palavras
• Sequência do banco de dados (subject)
• Linha entre as sequências: + para similaridade
espaço para mismatch
letra para identidade
• Regiões de baixa complexidade (XXX): Blast mascara as 
regiões de baixa complexidade, ou seja, regiões que possuem 
repetições de mesmo ou de alguns aminoácidos (ou nucleotídeo).
• As coordenadas ao lado das sequências indicam a posição de hit 
entre as sequências.
descrição
positivo
gap
identidade
gaps
Positivos:com preservação das
propriedades físico-químicas
Sem preservação das
propriedades físico-químicas
identidade
Região de baixa complexidade
• Parâmetros Métodos de Palavras
BLAST
BLASTP: compara uma sequência de entrada (proteína) com um 
banco de dados (proteínas).
BLASTN: compara uma sequência de entrada (DNA) a um banco 
de dados (DNA).
BLASTX:compara uma sequência de nucleotídeos, traduzida em 
todas os 6 frames, cm um banco de dados de proteínas. 
TBLASTN: compara uma sequência de proteína com um banco 
de dados de nucleotídeos traduzido em 6 frames.
TBLASTX:compara todos os 6 frames de uma sequência de 
nucleotídeos com um banco de dados de nucleotídeos, traduzidos 
em 6 frames.
10
Métodos de Palavras
BLAST
PSI-BLAST (Position Specific Iterated - BLAST ): performa
pesquisas iterativaspara localizar domínios conservados numa 
sequência de entrada de proteína que também estão presentes em 
sequências de um banco de dados 
PHI-BLAST (Pattern-Hit Initiated - BLAST):muito similar ao 
PSI-BLAST, exceto que a sequencia query é primeiro pesquisada
por um padrão fornecido pelo pesquisador.