Alineación de secuencias
Alineación de secuencias
Análisis y Diseño de Algoritmos
Análisis y Diseño de Algoritmos
Aplicaciones
Aplicaciones
Aplicaciones
Aplicaciones
Bioinformática
Bioinformática: :
Alineación de secuencias de ADN
Alineación de secuencias
de ADN
Ingeniería del Software:
Ingeniería del Software:
Detección de clones (fragmentos de código duplicado)
Detección de
clones (fragmentos de código duplicado)
Procesamiento del lenguaje natural:
Procesamiento del lenguaje natural:
Reconocimiento de voz, correctores ortográficos…
Reconocimiento de voz, correctores ortográficos…
11
Alineación de secuencias
Alineación de secuencias
Problema
Problema
Dadas dos secuencias, X = (x1 x2 … xm) e Y = (y1 y2 … yn),
encontrar la forma de alinearlas con un coste mínimo.
¿Cómo medimos ese coste?
¿Cómo medimos ese coste?
δδ [g[gap penalty],
ap penalty], cuando
cuando en en unauna cadena
cadena no no aparece
aparece un un
símbolo
símbolo queque sísí estáestá en la
ααααααααpqpq [mismatch penalty],
símbolo p p peropero en la
el el símbolo
en la otraotra..
[mismatch penalty], cuando
cuando en la
cadena X X aparece
aparece
en la cadena
cadena Y Y aparece
en la cadena
aparece q.q.
Alineación de secuencias
Alineación de secuencias
Ejemplos
Ejemplos
C
C
T
G A C C T A C C T
T G A C T A C A T
C
αTC + αGT + αAG + 2αCA
- C
T G A C C T A C C T
C
C
T G A C
-
T A C A T
2δ + αCA
22
33
Alineación de secuencias
Alineación de secuencias
Formalización
Formalización
UnaUna alineación
conjunto de pares (
alineación M M eses un un conjunto
cada
de los elementos
cada unouno de los
en un par y no se produce ningún
en un par y no se produce
en un par y no se produce
en un par y no se produce ningún
Los pares (xxii,y,yjj) y (
) y (xxi’i’,y,yjj’’) se
) se cruzan
de pares (xxii,y,yjj) ) taltal queque
elementos xxii e e yyjj aparece
como mucho
aparece como
mucho
ningún cruce
ningún cruce
cruce..
cruce..
cruzan sisi ii<<ii’ ’ peropero j>j’.
j>j’.
Los pares (
El El coste
coste de la
de la alineación
alineación M, M, porpor tanto
tanto, , viene
viene dado
dado porpor::
coste
(
M
=
)
∑
α
∈
M
+
j
yx
i
∑∑
+
δ
δ
,
)
(
yx
i
443442143421
Mx
i
My
j
∉
j
∉
errores
huecos
Alineación de secuencias
Alineación de secuencias
Ejemplo
Ejemplo
CTACCG vs. TACATG
CTACCG vs. TACATG
x2
x4
x3
x1
x6
C T A C C - G
C T A C C - G
x5
- T A C A T G
y6
y4
y1
y2
y3
y5
Alineación
Alineación M = { (x
M = { (x22,y,y11), (x
), (x33,y,y22), (x
), (x44,y,y33), (x
), (x55,y,y44), (x
), (x66,y,y66) }) }
Coste
Coste de la
de la alineación
alineación: : coste
coste(M) =
(M) = 22δδ + + ααCACA
44
55
Definición recursiva
Definición recursiva
OPT(i, j): Coste mínimo de alineación de las secuencias
Xi=(x1 x2 … xi) e Yj=(y1 y2 … yj).
CasoCaso 1: 1: ((xxii,y,yjj) ) estáestá en la
en la mejormejor alineación
alineación MMOPTOPT
Hay que pagar el coste de emparejar xi con yj, a lo
Hay que pagar el coste de emparejar xi con yj, a lo
que habrá que añadir el coste de alinear las
secuencias Xi-1=(x1 x2 … xi-1) e Yj-1=(y1 y2 … yj-1).
CasoCaso 2a:
2a: MMOPTOPT dejadeja xxii sin sin emparejar
emparejar
Hay que pagar una penalización δδ másmás el el coste
alinear
alinear laslas cadenas
cadenas Xi-1=( x1 x2 … xi-1) e Yj=(y1 y2 … yj).
coste de de
CasoCaso 2b2b: M: MOPTOPT dejadeja yyjj sin sin emparejar
emparejar
Penalización δδ másmás el el coste
Xi=( x1 x2 … xi) e Yj-1=(y1 y2 … yj-1).
coste de de alinear
alinear laslas cadenas
cadenas
66
Definición recursiva
Definición recursiva
OPT(i, j): Coste mínimo de alineación de las secuencias
Xi=(x1 x2 … xi) e Yj=(y1 y2 … yj).
OPT
),(
ji
=
δj
α
α
δ
min
δ
i yx
+
+
δ
i
+
+
OPT
(
i
−
−
,1
j
−
−
)1
j
OPT
(
i
−
OPT
,(
ji
),1
j
−
)1
0i si
=
en
otro
caso
0j si
=
77
Implementación
Implementación
Algoritmo basado en programación dinámica
SequenceAlignmentDP
SequenceAlignmentDP ( X( X, Y,
, Y, δδδδδδδδ, , αααααααα) )
{{
}}
forfor ii = 0 to
= 0 to X.length
X.length
M[0, ii] = ] = ii**δδδδδδδδ;;
M[0, ii] = ] = ii**δδδδδδδδ;;
M[0,
M[0,
forfor j = 0 to
j = 0 to Y.length
Y.length
M[j, 0] = j*j*δδδδδδδδ;;
M[j, 0] =
forfor ii = 1 to
= 1 to X.length
X.length
forfor j = 1 to
M[M[ii, j] =
, j] = min (
Y.length
j = 1 to Y.length
min ( αααααααα[X[[X[ii]][Y[j]]
δδδδδδδδ + + M[iM[i--1][j1][j],],
δδδδδδδδ + + M[M[ii][j][j--1]);1]);
]][Y[j]] + + M[iM[i--1][j1][j--11],],
return
return M[M[X.length
X.length][][Y.length
Y.length];];
88
Implementación
Implementación
Algoritmo basado en programación dinámica
Eficiencia
Eficiencia
Tiempo:
Espacio:
Espacio:
ΘΘ(|X||Y|)
ΘΘ(|X||Y|)
ΘΘ(|X||Y|)
Aplicaciones
Aplicaciones
Reconocimiento de voz con DTW, |X|<10, |Y|<100, OK.
Biología computacional: |X|=|Y|=100000
1010 operaciones, OK
Array con 1010 entradas > 10 GB !!!
99
Optimización
Optimización
¿Podemos evitar que nuestro algoritmo
sea cuadrático con respecto al espacio de
almacenamiento que requiere?
Es fácil si sólo nos interesa el coste de la alineación:
Calculamos
Calculamos el valor OPT(
el valor OPT(ii,·) a
,·) a partir
partir de OPT(i
de OPT(i--1,·).1,·).
Pero ya no podremos alinear las secuencias,
ya que no disponemos de la matriz M…
Optimización
Optimización
¿Podemos obtener la alineación óptima
de dos secuencias con un algoritmo de orden
cuadrático en tiempo pero lineal en espacio?
Sí, si combinamos nuestro algoritmo basado en
programación dinámica con la técnica “divide y
vencerás”. [[Hirschberg 1975
Hirschberg 1975].].
1010
1111
Alineación de secuencias
Alineación de secuencias
Sea f(i,j) el camino más corto de (0,0) a (i,j).
Observación: f(i,j) = OPT(i,j), m=|X|, n=|Y|
ε
ε
0,0
x1
x2
x3
y1
y2
y3
y4
y5
y6
αxi y j
δ
δ
i,j
m,n
1212
Alineación de secuencias
Alineación de secuencias
“Forward alignment”: Podemos calcular f(·,j)
para cualquier j en tiempo O(mn) y espacio O(m+n).
ε
ε
0,0
x1
x2
x3
y1
y2
y3
j
y4
y5
y6
i,j
m,n
1313
Alineación de secuencias
Alineación de secuencias
Sea g(i,j) el camino más corto de (m,n) a (i,j):
Se puede calcular invirtiendo los arcos del grafo anterior…
ε
ε
0,0
x1
x2
x3
y1
y2
y3
y4
y5
y6
δ
αxi y j
i,j
δ
m,n
1414
Alineación de secuencias
Alineación de secuencias
Backward alignment: Podemos calcular g(·,j)
para cualquier j en tiempo O(mn) y espacio O(m+n).
ε
ε
0,0
x1
x2
x3
y1
y2
j
y3
y4
y5
y6
i,j
m,n
1515
Alineación de secuencias
Alineación de secuencias
El coste del camino mínimo
que pasa por (i,j) es f(i,j) + g(i,j)
ε
ε
0,0
x1
x2
x3
y1
y2
y3
y4
y5
y6
i,j
m,n
1616
Alineación de secuencias
Alineación de secuencias
Sea q el índice que minimiza f(qf(q, n/2) + g(q, n/2
El camino más corto de (0,0) a (m,n) pasa por (q,n/2).
, n/2) + g(q, n/2)):
ε
ε
0,0
x1
x2
x3
y1
y2
y3
y4
y5
y6
i,j
n/2
q
m,n
1717
Algoritmo “divide y vencerás”
Algoritmo “divide y vencerás”
1. Encontrar el índice q que minimiza f(f(q,nq,n/2)+g(
usando programación dinámica: Alinear xxqq con
con yynn/2/2
/2)+g(q,nq,n/2)/2)
ε
ε
0,0
x1
x2
x3
y1
y2
y3
y4
y5
y6
i,j
n/2
q
m,n
1818
Algoritmo “divide y vencerás”
Algoritmo “divide y vencerás”
2. Calcular recursivamente la mejor alineación de los
segmentos a la izquierda y a la derecha de xxqq e e yynn/2/2.
ε
ε
0,0
x1
x2
x3
y1
y2
y3
y4
y5
y6
i,j
n/2
q
m,n
1919
Algoritmo “divide y vencerás”
Algoritmo “divide y vencerás”
Eficiencia del algoritmo “divide y vencerás”
Sea T(m,n) el tiempo requerido por el algoritmo
para alinear dos secuencias de longitud m y n:
nmT
(2 ),
nmT
(
,
≤
)2/
+
mnO
(
)
⇒
mnOnmT
∈
),
(
(
log
n
)
Este análisis no es preciso porque
los subproblemas no son de tamaño (m,n/2),
sino de tamaño (q, n/2) y (m-q, n/2).
2020
Algoritmo “divide y vencerás”
Algoritmo “divide y vencerás”
Eficiencia del algoritmo “divide y vencerás”
En En realidad
Tiempo
realidad, T(
Tiempo O(O(mnmn) en
, T(m,nm,n) ) eses O(O(mnmn))
) en calcular
calcular f(f( •, n/2) y g (
•, n/2) y g ( •, n/2)
•, n/2) parapara descubrir
descubrir q.q.
T(q, n/2) + T(m
T(q, n/2) + T(m
T(q, n/2) + T(m -- q, n/2)
T(q, n/2) + T(m -- q, n/2)
q, n/2) parapara laslas llamadas
q, n/2) parapara laslas llamadas
recursivas::
recursivas::
llamadas recursivas
llamadas recursivas
Demostración por inducción sobre n
Casos
Casos base:
base:
m=2 ó n=2
m=2 ó n=2. .
Hipótesis inductiva
Hipótesis
T(mT(m, n)
, n) ≤≤ 2cmn.
2cmn.
inductiva: :
T(m, 2) ≤ cm
T(2, n) ≤ cn
T(m, n) ≤ cmn + T (q, n /2) + T(m − q, n /2)
),
nmT
(
≤
≤
=
=
+
nqmT
(
,
nqT
,(
)2/
+
2
(22/
cqn
nqmc
+
−
cmn
cqn
)
cqn
cmn
−
−
+
)2/
+
2/
+
cmn
cmn
2121
2
cmn
Alineación de secuencias
Alineación de secuencias
Algoritmo
Tiempo
Espacio
Resultado
Programación
dinámica
Forward
alignment
Backward
alignment
Divide y
vencerás
O(mn)
O(mn)
Coste y alineación
O(mn)
O(m+n)
O(mn)
O(m+n)
Coste
Coste
O(mn)
O(m+n)
Coste y alineación
2222
Crear cuenta
Comentarios de: Análisis y Diseño de Algoritmos - Alineación de secuencias (0)
No hay comentarios