Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
Figueiredo – 2010
Teoria dos GrafosAula 17
Aula passadaProblema da soma do subconjunto (subset sum)Programação dinâmicaProblema da mochila
Aula de hojeAlinhamento de sequênciasProgramação dinâmicaCaminho mais curto (abordagem via grafos)
Figueiredo – 2010
Sugestões do Google
Como o Google faz isto?realmente sabia o que eu procurava?
por que não sugeriu “esperando” ou “expansão”?
Figueiredo – 2010
Medindo Similaridade Problema: medir “semelhança” entre duas palavras
Idéia: quantidade de modificações para transformar uma palavra em outra
mais modificações, maior diferença
Ex. exparansa e esperado
exparansa
esperado-
Operações de substituição e adição ou remoção (gap)
5 operações
Figueiredo – 2010
Medindo Similaridade Generalização: operações podem ter custos diferentes
ex. adição é mais caro do que substituição
Custo depende da substituiçãoex. trocar vogal por consoante é mais caro do que vogal por vogal
De forma geral, para cada par de letras p, q
pq = custo de substituir p por q
= custo do “gap” (remoção/adição)
Figueiredo – 2010
Exemplo
pq = 1 : quando p , q são vogais
pq
= 2 : caso contrario
= 3
exparansa
esperado-
Custo?2+1+2+2+3 = 10
exparansa
esperança
Custo?2+1+2 = 5
Custo?2+2+2+2+3 = 11
exparansa
expansão-
Google sugere palavra de menor custo (maior similaridade)
Menor custo depende dos pesos
Figueiredo – 2010
Alinhamento de PalavrasProblema: Determinar menor custo entre duas palavras
muitas maneiras de transformar uma palavra na outra
Ex. exparansa e expansão
Custo?2+2+2+2+3 = 11
exparansa
expansão-
Custo?2+3+3+1+3 = 12
Problema do alinhamento entre palavras
exparansa-
expan--são
Figueiredo – 2010
Genoma: Código da VidaGenoma: conjunto de moléculas do DNA de um organismo (gens ou cromossomos)
DNA: longa sequência de apenas 4 substâncias (A,C,G,T)
humano: 6 bilhões, ao todo
Subsequências (gigantes) determinam funcionalidade
ex. resistência a uma determinada toxina, controle do metabolismo, etc.
Figueiredo – 2010
Alinhamento de DNA
Problema: Medir similaridade entre os gens
Objetivo: Identificar gens (parte da sequência do DNA) que são similares
entre indivíduos, entre espécies, etc.
Problema importante e atual da área de Biologia Computacional
de grande interesse na biologia molecular
Figueiredo – 2010
Alinhamento de DNAMedir similaridade entre longas sequências
custo de transformação das sequências
Ex. similaridade entre as sequências ACCCAACCCCAAC e ACACAAACCCCCAC
ACCCAACCCCAAC-
ACACAAACCCCCAC
ACCCAA--CCCCAAC
ACACAAACCCCCA-C
Problema: Encontrar transformação de menor custo (definição de similaridade)
Figueiredo – 2010
EmparelhamentoConsidere duas sequências (de tamanho m e n)
X = x1 x
2 ... x
m
Y = y1 y
2 ... y
n
Emparelhamento M: conjunto de pares ordenados (i, j) tal que cada elemento i ou j ocorre em no máximo 1 par
Exemplo
x1 x
2 x
3 x
4 x
5
y1 y
2 y
3 y
4 y
5 y
6
M = {(1, 1), (2, 4), (3, 2), (5, 6)}
Figueiredo – 2010
AlinhamentoConsidere duas sequências (de tamanho m e n)
X = x1 x
2 ... x
m
Y = y1 y
2 ... y
n
Emparelhamento M é um alinhamento, quando não há cruzamentos
Para todo (i, j) e (i', j') pertencente a M, se i < i', então j < j'
M (slide anterior) é alinhamento?
M = {(1, 1), (2, 4), (3, 2), (5, 6)}
Figueiredo – 2010
Alinhamento
Exemplo: espera e perna
esper-a
--pernaM = {(3, 1), (4, 2), (5, 3), (6, 5)}
-esper-a
pe---rnaM = {(1, 2), (5, 3), (6, 5)}
Emparelhamento (alinhado) define a transformação
Cada emparelhamento tem um custo
Problema: Encontrar emparelhamento que minimiza o custo (ótimo)
Figueiredo – 2010
Alinhamento de SequênciaAbordagem via programação dinâmica
Estudo da solução ótima MM emparelhamento de menor custo
O que podemos dizer sobre o último par (m, n)?
último símbolo das duas sequências
Ou (m,n) pertence a M ou (m,n) não pertence a M
O que podemos afirmar quando (m,n) não pertence a M?
Figueiredo – 2010
Alinhamento de SequênciaSe (m, n) não pertence a M, então ou a posição m de X ou a posição n de Y não aparece em nenhum par
caso contrário, (se as duas aparecem em dois pares) teríamos um cruzamento
Se M é ótimo, então sabemos que(m, n) pertence a M ou
posição m de X não está emparelhada em M ou
posição n de Y não está emparelhada em M
Figueiredo – 2010
Analisando Solução Ótima
OPT(i, j): custo da solução ótima com as respectivas subsequências de X e Y
Variáveis para definição dos subproblemas?
número de caracteres sendo considerados da sequência X e Y (a partir do início)
i : x1
x2 ... x
i -- j : y
1 y
2 ... y
j
Três casos para considerar
1) Se (m, n) pertence a M
Custo do emparelhamento entre xm e y
n (que
pode ser zero) + custo do subproblema ótimo
OPT(m, n) = xm yn
+ OPT(m-1, n-1)
Figueiredo – 2010
Analisando Solução Ótima2) Se posição m de X não está emparelhada
Custo de um gap (da posição m de X) + custo da solução ótima sem a posição m de X
OPT(m, n) = + OPT(m-1, n)
3) Se posição n de Y não está emparelhada
Custo de um gap (da posição n de Y) + custo da solução ótima sem a posição n de Y
OPT(m, n) = + OPT(m, n-1)
Solução ótima considera caso de menor custo
entre as três possibilidades
Figueiredo – 2010
Analisando Solução Ótima
OPT(i, j) = min ( xi yj
+ OPT(i-1, j-1),
+ OPT(i-1, j), + OPT(i, j-1)
Generalizando o argumento para qualquer subsequência de tamanho i e j
Quando emparelhamento (i, j) pertence a solução ótima?
Quando primeiro caso é o mínimo
Figueiredo – 2010
AlgoritmoAlgoritmo para calcular OPT(n, m)?
iterativo, não recursivo (mas utilizando recursão)AlinhamentoOPT(X, Y)
Array A[0,...,m ; 0,...,n]Init A[i,0] = i*, para i = 0,...,mInit A[0,j] = j*, para j = 0,...,nInit A[0,0] = 0
For j = 1, ..., nFor i = 1, ..., m
A[i,j] = min((X[i],Y[j]) + A[i1,j1], + A[i1, j], + A[i, j1])
Retorna A[m,n]
Inicialização: “gap” em todos os caracteres quando a outra sequência é vazia
Figueiredo – 2010
ComplexidadeTempo de execução do algoritmo?
Número de elementos da matriz A
cada elemento da matriz A tem tempo constante O(1)
Complexidade O(m n)
Figueiredo – 2010
Redução para GrafosAlinhamento de sequências pode ser mapeado em problema de grafos
problema de menor caminho
Dado duas sequências X e Y, construir um grafo direcionado G
XY em um grid
Elemento (i, j) do grid corresponde aos índices (i, j) das sequências
Arestas direcionadas apenas entre vizinhos no grid (horizontal, vertical e diagonal)
Pesos correspondem ao custos de gap (horizontal e vertical) ou substituição (diagonal)
Figueiredo – 2010
Construindo o GrafoEx. X = x
1 x
2 x
3 Y = y
1 y
2 y
3 y
4
y1
y2
y3
y4
Mover na horizontal ou vertical, é igual a introduzir um gap
custo Mover na diagonal é igual a emparelhar (i, j)
custo xi yj
x1
x2
x3
0
Figueiredo – 2010
Caminho MínimoSeja c(i, j) o custo mínimo para ir do vértice (0, 0) ao vértice (i, j)
Então, para qualquer (i, j)
c(i, j) = OPT(i, j)custo do caminho mínimo é igual ao custo do emparelhamento ótimo
Prova por indução (e muito intuitiva)
Caminho de custo mínimo determina emparelhamento
c(m,n) é solução para o problema
Figueiredo – 2010
ComplexidadeSolução mais eficiente para o problema?
Número de vértices do grafo
(m+1)(n+1) ~ mn
Número de arestas do grafo
~ 3mn
Complexidade de Dijkstra (caminho mínimo)
O((n + m)log n), onde n é número de vértices e m número de arestas
Logo, com Dijkstra temos O(mn log mn)
Não reduz complexidade (necessariamente)
mas interpretação vem ajudando desenvolver outros algoritmos