Alinhamentos e Busca de Similaridade Ariane Machado Lima

Alinhamentos e Busca de Similaridade

Ariane Machado Lima

Busca de identidade

• Identificar o que é determinada seqüência •Ex.acabou de seqüenciar, seria contaminante?

• Outras fases de um projeto de seqüenciamento

Seqüenciamento shot-gun

Mascaramento de vetor

Montagem

Inferência de função a partir de similaridade

Nem sempre funciona...

Estrutura 3D de proteínas

2 seqüências

cacttttaactctctttccaaagtccttttcatctttccttcacagtacttgttcactat cacttttaactctctttccaaagaacttttcatctttccctcacggtacttgtttgctat

Processo evolutivo

Similaridade (e não identidade) entre os aminoácidos

Evolução convergente

• CUIDADO: Duas seqüências similares e com a mesma função podem não ter o mesmo ancestral...

Homologia, paralogia e ortologia

• Homologia: 2 seqüências são homólogas se elas possuem uma seqüência ancestral comum

• Paralogia: homologia por duplicação

• Ortologia: homologia por especiação

Homologia, paralogia e ortologia

Paralogia

Ortologia

• Se duas (ou mais) seqüências são parecidas:– elas podem ser homólogas– elas podem ter funções similares– elas podem ter a mesma estrutura

Identidade, similaridade e homologia

Busca de similaridade

• Predição de genes

• Predição de função

• Predição de estrutura

• Inferência de árvores filogenéticas

Alinhamentos

• Pairwise: 2 seqüências

• Múltiplo: mais de 2 seqüências

Alinhamentos de 2 seqüências(pairwise)

• “Deixar 2 seqüências o mais parecidas possível”

ROSAVERMELHAAMOROSOVERME

---ROSAVERMELHAAMOROSOVERME---

• Ajustando as posições de suas letras, se necessário usando espaços:

ROSAVERMELHA | AMOROSOVERME

Identidade: 8% (1/12)

---ROSAVERMELHA ||| ||||| AMOROSOVERME---


Sistema de scores

• Pontos para match (ex: +2)

• Penalidades para mismatch (ex: -1)

• Penalidades para gap– abertura (ex: -3)– extensão (ex: -1)

ROSAVERMELHA | AMOROSOVERME


SCORE: ???



SCORE: ???

Identidade, similaridade e homologia

Identidade

Similaridade

Homologia

Tipo de Medida

Quantitativa

Quantitativa

QUALITATIVA

Sentido

quantos idênticos

quantos parecidos

TEM ou NÃO TEMum ancestral comum

Tipos de alinhamentos

• Global

• Local

• Semi-global

Alinhamento global

QUERIDA---ROSAVERMELHA|||| ||| ||||| QUEROUMAMOROSOVERME---

Alinhamento global

• Aplicação:– comparar 2 proteínas (ex. para inferir

estrutura secundária)

Alinhamento global

• Algoritmo Needleman-Wunsch

• Programas:– needle (EMBOSS)– stretcher (EMBOSS) (demora mais, mas

economiza memória)– FASTA

Alinhamento local

QUERIDA---ROSAVERMELHA|||| ||| ||||| QUEROUMAMOROSOVERME---

QUER|||| QUER

ROSAVERME||| ||||| ROSOVERME

Alinhamento local

• Aplicações:– Encontrar um gene em um genoma

– Identificar éxons

– Identificar domínios proteicos

– Identificar possíveis homólogos em um banco de dados

Alinhamento Local

• Algoritmo Smith-Waterman

• Programas– water (EMBOSS)– matcher (demora mais, mas economiza memória)– cross_match (swat) – bom para mascaramento– FASTA– BLAST– BLAT

Alinhamento semi-global


Alinhamento semi-global• Aplicação: montagem de genomas!

Alinhamento múltiplo

Resumindo

• Alinhamento pairwise– global– local– semi-global

• Alinhamento múltiplo (sempre global)

Voltando ao sistema de score...

• Match/mismatch pode ser substituído por

– uma matriz 4x4 (nucleotídeos)

– uma matriz 20x20 (aminoácidos)

Similaridade entre os aminoácidos

Matrizes de score(matrizes de substituição)

• qij: probabilidade do aa i ser substituído pelo aa j

• pi: probabilidade do aa i

mij = log (qij / pi pj) = mij

Mij = 1/ log (qij / pi pj) = Mij

• Como achar qij, pi e pj?

• Algumas matrizes:

