8.5: Uso de HMM para alinear secuencias con penalizaciones por hueco afín

Última actualización
Guardar como PDF

Page ID: 54696

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Podemos usar HMM para alinear secuencias con penalizaciones por brecha afín. Recordemos que penalizaciones por brecha afín penaliza más abrir/ iniciar la brecha que extenderla, así la penalización de un hueco de longitud g es r (g) = -d - (g-1) *e, donde d es la penalización para abrir la brecha y e es la penalización para extender una brecha ya abierta.

Buscaremos alinear dos secuencias con la penalización por hueco afín. Se nos dan dos secuencias: X e Y, la matriz de puntuación S (S (xi, yj) = puntaje de coincidencia xi con yj), penalización por apertura de brecha de d y penalización de extensión de hueco de e. Podemos mapear este problema en un problema HMM usando los siguientes estados, probabilidades de transición y probabilidades de emisión.

Estados:

Hay tres estados que involucra: M (emparejando xi con yj), X (alineando xi con un hueco), Y (alineando yj con un hueco). Además, junto a cada transición, hay una actualización de los índices i, j. Siempre que estemos en estado M, (i, j) = (i, j) + (1,1). En estado X, (i, j) = (i, j) + (1,0). En estado Y, (i, j) = (i, j) + (0,1).

Probabilidades de transición:
Hay 7 probabilidades de transición a considerar como se muestra en la figura 6. P (siguiente Estado = M | corriente = M) = S (xi, yj)
P (siguiente Estado = X | corriente = M) = d
P (siguiente Estado = Y | corriente = M) = d
P (siguiente Estado = X | corriente = X) = e
P (siguiente Estado = M | corriente = X) = S (xi, yj)
P (siguiente Estado = Y | corriente = Y) = e
P (siguiente Estado = M | corriente = Y) = S (xi, yj)

También podemos guardar las probabilidades de transición en una matriz de transición A = [aij], donde aij = P (siguiente Estado = j | actual = i) y$\sum_{j}$ JaiJ = 1

Probabilidades de emisión:
Las probabilidades de emisión son:
Del estado M: p _xiyi = p (x _i alineado a y _j)

Del estado X: q _xi = p (x _i alineado al hueco)

Del estado Y: q _yi = p (yjalineado al hueco)

Ejemplo:
X = 'VLSPADK'

Y = 'HLAESK'
La alineación generada por el modelo es: MMXXMYM
Que corresponde a:
X = 'VLSPAD K'
Y = 'HL_ _AESK'

¿Sabías?

Para fines de clasificación, la decodificación posterior 'path' es más informativa que la ruta Viterbi ya que es una medida más refinada de la cual estados ocultos generaron x Sin embargo, puede dar una secuencia no válida de estados, por ejemplo, cuando no todas las transiciones j $->$ k pueden ser posibles, podría tener state (i) = j y state (i +1) =k