Alinhamento de Cadeias de DNA
COMPARAÇÃO
DE SEQÜÊNCIAS
Katia Guimarães
Montagem de Fragmentos de DNA
[email protected]
2
Montagem de Fragmentos de DNA
[email protected]
3
Montagem de Fragmentos de DNA
[email protected]
4
Programação Dinâmica
Metodologia para resolver problemas que consiste
na construção de uma tabela contendo soluções de
subproblemas de tamanho crescente.
Exemplo clássico: Fatorial
[email protected]
5
Fatorial
Abordagem Recursiva
function fatorial (n:integer):integer
if n > 1 then fatorial:=n * fatorial(n-1)
else fatorial:= 1
Implicações desta abordagem em termos de custo?
[email protected]
6
Fatorial - Abordagem Recursiva
function fat (n:integer):integer
if n > 1 then fat := n * fat (n-1)
else fat := 1
Muitas chamadas recursivas desnecessárias:
Fat(10)
Fat(9)
Fat(8)
[email protected]
...
Fat(1)
7
Fatorial - Abordagem Iterativa
function fat (n:integer):integer
i := 1; fat := 1;
while i < n do {
i := i+1;
fat := fat * i
}
1
2
6
24 120 720
[email protected]
...
8
Fibonacci - Abordagem Recursiva
Function fib (integer n): integer
if (n ≤ 2)
then return (1)
else return (fib(n-1) + fib(n-2))
Implicações desta abordagem em termos de custo?
[email protected]
9
Fibonacci - Abordagem Recursiva
/
F(4)
F(5)
/
\
F(3)
F(2)
/
\
F(2) F(1)
\
F(3)
/ \
F(2) F(1)
[email protected]
10
Fibonacci - Abordagem Iterativa
Function fib (integer n)
int a = 1, b = 1, c;
for (int i = 3; i ≤ n; i++)
{ c := a + b; a := b; b := c }
return (b);
1
1
2
3
5
[email protected]
8
11 ...
11
Alinhamento de Seqüências
Problema: Dadas duas seqüências
sobre o mesmo alfabeto, com
aproximadamente o mesmo
tamanho, encontrar o melhor
alinhamento entre estas duas
seqüências.
[email protected]
12
Alinhamento de Seqüências
O melhor alinhamento entre duas
seqüências:
GA- C G GATTAG
G A T C G G A AT A G
é dado por um score que é a soma
dos valores associados a cada posição,
de acordo com o critério pré-definido.
[email protected]
13
Alinhamento de Seqüências
O score que é a soma dos valores
associados a cada posição, de acordo
com o grau de similaridade entre os
elementos correspondentes.
Ex: match +1
mismatch -1
space
-2
[email protected]
14
Score de um Alinhamento
Ex: match +1
mismatch -1
space
-2
(good)
(bad)
(worse)
GA- C G GATTAG
G A T C G G A AT A G
score = 9 ·1+ 1·(-1) + 1·(-2) = 6
[email protected]
15
Programação Dinâmica
O número de possíveis alinhamentos é
exponencial no tamanho das seqüências.
(Logo, não podemos experimentar todos.)
Abordagem alternativa: Sejam s e t
duas seqüências, com |s|=m e |t|=n,
construir uma matriz (m+1) x (n+1),
onde M(i, j) contém a similaridade
entre s[1..i] e t[1..j].
[email protected]
16
Programação Dinâmica
Esta é uma abordagem indutiva, onde são
definidos os scores para as seqüências
menores, e a partir dessas, novos scores são
computados os scores de cadeias maiores.
Ex: G A - C A T T G
G A T C A AT G
  G custa -2;   GA custa -4;
G  G custa +1; G  GA custa -1;
[email protected]
17
Programação Dinâmica
1a. linha e1a. coluna fáceis de computar:
 G A C A T T G

G
A
T
C
A
A
T
G
0
-2
-4
-6
-8
-10
-12
-14
-16
-2
-4 -6 -8 -10 -12 -14
[email protected]
18
Programação Dinâmica
Dado que eu sei computar os scores dos
melhores alinhamentos entre prefixos de
s e t com tamanhos menores que i e j,
respectivamente, como eu posso calcular o
melhor alinhamento de s[1..i] com t[1..j]?
[email protected]
19
Programação Dinâmica
O score do melhor alinhamento será
calculado em função do último passo de
uma transformação de s[1..i] em t[1..j].
Um passo pode ser
I (inserção), R (remoção),
S (substituição) ou M (match)
[email protected]
20
Programação Dinâmica
1. Se do último passo for I (inserção):
Ex: G A G C A T T C
G A - C AAT C G
Solução: Alinhe s[1..i] com t[1..j-1]
e case um espaço com t[j].
1 .................................. i
s: G A G C A T T C
t: G A - C A A T C G
1 ................................ j-1 j
[email protected]
21
Programação Dinâmica
2. Se do último passo for M (match)
ou S (substituição):
Solução: Alinhe s[1..i-1] com t[1..j-1]
e case s[i] com t[j].
1 ........................... i-1 i
s: G A G C A T T C
t: G A - C A A T C
1 ........................... j-1 j
[email protected]
22
Programação Dinâmica
3. Se do último passo for R (remoção):
Solução: Alinhe s[1..i-1] com t[1..j]
e case s[i] com um espaço.
1 ................................. i-1 i
s: G A G C A T T C G
t: G A - C A A T C
1 ........................... j-1 j
[email protected]
23
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)
[email protected]
24