– PAMs

– BLOSUMs

Matrizes de score(matrizes de substitição)

Matrizes PAM de aminoácidos – Point Accepted Mutation

• Dayhoff, 1978• Processo:

– Alinhamento de conjuntos de seqüências relacionadas (85% id)

– Construção de árvores filogenéticas

– Cálculo da freqüência de substituição de cada par de aa

– Normalização das freqüências: 1% de mudança ~ 50 milhões de anos (PAM1)

Matrizes PAM de aminoácidos – Point Accepted Mutation

• Em um período de 2 PAMs, pode ter havido A ?, e então ? D

• Extrapolação: PAM2 = PAM1 x PAM1

PAMy = PAM1 x PAM1 x .... x PAM1

• PAM120: 40% de identidade

• PAM250: 20% de identidade

PAM250Diagonal Hidrofóbicos

Hidrofílicos

Problemas das PAMs

• Inferida por um conjunto restrito de proteínas

• Extrapolação

• Muitas novas proteínas foram seqüênciadas desde 78...

Matrizes BLOSUM de aminoácidos

• Henikoff & Henikoff, 1992

• Alinhamentos de blocos de vários grupos de proteínas relacionadas (banco de dados BLOCKS)

• Cálculo de freqüência de substituição de cada par de aa

• BLOSUMx: blocos de seqüências com no máximo x% de identidade

• Ex: BLOSUM62 e BLOSUM85

BLOSUM62Reference: Henikoff, S. and Henikoff, J. G. (1992). Amino acid substitution matrices from protein blocks. Proc. Natl. Acad. Sci. USA 89: 10915-10919.

A R N D C Q E G H I L K M F P S T W Y V B Z X *A 4 -1 -2 -2 0 -1 -1 0 -2 -1 -1 -1 -1 -2 -1 1 0 -3 -2 0 -2 -1 0 -4 R -1 5 0 -2 -3 1 0 -2 0 -3 -2 2 -1 -3 -2 -1 -1 -3 -2 -3 -1 0 -1 -4 N -2 0 6 1 -3 0 0 0 1 -3 -3 0 -2 -3 -2 1 0 -4 -2 -3 3 0 -1 -4 D -2 -2 1 6 -3 0 2 -1 -1 -3 -4 -1 -3 -3 -1 0 -1 -4 -3 -3 4 1 -1 -4 C 0 -3 -3 -3 9 -3 -4 -3 -3 -1 -1 -3 -1 -2 -3 -1 -1 -2 -2 -1 -3 -3 -2 -4 Q -1 1 0 0 -3 5 2 -2 0 -3 -2 1 0 -3 -1 0 -1 -2 -1 -2 0 3 -1 -4 E -1 0 0 2 -4 2 5 -2 0 -3 -3 1 -2 -3 -1 0 -1 -3 -2 -2 1 4 -1 -4 G 0 -2 0 -1 -3 -2 -2 6 -2 -4 -4 -2 -3 -3 -2 0 -2 -2 -3 -3 -1 -2 -1 -4 H -2 0 1 -1 -3 0 0 -2 8 -3 -3 -1 -2 -1 -2 -1 -2 -2 2 -3 0 0 -1 -4 I -1 -3 -3 -3 -1 -3 -3 -4 -3 4 2 -3 1 0 -3 -2 -1 -3 -1 3 -3 -3 -1 -4 L -1 -2 -3 -4 -1 -2 -3 -4 -3 2 4 -2 2 0 -3 -2 -1 -2 -1 1 -4 -3 -1 -4 K -1 2 0 -1 -3 1 1 -2 -1 -3 -2 5 -1 -3 -1 0 -1 -3 -2 -2 0 1 -1 -4 M -1 -1 -2 -3 -1 0 -2 -3 -2 1 2 -1 5 0 -2 -1 -1 -1 -1 1 -3 -1 -1 -4 F -2 -3 -3 -3 -2 -3 -3 -3 -1 0 0 -3 0 6 -4 -2 -2 1 3 -1 -3 -3 -1 -4 P -1 -2 -2 -1 -3 -1 -1 -2 -2 -3 -3 -1 -2 -4 7 -1 -1 -4 -3 -2 -2 -1 -2 -4 S 1 -1 1 0 -1 0 0 0 -1 -2 -2 0 -1 -2 -1 4 1 -3 -2 -2 0 0 0 -4 T 0 -1 0 -1 -1 -1 -1 -2 -2 -1 -1 -1 -1 -2 -1 1 5 -2 -2 0 -1 -1 0 -4 W -3 -3 -4 -4 -2 -2 -3 -2 -2 -3 -2 -3 -1 1 -4 -3 -2 11 2 -3 -4 -3 -2 -4 Y -2 -2 -2 -3 -2 -1 -2 -3 2 -1 -1 -2 -1 3 -3 -2 -2 2 7 -1 -3 -2 -1 -4 V 0 -3 -3 -3 -1 -2 -2 -3 -3 3 1 -2 1 -1 -2 -2 0 -3 -1 4 -3 -2 -1 -4 B -2 -1 3 4 -3 0 1 -1 0 -3 -4 0 -3 -3 -2 0 -1 -4 -3 -3 4 1 -1 -4 Z -1 0 0 1 -3 3 4 -2 0 -3 -3 1 -1 -3 -1 0 -1 -3 -2 -2 1 4 -1 -4 X 0 -1 -1 -1 -2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2 0 0 -2 -1 -1 -1 -1 -1 -4 * -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 1

