Alinhamento
Definições e tipos de alinhamento.
O uso do BLAST
Banco de dados


Um banco de dados organiza e estrutura as
informações de modo a facilitar consultas,
atualizações e deleções de dados.
A grande maioria dos bancos de dados é atrelado a
um sistema denominado SGBD (Sistema de
Gerenciamento de Banco de Dados).
– MySQL;
– postgreSQL;
– SQL Server;
– Oracle.
Algoritmo



“Um algoritmo é uma seqüência
finita e não ambígua de instruções
para solucionar um problema ”
Loops e decisões lógicas
http://pt.wikipedia.org/wiki/Algoritmo
Problema do caixeiro
viajante

Problema: Qual o menor caminho para
passar por todas as cidades e depois
voltar a inicial?
Problema do caixeiro
viajante


Solução “ótima”: Calcular a distância
total de todos os caminhos possíveis.
Alta complexidade, (n-1)!
Heurística

“heurística e método heurístico
são denominações para o algoritmo
que fornece soluções sem um limite
formal de qualidade, tipicamente
avaliado empiricamente em termos de
complexidade (média) e qualidade das
soluções”
Similaridade X Homologia


Similaridade é a observação empírica
das semelhanças entre duas
seqüências e pode ser quantificada.
Homologia implica ancestralidade
comum entre duas seqüências,
podendo apenas ser inferida e nunca
quantificada.
Seqüências ortólogas e
parálogas



seqüências ortólogas: as quais têm
origem em um ancestral comum
seqüências parálogas: as quais têm
origem em uma duplicação gênica
– Ex: Hemoglobina F e Hemoglobina A
http://adi-38.bio.ib.usp.br/sismo/tipos.html
Alinhamento


Comparação de duas ou mais
sequências por meio de buscas de
uma série de caracteres ou padrões de
caracteres que estão na mesma ordem
Tipos de alinhamento:
– Global
– Local
– Múltiplo
Para que fazer um
alinhamento?




Filogenia
Busca de similaridade
Anotação de seqüências
Busca em bancos de dados de
seqüências
Alinhamento local

O alinhamento localiza fragmentos de
sequências que são mais similares
Query: 1 ALINHA 6
||||||
Sbjct: 1 ALINHA 6
Alinhamento global

O alinhamento global se estende por
toda a seqüência:
ALINHAMENTO
||||||
|
ALINHAVAD_O
Alinhamento múltiplo


Pode usar alinhamento local ou global
(normalmente global) para alinhar
múltiplas seqüências.
Normalmente alinha duas a duas, e
posteriormente vai juntando as mais
similares
Parâmetros para avaliar
um alinhamento




Programação dinâmica
Concodante - “match”
Discordante - “mismatch”
Ausente - “gap”
ALINHAMENTO
||||||
|
ALINHAVAD_O
Algoritmo básico de
programação dinâmica
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)
Matrizes de substituição


http://mcb.berkeley.edu/labs/king/blast/docs/matrix
_info.html
PAM
– The rapid generation of mutation data matrices
from protein sequences. Jones DT, Taylor WR,
Thornton JM. Comput Appl Biosci. 1992 Jun;8(3):275-82.
PMID: 1633570
– http://www.bioinformatics.nl/tools/pam.html

BLOSUM
– Amino acid substitution matrices from protein
blocks. Henikoff S, Henikoff JG. Proc Natl Acad Sci U S A.
1992 Nov 15; 89(22): 10915-10919. PMCID: 50453
Matrizes de substituição


Henikoff S. e Henikoff J.G. (1993)
indicam a matriz BLOSUM62 como a
matriz de substituição com melhores
resultados para aplicações gerais no
artigo “Performance evaluation of
amino acid substitution matrices.”
PS: Eles “inventaram” a BLOSUM62...
BLOSUM 62
http://www.icb.ufmg.br/~lbcd/grupo1/tabela1.html Tabela do código dos aminoácidos
A
R
N
D
C
Q
E
G
H
I
L
K
M
F
P
S
T
W
Y
V
A
4
-1
-2
-2
0
-1
-1
0
-2
-1
-1
-1
-1
-2
-1
1
0
-3
-2
0
R
-1
5
0
-2
-3
1
0
-2
0
-3
-2
2
-1
-3
-2
-1
-1
-3
-2
-3
N
-2
0
6
1
-3
0
0
0
1
-3
-3
0
-2
-3
-2
1
0
-4
-2
-3
D
-2
-2
1
6
-3
0
2
-1
-1
-3
-4
-1
-3
-3
-1
0
-1
-4
-3
-3
C
0
-3
-3
-3
9
-3
-4
-3
-3
-1
-1
-3
-1
-2
-3
-1
-1
-2
-2
-1
Q
-1
1
0
0
-3
5
2
-2
0
-3
-2
1
0
-3
-1
0
-1
-2
-1
-2
E
-1
0
0
2
-4
2
5
-2
0
-3
-3
1
-2
-3
-1
0
-1
-3
-2
-2
G
0
-2
0
-1
-3
-2
-2
6
-2
-4
-4
-2
-3
-3
-2
0
-2
-2
-3
-3
H
-2
0
1
-1
-3
0
0
-2
8
-3
-3
-1
-2
-1
-2
-1
-2
-2
2
-3
I
-1
-3
-3
-3
-1
-3
-3
-4
-3
4
2
-3
1
0
-3
-2
-1
-3
-1
3
L
-1
-2
-3
-4
-1
-2
-3
-4
-3
2
4
-2
2
0
-3
-2
-1
-2
-1
1
K
-1
2
0
-1
-3
1
1
-2
-1
-3
-2
5
-1
-3
-1
0
-1
-3
-2
-2
M
-1
-1
-2
-3
-1
0
-2
-3
-2
1
2
-1
5
0
-2
-1
-1
-1
-1
1
F
-2
-3
-3
-3
-2
-3
-3
-3
-1
0
0
-3
0
6
-4
-2
-2
1
3
-1
P
-1
-2
-2
-1
-3
-1
-1
-2
-2
-3
-3
-1
-2
-4
7
-1
-1
-4
-3
-2
S
1
-1
1
0
-1
0
0
0
-1
-2
-2
0
-1
-2
-1
4
1
-3
-2
-2
T
0
-1
0
-1
-1
-1
-1
-2
-2
-1
-1
-1
-1
-2
-1
1
5
-2
-2
0
W
-3
-3
-4
-4
-2
-2
-3
-2
-2
-3
-2
-3
-1
1
-4
-3
-2
11
2
-3
Y
-2
-2
-2
-3
-2
-1
-2
-3
2
-1
-1
-2
-1
3
-3
-2
-2
2
7
-1
V
0
-3
-3
-3
-1
-2
-2
-3
-3
3
1
-2
1
-1
-2
-2
0
-3
-1
4
Algoritmo do BLAST

O algorítimo BLAST é um método de busca heurística que
busca por palavras de comprimento W (por padrão W = 3 no
in blastp) que tenham valor de alinhamento (score) de pelo
menos T quando alinhados com a seqüência consulta de
acordo com a matriz de substituição utilizada. Palavras no
banco de dados com valor igual ou maior à T são extendidas
nas duas direções na tentativa de localizar um alinhamento
ótimo local sem “gaps” ou HSP (high scoring pair) com um
valor (“score”) de pelo menos S ou um E value menor que o
especificado como limite superior. HSPs que estiverem dentro
desses critérios serão reportadas pelo BLAST, desde que seu
número não seja maior que o limite especificado de
descrições ou alinhamtentos a serem reportados.
Algoritmo do BLAST