Intr. à Biologia Computacional
ALINHAMENTOS ÓTIMOS
GLOBAIS
Programação Dinâmica
M (i, j) =
max
M (i, j-1) - 2
(último passo = I)
M (i-1, j-1) + p(i,j) (último passo = S/M)
M (i-1, j) - 2
(último passo =R)
onde p(i,j) = +1
-1
set/00
se s[i] = t[j] (M)
se s[i]  t[j] (S)
[email protected]
2
Computando a Matriz M
i-1, j-1
i-1, j
-1 +1
S M -2 R
i, j-1
set/00
-2
I
i, j
[email protected]
3
Computando a Matriz M
A
G
C
0
-2
-4
-6
A
-2
1
-1
-3
A
-4
-1
0
-2
A
-6
-3
-2
-1
C
-8
-5
-4
-1
set/00
[email protected]
4
Algoritmo M
m  |s|; n  |t|;
for i  0 to m do M[i, 0]  i · g custo rem.
for j  0 to n do M[0, j]  j · g custo ins.
for i  1 to m do
for j  1 to n do
M[i, j]  max  M [i, j-1] + g;
M [i-1, j-1] + p(i,j); M [i-1, j] + g 
return (M[m, n] )
set/00
[email protected]
5
Construindo Alinhamentos
Vamos começar na entrada [m, n] da
matriz M, e seguir as setas até chegar
na entrada [0, 0].
1. Se a seta saindo de [i, j] é horizontal,
então teremos uma coluna com um
espaço em s casado com t[j].
Ex: M[1, 2]:
s: A -
t: A G
set/00
[email protected]
6
Construindo Alinhamentos
2. Se a seta saindo de [i, j] é vertical,
então teremos uma coluna com
s[i] casado com um espaço em t.
Ex: M[3, 1]:
s: A A A
t: A -
set/00
[email protected]
-
7
Construindo Alinhamentos
3. Se a seta saindo de [i, j] é diagonal,
então teremos uma coluna com
s[i] alinhado com t[j] (quer sejam
idênticos ou não).
Ex: M[3, 3]:
s: A A A
t: A G C
set/00
[email protected]
8
Algoritmo Align (m, n, len, M)
Entrada: m = |s|, n = |t|, matriz M
Saída: len, o comprimento da
seqüência de alinhamento, dada
pelos vetores align-s e align-t,
que contêm símbolos e espaços.
Note que max(|s|, |t|)  len  m + n.
set/00
[email protected]
9
Algoritmo Align (m, n, len, M)
if i = 0 and j = 0 then len  0
else if i  0 and M[i, j] = M[i-1, j] + g
then /* símbolo de s com ´-` */
Align (i-1, j, len, M);
len  len + 1;
align-s[len]  s[i]
align-t[len]  ´-`
else
set/00
[email protected]
10
Algoritmo Align (m, n, len, M)
if ( i  0 and j  0 and
M[i, j] = M[i-1, j-1] + p(i, j) )
then /* alinha s[i] com t[j] */
Align (i-1, j-1, len, M);
len  len + 1;
align-s[len]  s[i]
align-t[len]  t[j] 
else
set/00
[email protected]
11
Algoritmo Align (m, n, len, M)
/* caso: j > 0 e M[i, j] = M[i, j-1] + g */
/* alinha t[j] com espaço*/
Align (i, j-1, len, M);

set/00
len  len + 1;
align-s[len]  ´-`
align-t[len]  t[j] 
[email protected]
12
Algoritmo Align
Observe que há em geral diversas
escolhas para um alinhamento ótimo.
O algoritmo dado dá preferência aos
passos na ordem:
1. Vertical (R)
2. Diagonal (S/M)
3. Horizontal (I)
set/00
[email protected]
13
Algoritmo Align
Se s = ATAT e t = TATA, obtemos:
Align-s = - A T A T
Align-t = T A T A Se s = AA e t = AAAA, obtemos:
Align-s = - - A A
Align-t = A A A A
(Há outros 5 alinhamentos ótimos)
set/00
[email protected]
14
Complexidade dos Algoritmos
Algoritmo M:
O(m . n )
Algoritmo Align:
set/00
O(m + n )
[email protected]
15