PAMs e BLOSUMs• Para encontrar alinhamentos mais curtos e

com maior similaridade:

– PAMs

– BLOSUMs

• Para encontrar alinhamentos mais longos e com menor similaridade:

– PAMs

– BLOSUMs

mais baixas

mais baixas

mais altas

mais altas

Papel dos gaps

• Veremos na aula prática....

Significância de scores

• Scores e a distribuição de Gumbel

• P-value (s): probabilidade de obter um score tão bom ou melhor que s puramente por chance em um banco de dados aleatório, do mesmo tamanho e com a mesma composição de bases

• E-value (s): número de hits com score tão bom ou melhor que s puramente por chance em um banco de dados aleatório, do mesmo tamanho e com a mesma composição de bases

Significância de scores

• E-value é um número real não negativo

• Quanto menor... ... melhor!!!!

• E-value depende de...

E(S) = Kmne-S

... por isso não existe número mágico

BLAST

Basic Local Alignment Search Tool

• NCBI BLAST ou WU-BLAST

• Heurísticas

“Palavras” do BLAST (W)

MLILII

MLIIKRDELVISWASHERE seqüência query

IIKIKRKRDRDEDELELVLVIVISISWSWAWASASHSHEHERERE

todas as palavras de tamanho 3 com sobreposição

Outros programas BLAST

• PSI-BLAST – Position-Specific Iterated BLAST:– busca iterativa a partir de seqüências encontradas

• PHI-BLAST – Pattern-Hit Initiated BLAST: – expressões regulares + alinhamento local nos

matches

• MEGABLAST:– algoritmo guloso para acelerar buscas de seqüências

altamente similares (até 10x)

BLAT – Blast Like Alignment Tool

• Mais rápido e mais preciso (para seqüências altamente similares)

• Aplicação: mapeamento de seqüências (ex: transcritos)

• Mantém um índice de todo o banco em memória (non-overlapping k-mers)

Formato FASTA

>Identificador da seqüência

GCCCCCGGCCCCGCCCCGGCCCCGCCCCCGGCCCCGCCCCGCAAGGGTCACAGGTCACGGGGCGGGGCCGAGGCGGAAGCGCCCGCAGCCCGGTACCGGCTCCTCCTGGGCTCCCTCTAGCGCCTTCCCCCCGGCCCGACTCCGCTGGTCAGCGCCAAGTGACTTACGCCCCCGACCTCTGAGCCCGGACCGCTAG

Programas standalone

• Programas como Blast, BLAT e muuuuitos outros:– via web server– standalone (linha de comando) – Perl

scripts!!!!

• netblast: linha de comando, mas executa remotamente

Similaridade de seqüências

Aula Prática

Ex.1: Identidade e similaridade

• Qual é o melhor alinhamento?

a) 100% (10/10)b) 91% (95/104)c) 74% (80/108)d) 53% (59/111)

Alinhamento global

• Needleman-Wunsch• Programas:

– needle (EMBOSS)– stretcher (EMBOSS) (demora mais, mas

economiza memória)– FASTA

• Alinhamento múltiplo:– ClustalW– T-Coffee

Alinhamento local

• Smith-Waterman• Programas

– water (EMBOSS)– matcher (demora mais, mas economiza memória)– cross_match (swat)– FASTA– BLAST

Ex.2: needle• Vamos alinhar as seqüências de uma hemoglobina

humana e outra de camundongo

