Bioinformática: Fundamentos y aplicaciones de actualidad
Curso de verano 2005
Revisión de algunos modelos
probabilísticos de evolución genética
(Procesos de Markov
y cadenas de Markov ocultas)
César Sánchez Sellero
Universidad de Santiago de Compostela
1.
Motivación
2.
Probabilidad
3.
Procesos estocásticos
4.
Cadenas de Markov
5.
Cadenas de Markov ocultas
6.
Aplicaciones
Motivación: Modelo para familias de proteínas
d1
d2
d3
d4
i0
i1
i2
i3
i4
m0
m1
m2
m3
m4
m5
Probabilidad
Experimento aleatorio. Es un experimento cuyos resultados posibles son
conocidos de antemano, pero se desconoce cuál de ellos va a ocurrir.
Espacio muestral. Es el conjunto formado por todos los resultados
posibles del experimento aleatorio. Lo denotamos por Ω.
Ejemplo. Lanzar una moneda. Ω={c, +}.
Suceso. Cualquier subconjunto del espacio muestral.
Ejemplo. Lanzar un dado. Ω={1, 2, 3, 4, 5, 6}. A=“que salga par”={2, 4, 6}.
Suceso elemental. Es un suceso unitario. Está constituido por un único elemento.
Decimos que ha ocurrido un suceso cuando se ha obtenido alguno de los
resultados que lo forman.
Suceso seguro. Es el que siempre ocurre, y por tanto, es Ω.
Suceso imposible. Es el que nunca ocurre, y por tanto, es el vacío, Ø.
Unión. Ocurre AUB si ocurre al menos uno de los sucesos A o B.
Intersección. Ocurre A B si ocurren los dos sucesos A y B a la vez.
Complementario. Ocurre Ac si y sólo si no ocurre A.
Diferencia de sucesos. Ocurre A\B si ocurre A pero no ocurre B. A\B=A Bc.
Sucesos incompatibles. A y B son incompatibles sino pueden ocurrir a la
vez. A B = Ø.
Suceso contenido en otro. Siempre que sucede A, sucede también B. A  B.
Definición. Se define la probabilidad como una aplicación que a cada suceso
le asigna un número entre cero y uno ( su probabilidad), y que cumple las
siguientes condiciones:
i.
P(Ω)=1.
ii.
Si A B = Ø entonces P(AUB)=P(A)+P(B).
Propiedades
1. P(Ø)=0.
2. Si A1, A2, …, An son sucesos incompatibles dos a dos, entonces
P(A1, A2, …, An) = P(A1) + P(A2) + … + P(An).
3. P(Ac) = 1 - P(A)
4. Si A  B, entonces P(A) ≤ P(B).
5. Si A y B son dos sucesos cualesquiera, se cumple
P(AUB) = P(A) + P(B) - P(A B)
Asignación de probabilidades
La asignación de probabilidades a veces se deduce de la estructura del
experimento.
Si Ω es finito, en ciertas ocasiones podemos pensar que todos los sucesos
elementales tienen la misma probabilidad (equiprobables).
Esto permite calcular la probabilidad de cualquier otro suceso mediante la
regla de Laplace:
P ( A) 
C asos favorables
C asos posibles
Probabilidad condicionada. Independencia.
P(B/A)
P(A)
0.3
B
0.7
Bc
A
0.6
0.4
P(A B)=P(A).P(B/A)=0.6x0.3=0.18
0.42
0.8
B
0.32
0.2
Bc
0.08
Ac
1.00
Regla del producto
P  A3 A1
P  A 2 A1 
A1
P  A1 
A2 
A3
A2
A3
c
A2c
A1c
P  A1
A2
A3   P  A1  P  A2 A1  P  A3 A1
A2 
Ley de las probabilidades totales
B
A1
Bc
B
A2
P(A1 B)=P(A1).P(B/A1)
P(A2 B)=P(A2).P(B/A2)
Bc
.
.
.
B
An
P(An B)=P(An).P(B/An)
Bc
P(B)
Teorema de Bayes
B
A1
P(A1 B)=P(A1).P(B/A1)
Bc
B
A2
P(A2 B)=P(A2).P(B/A2)
Bc
.
.
.
B
An
P  A1 B  
P  A1
B
P B
P(An B)=P(An).P(B/An)
Bc

P  A1  P  B A1 
P  A1  P  B A1   P  A2  P  B A2  
 P  An  P  B An 
