Projeto e Análise de Algoritmos
Aula 08 – Maior Subsequência Comum (LCS)
Edirlei Soares de Lima
<edirlei@iprj.uerj.br>
Problema
•
•
Subsequência: sequência de caracteres não
necessariamente contínuos, retirados de uma cadeia
em ordem.
–
Exemplo: AAAG é subsequência da cadeia CGATAATTGAGA
Problema: Dadas duas sequências X = {x1, x2, . . . , xm}
e Y = {y1, y2, . . . , yn}, encontrar uma subsequência de
maior tamanho (LCS(X, Y))
Problema
•
•
Problema: Dadas duas sequências X = {x1, x2, . . . , xm}
e Y = {y1, y2, . . . , yn}, encontrar uma subsequência de
maior tamanho (LCS(X, Y))
Exemplo:
–
X = {A, B, C, B, D, A, B}
–
Y = {B, D, C, A, B, A}
–
LCS(X, Y) = {B, C, B, A} ou {B, D, A, B}
Problema
•
Exemplo de Aplicação: análise do DNA de dois ou
mais organismos distintos.
–
Um DNA é composto por uma sequência de moléculas,
chamadas de bases:
•
Adenina (A); Timina (T); Citosina (C); Guanina (G).
–
–
Exemplo: ACGGGTAGTCGCAA
Computacionalmente, um DNA pode ser visto como um
vetor de caracteres, com o alfabeto {A, T, G, C}
Problema
•
•
Dado os DNAs de dois organismos:
–
S1 = ACCGTGGAAAAGGTTAAGGCCAGGATTTAACCGCGGGC
–
S2 = ACCGCGGTTTAATCCGGATAGGTTGAAATGGTTGAAAC
É possível questionar:
–
–
–
Quão semelhantes são estes dois organismos?
Estes organismos são da mesma espécie?
Um destes organismos é ancestral do outro organismo?
•
As respostas vão depender de semelhanças.
Como Resolver?
•
•
Problema: Dadas duas sequências X = {x1, x2, . . . , xm}
e Y = {y1, y2, . . . , yn}, encontrar uma subsequência de
maior tamanho (LCS(X, Y))
Exemplo:
–
X = {A, B, C, B, D, A, B}
–
Y = {B, D, C, A, B, A}
–
LCS(X, Y) = {B, C, B, A} ou {B, D, A, B}
LCS – Força Bruta
•
•
Algoritmo: Enumera-se todas as possíveis
subsequências de X. Checa-se se cada uma destas
subsequências também é subsequências de Y,
guardando a de maior comprimento.
Complexidade?
m
–
–
–
Existem 2 subsequências diferentes de X;
Tempo linear para verificar se a subsequência de X está em Y;
O(2m n) = O(2m) → INEFICIENTE!
LCS – Força Bruta
•
Outras soluções?
LCS – Programação Dinâmica
•
•
Solução: Programação Dinâmica!
Ideia: quebrar o problema em subproblemas, com
estrutura semelhante ao problema geral. Armazena-
se a solução para cada um desses subproblemas para
utiliza-las para a solução geral.
LCS – Programação Dinâmica
•
•
Dada uma sequência X = {x1, x2, . . . , xm}, define-se o
i-ésimo prefixo de X, para i = 0, 1, 2, . . . , m como Xi =
{
x1, x2, . . . , xi}
Por exemplo, dada a sequência X = {A, B, C, B,D, A, B}
–
–
–
X0 = {}
X3 = {A, B, C}
X4 = {A, B, C, B}
LCS – Programação Dinâmica
•
Uma LCS(X, Y) pode ser obtida recurivamente da
seguinte forma:
–
–
Se xm = yn deve-se procurar uma LCS(Xm−1, Yn−1) e depois
acrescentar xm ou yn.
Se xm ≠ yn, então deve-se resolver 2 subproblemas:
•
•
•
Encontrar uma LCS(Xm−1, Yn);
Encontrar uma LCS(Xm, Yn−1);
Sendo a LCS mais longa destas duas.
LCS – Programação Dinâmica
•
Defina c(i, j) como o tamanho da LCS(Xi, Yj):
0
ꢄꢅ ꢁ = 0 ꢆꢇ ꢂ = 0
ꢃ ꢁ − 1, ꢂ − 1 + 1
ꢁ, ꢂ = ቐ
max ꢀ ꢁ − 1, ꢂ , ꢀ ꢁ, ꢂ − 1
ꢄꢅ ꢁ = ꢂ
ꢄꢅ ꢁ ≠ ꢂ
ꢀ
LCS – Programação Dinâmica
•
Ideia do Algoritmo:
–
Considere duas sequências como entrada, X = {x1, x2, . . . ,
xm} e Y = {y1, y2, . . . , yn};
–
Os valore c(i, j) são armazenados em uma tabela c[0..m,
0
..n], onde os valores são computados linha a linha,
esquerda para direita;
–
Também há uma tabela b[1..m, 1..n] tal que são
armazenados as entradas para a escolha da solução ótima
dos subproblemas quando está se computando c(i , j).
LCS – Exemplo
•
X=BDCABA e Y=ABCBDAB
LCS – Exemplo
•
X=BDCABA e Y=ABCBDAB
LCS – Algoritmo
. LCS(X, m, Y, n)
1
2
3
4
5
6
7
8
9
1
1
1
1
1
1
1
1
. para i ← 0 até m faça
. c[i,0] ← 0
O(mn)
. para i ← 0 até n faça
. c[0,i] ← 0
. para i ← 1 até m faça
. para j ← 1 até n faça
.
se Xi == Yi então
.
c[i,j] = c[i – 1, j – 1] + 1
b[i,j] = "↖"
0.
1. senão se c[i – 1, j] ≥ c[i, j – 1] então
2.
2.
c[i,j] = c[i – 1, j]
b[i,j] = "↑"
4. senão
5.
6.
c[i,j] = c[i, j - 1]
b[i,j] = "←"
7. retorna c, b
LCS – Algoritmo
•
Algoritmo para imprimir a LCS na ordem correta:
1
2
3
4
5
6
7
8
9
1
. PRINT-LCS(b, X, i, j)
. se i == 0 ou j == 0 então
. retorna
. se b[i, j] == "↖" então
. PRINT-LCS(b, X, i – 1, j – 1)
. escreva Xi
. senão se b[i, j] == "↑" então
. PRINT-LCS(b, X, i – 1, j)
. senão
0. PRINT-LCS(b, X, i, j - 1)
Exercício
1
) A maior subsequência comum entre DCCFDEBDBCDF
e CDFFAADBFFFD é DFDBD. Verdadeiro ou Falso?
Justifique sua resposta construindo as matrizes geradas
pelo algoritmo para encontrar a maior subsequência
comum baseado em programação dinâmica.
Exercícios
Lista de Exercícios 08 – Maior Subsequência
Comum
http://www.inf.puc-rio.br/~elima/paa/
Leitura Complementar
•
•
Halim e Halim. Competitive Programming,
3
rd Edition, 2003.
Capítulo 6: String Processing