Ex.2: needle

• Vamos alinhar as seqüências de uma hemoglobina humana e outra de cavalo

http://www.vision.ime.usp.br/~ariane/inverno2008/ex2

Ex.2: needle• http://www.ebi.ac.uk/Tools/emboss/align/


– Gaps default (10.0 ; 0.5)– Conservador (100.0 ; 10.0)– Flexível (1.0 ; 0.1)

http://www.ebi.ac.uk/Tools/emboss/align/

Ex.3: water• http://www.ebi.ac.uk/emboss• Vamos alinhar as seqüências do ex. 2


– Gaps default (10.0 ; 0.5)– Homework:

• Conservador (100.0 ; 10.0)• Flexível (1.0 ; 0.1)

Ex.4: needle• http://www.ebi.ac.uk/emboss• Vamos alinhar as seqüências de um mRNA de

hemoglobina de camundongo com seu locus genômico



Ex.5: water

• http://www.ebi.ac.uk/emboss• Vamos alinhar as seqüências do exercício 4



Ex.6 - Matrizes BLOSUM

• Usando a matriz de escore default BLOSUM62, você encontrou duas proteínas que divergiram bem recentemente.

• Se você quiser refinar seu alinhamento, que matriz você deveria usar (com número mais alto ou mais baixo)?

Ex. 7 - Score e E-value

• Ordene por relevância:a) Score = 155 bits (393), Expect = 4e-37 Identities = 79/150 (52%), Positives = 101/150 (67%), Gaps = 1/150 (0%)b) Score = 74.3 bits (181), Expect = 2e-12 Identities = 36/105 (34%), Positives = 57/105 (54%), Gaps = 0/105 (0%)c) Score = 347 bits (889), Expect = 1e-94 Identities = 167/167 (100%), Positives = 167/167 (100%), Gaps = 0/167

(0%)d) Score = 189 bits (480), Expect = 3e-47 Identities = 88/151 (58%), Positives = 114/151 (75%), Gaps = 1/151 (0%)e) Score = 89.7 bits (221), Expect = 4e-17 Identities = 52/127 (40%), Positives = 68/127 (53%), Gaps = 5/127 (3%)

Ex. 8 - BLAST e filtros

• Vamos buscar seqüências similares a http://www.vision.ime.usp.br/~ariane/inverno2008/ex8

• Qual um programa apropriado?

1) Ligue os filtros2) Desligue os filtros

Ex. 9 - BLASTP

• Busque no SWISSPROT seqüências similares à hemoglobina de camundongo


Ex. 10 - ?

• Você seqüenciou uma seqüência de DNA– Agora você quer encontrar seqüências

similares com alta qualidade de anotação– Assim, você quer começar fazendo uma

busca no SWISSPROT

• Que programa usar?


Ex. 11 - ?

• Você tem uma seqüência de proteína (hemoglobina de camundongo) e quer saber em qual chromossomo está o gene desta proteína.

• Qual programa usar?


Ex: 12 - Seqüências de proteína x DNA

• Seqüências de DNA são menos conservadas que seqüências de aminoácidos, que por sua vez são menos conservadas que a estrutura de uma proteína

• Se você quer inferir função, qual das duas usar?

• Se você quer detalhes mais finos (ex: distância evolutiva), qual usar?

Ex.13 - BLAT

• Útil para buscar seqüências altamente similares (de forma mais rápida)

• Utilize a seqüência de hemoglobina de camundongo para fazer seu mapeamento no genoma de camundongo


Ex.14 - BLAT

• Dá para fazer o mesmo com seqüência de proteína?

• Utilize a seqüência de hemoglobina de proteína de camundongo para fazer seu mapeamento no genoma de camundongo


Ex. 14 - PSI-BLAST• Você se pergunta se há parentes próximos da

família de antígenos de membrana no SWISSPROT.

• Para buscá-las, você decide usar o PSI-BLAST que usa seqüências similares à sua seqüência query (antígeno de membrana) para obter uma descrição mais flexível dessa família.


Ex. 15 - PHI-BLAST

• Além das vantagens do PSI-BLAST, você também quer definir um “padrão” que as seqüências devem ter


Referências

Caprichado:

Mount - http://www.bioinformaticsonline.org/

Básico:

O'Reilly - http://www.oreilly.com/catalog/bioskills/

BLAST:

http://www.oreilly.com/catalog/blast/

Documents

Alinhamentos e Busca de Similaridade Ariane Machado Lima