Procesos estocásticos
Espacio de
estados
1
2
3
4
5
6
7
Indice del proceso, t
8
9
10
Cadenas de Markov
Definición. Una cadena de Markov es un proceso estocástico que presenta las
siguientes propiedades:
i.
Es un proceso en tiempo discreto.
ii.
El espacio de estados es discreto.
iii. Dependencia markoviana.
iv. Las probabilidades de transición no dependen de la etapa.
Elementos de una cadena de Markov.
Espacio de estados:
E   E1 , E 2 ,
Matriz de transición:
 p11

p 21
P 


 p s1
Distribución inicial:
P
0

, Es
p1 s 

p2s



p ss 
p12
p 22
ps2
0
0
 p1 , p 2 ,
0
, ps

siendo p ij  P  X t  1  E j X t  E i 
0
siendo p i
 P  X 0  Ei 
Representación de una cadena de Markov
Ejemplo.
E   E1 , E 2 , E 3 
 0

P  0 .2 5

 0

0
0 .2 5
1
1 

0 .5

0 
0.25
0.25
E1
E2
0.5
1
1
E3
Distribución de probabilidad en la etapa t
Por la ley de probabilidades totales, la distribución de probabilidad
en la primera etapa se puede obtener así
P
1 
 P
0
P
Pero esto nos permite pasar también a la segunda etapa, y así
sucesivamente a cualquier etapa, multiplicando por la matriz de
transición tantas veces como etapas haya que recorrer.
P
t 
 P
0
P
t
Tipos de estados
Efímero. Ningún estado conduce a él.
Transitorio. Tras pasar por él, al cabo de cierto número de etapas, la cadena
de Markov ya no regresa a él.
Recurrente. Si no es transitorio, esto es, si tras pasar por él, la cadena de Markov
siempre regresa a él.
Absorbente. Al llegar a él, ya no se sale a ningún otro estado.
Distribución estacionaria y comportamiento límite
Definición. Л es una distribución estacionaria sobre E si Л P= Л .
1. Las distribuciones estacionarias otorgan probabilidad cero a los estados
transitorios.
2. Cada grupo de estados recurrentes intercomunicados tiene una única
distribución estacionaria.
3. Cuando el número de etapas converge a infinito,
P 
S
t
y
P
t 
 P
0
P 
P
t
0
S
4. Si Rt es el número de veces que la cadena pasa por el estado Ei en las t
primeras etapas, cuando t tiende a infinito,
Rt
t

P
0
S
casi seguro.
Estimación de los parámetros de una cadena de Markov
A partir de una realización de la cadena de Markov, se pueden estimar las
probabilidades de transición mediante las siguientes proporciones observadas:
pˆ ij 
N um ero de transiciones observadas de E i a E j
N um ero de transiciones observadas desde E i
Esto presenta limitaciones dependiendo de cómo haya evolucionado la
realización observada. Además, no permite estimar las probabilidades iniciales.
Por estos motivos es conveniente disponer de varias realizaciones de la cadena
de Markov.
Cadenas de Markov ocultas
En lugar de observar los estados de la cadena de Markov, observamos otros
elementos, bajo ciertas probabilidades:
Elementos de una cadena de Markov oculta.
Espacio de estados:
E   E1 , E 2 ,
Matriz de transición:
 p11

p 21
P 


 p s1
, Es
p1 s 

p2s



p ss 
p12
p 22
ps2
A   a1 ,
Alfabeto de símbolos observables:
B   bi  a  
Probabilidades de emisión:
Distribución inicial:
P
0

0
0
 p1 , p 2 ,
0
, ps
siendo p ij  P  X t  1  E j X t  E i 
, am 
siendo bi  a   P  E i em ita el sim bolo a 

0
siendo p i
 P  X 0  Ei 
Tres problemas
Llamemos λ al conjunto de parámetros del modelo de Markov oculto, y
O   O1 ,
, OT

a una realización de la cadena de Markov oculta.
Problema 1. Calcular P ( O / λ ) .
Problema 2. Encontrar la secuencia de estados
X   X 1,
, XT

que mejor se corresponda con la secuencia observada O, bajo el modelo λ .
Problema 3. Estimar los parámetros del modelo. Lo haremos buscando λ que
haga máxima P ( O / λ ) .
Una primera idea
Si supiéramos cuál ha sido la sucesión de estados, entonces
P  O X ,    b x1  O 1   b x 2  O 2 
b xT  O T

