Algoritmos e Heurísticas
para Seqüenciamento de DNA
Geraldo FERREIRA & Tiago MACAMBIRA
DCC-UFMG
Objetivos
•
•
•
•
•
Apresentação do Ambiente Biológico
Alinhamento Global
Alinhamento Local
Alinhamento Múltiplo
Ferramenta BLAST
Agosto de 2003
Geraldo FERREIRA
Tiago MACAMBIRA
2
Mundo Biológico
•
•
•
•
•
•
Corpo
Célula
Cromossomo
Genoma/Gene
DNA
Bases
Agosto de 2003
Geraldo FERREIRA
Tiago MACAMBIRA
3
Alinhamento Global
• 2 seq. basicamente similares durante todo comprimento
• Tenta casar fim-a-fim uma sequência sobre a outra
A A A G C G G A A G T C A C A G
|
|
.
|
|
.
|
|
|
|
|
|
.
|
|
A A G G C T G A A G T - A T A G
Agosto de 2003
Geraldo FERREIRA
Tiago MACAMBIRA
4
Alinhamento Local
• Segmentos das 2 sequências com bons casamentos
• Não existe a tentativa de forçar o alinhamento
A A A G C G G A A G T C A C A G
. . . . . .
|
|
|
|
|
. . . .
A A G G C T G A A G T - A T A G
Agosto de 2003
Geraldo FERREIRA
Tiago MACAMBIRA
5
Pontuação de Similaridade
• A Similaridade tenta inferir quão forte é a
homologia
• Atribuições: Match=1 , Mismatch=-1, Gap=-2
G
A
|
|
G
A
-
T
C
G
G
A
T
T
A
G
|
|
|
|
.
|
|
|
C
G
G
A
A
T
A
G
S= [9 x 1] + [1 x (-1)] +[1 x (-2)] = 6
Agosto de 2003
Geraldo FERREIRA
Tiago MACAMBIRA
6
Alinhamento Global 1/3
• Calcula a similaridade dos prefixos curtos
• Usa os resultados para o cálculo dos prefixos longos
Agosto de 2003
Geraldo FERREIRA
Tiago MACAMBIRA
7
Alinhamento Global 2/3
• Exemplo (Match=5, Mismatch= - 4, Gap w= -7 )
G C T G GAA G G C AT
GCAGAGCACT
Agosto de 2003
Geraldo FERREIRA
Tiago MACAMBIRA
8
Alinhamento Global 3/3
• Caminho c/ mais altas pontuações = Caminho Ótimo
• Custo para obtenção S[m,n] = O(m.n)
• Custo para construção do caminho = O(m+n)
Agosto de 2003
Geraldo FERREIRA
Tiago MACAMBIRA
9
Alinhamento Local
• Decidir quando um alinhamento local deve ser abandonado.
• Modificar a recorrência para evitar pontuações abaixo de zero.
• Pesquisar pelo S com maior pontuação. Caminhar de volta.
Agosto de 2003
Geraldo FERREIRA
Tiago MACAMBIRA
10
Alinhamento Múltiplo
• Generalização do
problema de alinhamento
de duplas de seqüências
• Geralmente usado com
proteínas
• Insere-se espaços em
várias seqüencias para
torná-las de mesmo
tamanho
• Como definir a qualidade
de um alinhamento?
– Métricas
Agosto de 2003
Geraldo FERREIRA
Tiago MACAMBIRA
11
Alinhamento Múltiplo
• Intuição:
– Estender os algoritmos de alinhamento de
duplas
• Como?
– Função de Pontuação
– Algoritmo de Programação dinâmica
Agosto de 2003
Geraldo FERREIRA
Tiago MACAMBIRA
12
Métrica SP
• Função de Pontuação deve
– Independente da ordem dos Argumentos
– Premiar resíduos iguais ou relacionados
– Penalisar espaços
• Sum-of-Parts
SP(a,b,c,d,) = p(a,b) + p(a,c) + p(a,d) + p(b,c) +
p(b,d) + p(c,d)
Agosto de 2003
Geraldo FERREIRA
Tiago MACAMBIRA
13
Métrica SP e Programação
Dinâmica
• Extensão da matriz
– Complexidade de espaço O(nk)
– Complexidade de Tempo: O(k22knk)
• Alinhamento Múltiplo com a métrica SP é
NP-Completo
• Heurísticas
Agosto de 2003
Geraldo FERREIRA
Tiago MACAMBIRA
14
Alinhamento Estrela
• Heurística para alinhamento
múltiplo
– Construir o múltiplo usando
apenas alinhamento de duplas
– Sem garantias, mas bom na
prática
• Escolhe-se uma seqüência
como centro da estrela
• Alinhamento múltiplo é
construído em torno da estrela
• Complexidade tempo:
O(kn2+k2l)
Agosto de 2003
Geraldo FERREIRA
Tiago MACAMBIRA
15
Busca em Banco de Dados
• Vastos bancos de de seqüências
• Algoritmos tradicionais muito lentos com
as instâncias dadas
• Heurísticas
• BLAST (Basic Local Aligment Search Tool)
Agosto de 2003
Geraldo FERREIRA
Tiago MACAMBIRA
16
BLAST
• Sementes
• MSP (Maximal Segment Pair)
• Funcionamento
– Compila lista de palavras com alta pontuação
– Busca casamentos entre essas palavras e
seqüências no banco de dados
– Estende casamentos para formar MSP
Agosto de 2003
Geraldo FERREIRA
Tiago MACAMBIRA
17
FIM
Agosto de 2003
Geraldo FERREIRA
Tiago MACAMBIRA
18