Alinhamento de sequências
Prof. Dr. Francisco Prosdocimi
Definição
 O alinhamento de
sequências consiste no
processo de comparar
duas ou mais sequências
(de nucleotídeos ou
aminoácidos) de forma a
se observar seu nível de
similaridade
 Comparação de strings
 Identificação de substrings
compartilhadas
 Uma das mais poderosas
técnicas da bioinformática
Tipos de alinhamento
• Simples X Múltiplo
• Local X Global
• Heurístico X Ótimo
Score = 276 bits (139), Expect = 3e-78
Identities = 139/139 (100%)
Strand = Plus / Plus
Query: 326 aggtgtaaaaccgtttgaatgcacttattgttataaaggattcactcgaaattctgatct 385
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Sbjct: 560 aggtgtaaaaccgtttgaatgcacttattgttataaaggattcactcgaaattctgatct 619
Query: 386 tcataagcacatcgacgctgttcacaaaggtctcaagcctttcggatgtgaagtatgcca 445
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Sbjct: 620 tcataagcacatcgacgctgttcacaaaggtctcaagcctttcggatgtgaagtatgcca 679
Query: 446 gcgaaacttctctcagaaa 464
|||||||||||||||||||
Sbjct: 680 gcgaaacttctctcagaaa 698
Alinhamento Simples
• Aquele realizado entre seqüências de DNA ou
proteínas, desde que duas a duas
Score = 652 bits (329), Expect = 0.0
Identities = 240/240 (100%)
Strand = Plus / Plus
Interpretando os valores
Query: 1
ctttcaagatgaacgaaccaactggtgtcgggccaacatttgctgatgcatgcgatgatg 60
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Sbjct: 136 ctttcaagatgaacgaaccaactggtgtcgggccaacatttgctgatgcatgcgatgatg 195
Query: 61
gcgaacttatcagcatttgttgtctttgtggtaaaacgttttcaagtcagagtcttctac 120
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Sbjct: 196 gcgaacttatcagcatttgttgtctttgtggtaaaacgttttcaagtcagagtcttctac 255
Query: 121 acaaacattttgaattgatgcatgaaggtacggaaatagatactgaacagtatgatctaa 180
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Sbjct: 256 acaaacattttgaattgatgcatgaaggtacggaaatagatactgaacagtatgatctaa 315
Query: 181 gtggatttgccgctatggggaatgaacaaggtcgtaaaagtaatggtgaagaagatgcaa 240
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Sbjct: 316 gtggatttgccgctatggggaatgaacaaggtcgtaaaagtaatggtgaagaagatgcaa 375
Alinhamento múltiplo
• Aquele realizado entre MAIS DE DUAS
seqüências de DNA ou proteínas
Seq1
Seq4
Seq2
Seq3
------------------------------------------------------------GCACGAGGACTGTGA-----ACCGAATCGGTTCAGTAAAATGTTCAATTGTGCGCTGGA
------------------------------GTTCAGTAAAATGTTCAATTGTGCGCTGGA
GGCACGAGGGCTACGACTGTGAACGAATCGGTTCAGTAAAATGTTCAATTGTGCGCTGGA
Seq1
Seq4
Seq2
Seq3
-----------------------------------------------------------ATCTATTGTGTAGACTATTAACTATGGAATTTTACTTCACATTGACTAAAAAGCTGAGCA
ATCTATTGTGTAGACT-TTAACTATGGAATTTTACTTCACATTGACTAAAAAGCTGAGCA
ATCTATTGTGTAGACTATTAACTATGGAATTTTACTTCACATT-ACTAAAAAGCTGAGCA
Seq1
Seq4
Seq2
Seq3
---------------------CTTTCAAGATGAACGAACCAACTGGTGTCGGGCCAACAT
AATATACCTGGAGCGTTCAGACTTTCAAGATGAACGAACCAACTGGTGTCGGGCCAACAT
AATATACCTGGAGCGTTCAGACTTTCAAGATGAACGAACCAACTGGTGTCGGGCCAACAT
AATATACCTGGAGCGTTCAGACTTTCAAGATGAACGAACCAACTGGTGTCGGGCCAACAT
***************************************
Alinhamentos Global e Local
• Global: as seqs são alinhadas de ponta a ponta
• Local: pedaços das seqs é que são comparados
Qual deles
é melhor?
Alinhamentos ótimo e
heurístico
• heurística -- do dicionário Houaiss
Acepções
¦ substantivo feminino
1
arte de inventar, de fazer descobertas; ciência que tem por objeto a
descoberta dos fatos
1.1
Rubrica: história.
ramo da História voltado à pesquisa de fontes e documentos
1.2
Rubrica: informática.
método de investigação baseado na aproximação progressiva de um dado
problema
1.3
Rubrica: pedagogia.
método educacional que consiste em fazer descobrir pelo aluno o que se
lhe quer ensinar
LOGO:
• Alinhamento ótimo: produz o melhor resultado computacionalmente
possível
• Alinhamento heurístico: produz um resultado o mais próximo
possível do resultado ótimo, mas, principalmente, produz um
resultado de maneira muito veloz
Ferramentas de alinhamento
Programa
Tipo de
Alinhamento
Precisão do
Alinhamento
Número de seqüências
a serem alinhadas
BLAST2Sequences
Local
Heurístico
2
SWAT
(Smith-Waterman)
Local
Ótimo
2
ClustalW
Global
Heurístico
N
Multalin
Global
Heurístico
N
Needleman-Wunsch
Global
Ótimo
2
Elementos de um alinhamento
Matrizes de substituição
• Definem pontuação
específica específica
para a troca entre
símbolos
• Qual a diferença entre as
duas matrizes ao lado
• Modelos de substituição
– Jukes-Cantor X Kimura
A
C
G
T
A
1
-2
-2
-2
C
-2
1
-2
-2
G
-2
-2
1
-2
T
-2
-2
-2
1
A
C
G
T
A
1
-2
-1
-2
C
-2
1
-2
-1
G
-1
-2
1
-2
T
-2
-1
-2
1
Matrizes de
substituição de aminoácidos
Outros parâmetros
• Matrizes de substituição definem a pontuação
para matches e mismatches
• A penalidade de abertura e extensão de gaps
também é importante
• Na maioria dos programas, o usuário pode
fornecer um parâmetro para modificar a
pontução
– Não deve ser utilizado a menos que se saiba o que
se está fazendo
BLAST
Prof. Dr. Francisco Prosdocimi
BLAST
• Basic Local Alignment Search Tool
• Ferramenta de alinhamento mais utilizada no mundo
• Todo pesquisador em biologia molecular já usou
alguma vez (ou centenas de vezes)
• Diz-se que o trabalho original onde a ferramenta foi
publicada é o mais citado da história das ciências
biológicas
• É um algoritmo de alinhamento simples, heurístico e
local
• Alinha um seqüência de entrada contra uma base de
dados desejada
Sub-programas BLAST
Formato da
Seqüência de
Entrada
Banco de
dados
Formato da
seqüência que
é comparado
Programa
BLAST
adequado
Nucleotídeos
Nucleotídeos
Nucleotídeos
BLASTn
Proteínas
Proteínas
Proteínas
BLASTp
Nucleotídeos
Proteínas
Proteínas
BLASTx
Proteínas
Nucleotídeos
Proteínas
TBLASTn
Nucleotídeos
Nucleotídeos
Proteínas
TBLASTtx
BLAST, funcionamento
•
Heurístico
•
Define um tamanho de palavra
chamado seed (semente)
– Blastn = 11; Megablast = 28
– Blastx = 3;
•
Procura em seu banco de dados
sequências com 100% de match
da seed quando comparada com
a query
•
Alonga a extremidade da seed até
onde o alinhamento seja “bom”
•
Metodologia verdadeiramente
rápida
•
E-value: chance estatística de
encontrar aquele ao alinhamento
ao acaso, dado o tamanho da DB
Bases de dados BLAST
• Apresentam um formato especial
• As sequências no formato FASTA devem ser formatadas
usando um programa especial (formatdb)
– Cria uma base de dados com todas as seeds possíveis e as
sequências que as contém
– Dados da base de dados estão pré-computados (velocidade)
• O BLAST então pode comparar uma sequência FASTA
de entrada com o banco de dados pronto
>gi|188497754|ref|NP_000179.2| hexokinase 1 isoform HKI [Homo sapiens]
MIAAQLLAYYFTELKDDQVKKIDKYLYAMRLSDETLIDIMTRFRKEMKNGLSRDFNPTATVKMLPTFVRS
IPDGSEKGDFIALDLGGSSFRILRVQVNHEKNQNVHMESEVYDTPENIVHGSGSQLFDHVAECLGDFMEK
RKIKDKKLPVGFTFSFPCQQSKIDEAILITWTKRFKASGVEGADVVKLLNKAIKKRGDYDANIVAVVNDT
VGTMMTCGYDDQHCEVGLIIGTGTNACYMEELRHIDLVEGDEGRMCINTEWGAFGDDGSLEDIRTEFDRE
IDRGSLNPGKQLFEKMVSGMYLGELVRLILVKMAKEGLLFEGRITPELLTRGKFNTSDVSAIEKNKEGLH
NAKEILTRLGVEPSDDDCVSVQHVCTIVSFRSANLVAATLGAILNRLRDNKGTPRLRTTVGVDGSLYKTH
PQYSRRFHKTLRRLVPDSDVRFLLSESGSGKGAAMVTAVAYRLAEQHRQIEETLAHFHLTKDMLLEVKKR
MRAEMELGLRKQTHNNAVVKMLPSFVRRTPDGTENGDFLALDLGGTNFRVLLVKIRSGKKRTVEMHNKIY
AIPIEIMQGTGEELFDHIVSCISDFLDYMGIKGPRMPLGFTFSFPCQQTSLDAGILITWTKGFKATDCVG
HDVVTLLRDAIKRREEFDLDVVAVVNDTVGTMMTCAYEEPTCEVGLIVGTGSNACYMEEMKNVEMVEGDQ
GQMCINMEWGAFGDNGCLDDIRTHYDRLVDEYSLNAGKQRYEKMISGMYLGEIVRNILIDFTKKGFLFRG
QISETLKTRGIFETKFLSQIESDRLALLQVRAILQQLGLNSTCDDSILVKTVCGVVSRRAAQLCGAGMAA
VVDKIRENRGLDRLNVTVGVDGTLYKLHPHFSRIMHQTVKELSPKCNVSFLLSEDGSGKGAALITAVGVR
LRTEASS
Query
and
Subject
BlastDB
BLAST em LINUX
• Download dos programas executáveis BLAST
através do NCBI
• Permite que o usuário monte sua própria base
de dados específica para um projeto
• Permite parametrização detalhada
$> formatdb –i cog.fasta –p T –n COG
$> blastall –p blastp –i hexokinase.fasta –d COG –e 10 –m 10 –o
hexokinase.blast.output –F T –v 500 –b 250 –M BLOSUM62
Alinhamentos múltiplos
Prof. Dr. Francisco Prosdocimi
What is a multiple alignment?
conserved residues
conservation profile
secondary structure
Blocos conservados
DbClustal
• Blocos conservados
– Domínios funcionais
– Sítios catalíticos de enzimas
– Assinaturas de famílias gênicas
Alinhamentos múltiplos
• Problema altamente complexo
• Teoria da complexidade de algoritmos
– O valor de O
• Problema NP-completo (NP-hard)
– Aumentando o número de sequências (ou o tamanho
das sequências), o aumento no tempo de
computação sobe exponencialmente
• Clustal, MAFFT, T-coffe, MUSCLE, DIALIGN
Alinhamentos múltiplos e homologia
Do alinhamento à filogenia
• Métodos fenéticos
Example in Clustalx :
• Montagem
distance between 2 sequences = 1- No. identical residues
da matrix de
No. aligned residues
distância
Hbb_human
Hbb_horse
Hba_human
Hba_horse
Myg_phyca
Glb5_petma
Lgb2_lupla
1
2
3
4
5
6
7
.17
.59
.59
.77
.81
.87
1
.60
.59
.77
.82
.86
2
.13
.75
.73
.86
3
.75
.74
.88
4
.80
.93
5
.90
6
7
Produção da árvore
• Método fenético
– Não considera a evolução de cada caráter (coluna no
alinhamento)
– Produz uma árvore a partir de uma matriz de distância gerada
ao considerar todo o conjunto de dados
• Vizinhos mais-próximos
– Neighbor-joining
.081
.226
• Average neighbor
• Nearest neighbor
• Farthest neighbor
.061
.015
.062
6
5
4
3
2.084
.055
.219
1.065
Hbb_human
Hbb_horse
Hba_human
Hba_horse
.398
Myg_phyca
.389
Glb5_petma
.442
Lgb2_lupla
Conclusões
•
O alinhamento de sequências e
as técnicas para implementá-lo
estão entre as mais importantes
tarefas da bioinformática
•
Existe uma limitação para a
análise filogenética que vem do
fato de os alinhamentos multiplos
não serem rápidos ou ótimos
•
O bioinformata deve conhecer as
diferentes técnicas de
alinhamento e saber aplicá-las
corretamente