La probabilidad de una sucesión de estados es
0
P  X    p x1  p x1 x 2  p x 2 x3
p xT 1 xT
Entonces, por la ley de probabilidades totales
P O   
 PX
  P O X ,  
X


X
0
p x1  p x1 x 2  p x 2 x3
p xT 1 xT  b x1  O1   b x 2  O 2 
b xT  O T

Procedimiento Adelante/Atrás (Inducción)
Definimos las funciones adelante así:
 t  i   P  O1 , O 2 ,
, OT , X t  E i  
Las funciones adelante se pueden calcular por inducción así:
Paso inicial
Inducción
Paso final
0
 1  i   p i  bi  O 1 
 s
 t 1  i      t
 j 1
P O   


j  p ji   b j  O t  1 

s
  i
T
i 1
Definimos las funciones atrás así:
 t  i   P  O t 1 , O t  2 ,
, OT X t  E i ,  
Las funciones atrás se pueden calcular por inducción así:
Paso inicial
Inducción
T i  1
t i 
s

p ij b j  O t  1   t  1  j 
j 1
Paso final
P O   
s
  i
T
i 1
Algoritmo de Viterbi
Buscamos la cadena de estados que mejor se corresponda con la secuencia observada
(problema 2). Formalizamos esto en el objetivo siguiente: m ax P O , X 
X


Definimos las funciones:
t i 
m ax
x1 , x 2 ,
, x t 1
P  x1 , x 2 ,
, x t 1 , x t  E i , O1 , O 2 ,
, Ot  
Estas funciones y los argumentos donde se alcanza el máximo se pueden calcular por
inducción así:
0
Paso inicial
 1  i   p i  bi  O1 
Inducción
 t  i   m ax   t 1  j  p ij   b j  O t 
j 1, , s 
Paso final
P  m ax  T  i 
*
Secuencia de estados
i
 1 i   0
xT  arg m ax  T  i 
*
i
x t   t 1  x t 1 
*
 t  i   arg m ax   t 1  j  p ij 
j  1, , s
*


Estimación de los parámetros del modelo
m ax P  O  
Lo haremos por máxima verosimilitud y aplicaremos un método de tipo EM.

Definimos las funciones:
 t  i , j   P  x t  E i , x t 1  E j O ,  
Se pueden calcular a partir de las funciones adelante y
atrás así:
 t  i, j  
 t  i  p ij b j  O t  1   t  1  j 
P O  
Los parámetros estimados se
actualizan de la siguiente manera:

pˆ i
0
 1 i
T 1
   i, j 
t
Además podemos considerar todas las transiciones que
parten de un estado:
pˆ ij 
t 1
T 1
  i
t
t 1
 t i 
s
T
   i, j 
t
j 1
bˆi  k  

 t i
t :O t  a k
T
  i
t
t 1
Aplicaciones




Modelos para familias de proteínas
Alineamiento de secuencias
Descubrimiento de subfamilias
Modelación de dominios dentro de la
cadena de aminoácidos
Modelo para familias de proteínas
d1
d2
d3
d4
i0
i1
i2
i3
i4
m0
m1
m2
m3
m4
m5
Alineamiento de secuencias
Una vez construido el modelo de Markov oculto y estimados sus parámetros, se
puede emplear el modelo para reconstruir la sucesión de estados más probable
que corresponde a cierta secuencia de aminoácidos.
Dicho de otro modo, a partir de una secuencia de aminoácidos podemos
encontrar cuál es la sucesión de inserciones o supresiones que se han producido
(con mayor probabilidad).
Ejemplo. Secuencias CAEFDDH y CDAEFPDDH. Modelo de longitud 10.
Se ajustan las sucesiones de
estados más probables y resultan
Entonces las dos secuencias se alinean así
m0m1m2m3 m4d5d6m7m8m9m10
C _ A E F_ _ D D H
m0m1i1m2m3 m4d5m6m7m8m9m10
C D A E F_ P D D H
Descubrimiento de subfamilias
Modelo 1
Modelo 2
Inicio
Fin
Modelo k
Modelación de dominios dentro de la cadena de
aminoácidos
Modelo para el dominio
Inicio
IA
m0
mN+1
ID
Fin
Descargar

Diapositiva 1