Bioinformática

Algoritmo de Ukkonen

algoritmo de Ukkonen es un algoritmo on-line, con tiempo de computación lineal, para construir un árbol de sufijos de una cadena ${\displaystyle S}$. Este algoritmo fue propuesto por Esko Ukkonen en 1995.

Anteriormente existían dos algoritmos capaces de construir el árbol de sufijos de una cadena ${\displaystyle S}$ en tiempo lineal, estos son el algoritmo de Weiner (1973) y el algoritmo de McCreight (1976). Pero el algoritmo de Ukkonen se destaca por ser más sencillo y por tener la característica de ser on-line.

Explicación del Algoritmo

Para explicar el algoritmo de Ukkonen partiremos de una implementación ingenua de este algoritmo que es ${\displaystyle O(n^{3})}$ a la cual se le hacen sucesivas mejoras hasta obtener el ${\displaystyle O(n)}$.

Sea ${\displaystyle Ti}$ el árbol de sufijos implícito de la cadena ${\displaystyle S[1..i]}$, con ${\displaystyle i}$ desde ${\displaystyle 1}$ hasta ${\displaystyle n}$, el algoritmo de Ukkonen aplicado a la cadena ${\displaystyle S\$}$ de longitud ${\displaystyle n}$, construye sucesivamente ${\displaystyle T1,T2,...,Tn}$. La ejecución del algoritmo de Ukkonen se divide en ${\displaystyle n}$ fases, en la fase ${\displaystyle i+1}$ se construye ${\displaystyle Ti+1}$ modificando ${\displaystyle Ti}$, como el último carácter de ${\displaystyle S}$ es ${\displaystyle \$}$ se cumple que ${\displaystyle Tn}$ es el árbol de sufijos de ${\displaystyle S}$.

Cada fase ${\displaystyle i+1}$ es a su vez dividida en ${\displaystyle i+1}$ extensiones. En la extensión ${\displaystyle j}$-ésima de la fase ${\displaystyle i+1}$ se busca el final del camino desde la raíz etiquetado con la subcadena ${\displaystyle S[j...i]}$ y se "extiende" dicho camino con el carácter ${\displaystyle S[i+1]}$.

Reglas de extensión

A continuación se especifica cómo se realizan las extensiones.

Sea ${\displaystyle S[j..i]=a}$ un sufijo de ${\displaystyle S[1..i]}$. En la extensión ${\displaystyle j}$, el algoritmo encuentra el final de ${\displaystyle a}$ y lo extiende con el carácter ${\displaystyle c=S[i+1]}$ de acuerdo a una de las siguientes reglas:

Regla 1: (Extensión en una hoja)

El camino de ${\displaystyle a}$ termina en una hoja. El carácter ${\displaystyle c}$ es añadido al final de la etiqueta de la arista incidente en dicha hoja.

Regla 2: (Extensión en una arista o nodo interno)

El camino de ${\displaystyle a}$ no termina en una hoja, pero ningún camino desde el final de ${\displaystyle a}$ inicia con el carácter ${\displaystyle c}$. En este caso una nueva arista etiquetada con ${\displaystyle c}$ es creada desde el final de ${\displaystyle a}$, dicha arista incide en una nueva hoja etiquetada con ${\displaystyle j}$. Si ${\displaystyle a}$ termina en el interior de una arista, debe crearse además un nuevo nodo que corte dicha arista en el final de ${\displaystyle a}$.

Regla 3: (El carácter c ya aparece, no hay que hacer nada) Algún camino desde el final de ${\displaystyle a}$ inicia con el carácter ${\displaystyle c}$. No es necesario hacer nada.

Suffix links

Definición: Sea un ${\displaystyle v}$ nodo interno con etiqueta ${\displaystyle xa}$ donde ${\displaystyle x}$ denota un carácter y ${\displaystyle a}$ denota un string posiblemente vacío, si existe otro nodo ${\displaystyle s(v)}$ con etiqueta ${\displaystyle a}$, entonces un puntero de ${\displaystyle v}$ a ${\displaystyle s(v)}$ es llamado un suffix link y se denota ${\displaystyle (v,s(v))}$.

Obsérvese que la definición no tiene sentido cuando ${\displaystyle v}$ es la raíz, pues esta no está etiquetada con una cadena de la forma ${\displaystyle xa}$.

Lema: Si al final de una fase, la cadena ${\displaystyle xa}$ pertenece al árbol, entonces la cadena ${\displaystyle a}$ también pertenece.

Demostración: Si ${\displaystyle xa}$ se insertó en la extensión ${\displaystyle j}$ de alguna fase ${\displaystyle i}$, en la extensión ${\displaystyle j+1}$ de dicha fase se insertó ${\displaystyle a}$.

Teorema: Si un nuevo nodo interno ${\displaystyle v}$ con etiqueta ${\displaystyle xa}$ es añadido al árbol en la extensión ${\displaystyle j}$ de la fase ${\displaystyle i+1}$, entonces se tendrá uno de los siguientes casos:

• El camino etiquetado ${\displaystyle a}$ termina en un nodo interno.
• En la extensión ${\displaystyle j+1}$ un nodo interno al final del camino a será creado.

Demostración: Un nuevo nodo es creado en la extensión ${\displaystyle j}$ de la fase ${\displaystyle i+1}$ solamente cuando la extensión ocurre en una arista (regla 2). Por tanto el camino etiquetado con ${\displaystyle xa}$ continua con un carácter ${\displaystyle d}$ distinto de ${\displaystyle c=S[i+1]}$. Al inicio de la extensión ${\displaystyle j+1}$, por el lema anterior, se cumple que hay un camino etiquetado con ${\displaystyle a}$ en el árbol y este continua con el carácter ${\displaystyle d}$, (y posiblemente con otros caracteres). Si el camino etiquetado con ${\displaystyle a}$ continua con otros caracteres además de ${\displaystyle d}$, entonces este ya termina en un nodo interno (primera situación del teorema). Por otra parte si el camino etiquetado con ${\displaystyle a}$ continua solamente con el carácter ${\displaystyle d}$, entonces en la extensión ${\displaystyle j+1}$, se aplicará la regla 2 y se creará un nodo interno al final de dicho camino (segunda situación del teorema).

Corolario: Al final de cada fase todos los nodos internos exceptuando la raíz tendrán un suffix link hacia otro nodo interno.

Usando los Suffix links para construir Ti+1

Recordemos que en la extensión ${\displaystyle j}$ de la fase ${\displaystyle i+1}$ el algoritmo localiza el sufijo ${\displaystyle S[j..i]}$ de ${\displaystyle S[1..i]}$ con ${\displaystyle 1\leq j\leq i+1}$, y luego realiza la extensión adecuada en dicho punto. Los suffix links se utilizarán para acortar el camino a la hora de localizar ${\displaystyle S[j..i]}$ en el árbol. Las primera extensión se puede realizar macheando el string ${\displaystyle S[1..i]}$en el árbol, sin la ayuda de suffix links. Para realizar la extensión ${\displaystyle j+1}$, debemos analizar los posibles casos donde ocurrió la extensión ${\displaystyle j}$.

• Si ${\displaystyle j}$ ocurrió en un nodo interno ${\displaystyle v}$ (distinto de la raíz), este estará etiquetado con el string ${\displaystyle xa=S[j..i]}$ y tendrá un suffix link hacia un nodo ${\displaystyle s(v)}$ etiquetado con el string ${\displaystyle a=S[j+1..i]}$ (por ser un nodo interno distinto de la raíz, creado en una extensión anterior a la extensión ${\displaystyle j}$ de la fase ${\displaystyle i}$). Por tanto la extensión ${\displaystyle j+1}$ se realizará en el nodo ${\displaystyle s(v)}$.

• Si ${\displaystyle j}$ ocurrió en una hoja ${\displaystyle u}$, sea ${\displaystyle v}$ el padre de ${\displaystyle u}$, y sea ${\displaystyle L}$ la etiqueta de la arista ${\displaystyle (u,v)}$. Si ${\displaystyle u}$ es la raíz, la extensión ${\displaystyle j+1}$ se debe realizar macheando la cadena ${\displaystyle S[j+1..i]}$ desde la raíz. Por otra parte si ${\displaystyle u}$ no es la raíz, entonces tiene un suffix link hacia el nodo ${\displaystyle s(u)}$, para realizar la extensión ${\displaystyle j+1}$, basta machear la cadena ${\displaystyle L}$ a partir de ${\displaystyle s(v)}$.

-Si ${\displaystyle j}$ ocurrió en una arista, sea ${\displaystyle v}$ el nodo creado para partir dicha arista, sea ${\displaystyle u}$ el padre ${\displaystyle v}$ y sea ${\displaystyle L}$ la etiqueta de la arista ${\displaystyle (u,v)}$. La extensión ${\displaystyle j+1}$ se realiza de forma análoga al caso anterior.

Obsérvese que la extensión ${\displaystyle j}$ no puede ocurrir en la raíz pues esta no es la última extensión de la fase.

Skip/count trick

Cuando se desea buscar la localización del final de una cadena ${\displaystyle S}$ en el árbol y se tiene la certeza de que esta se encuentra (como es el caso de las búsquedas que se realizan en las extensiones), no es necesario machear la cadena ${\displaystyle S}$ carácter a carácter, en estos casos es posible utilizar el skip/count trick que permite realizar la búsqueda en un orden linear respecto al número de nodos del camino.

Sea ${\displaystyle cur}$ el nodo en el que se encuentra el algoritmo, intentando localizar la cadena ${\displaystyle S}$, el skip/count trick ejecuta sucesivamente el siguiente procedimiento hasta obtener la posición buscada:

Si S es la cadena vacía, cur es la posición buscada.
Sino (cur,v) es la arista etiqueta L comparte el primer carácter con S (tiene que existir y ser única)
    Si |L|<|S|, la posición buscada es el carácter |S|-ésimo de la arista (cur,v).
    Sino hacer cur=v y eliminar los primeros |L| caracteres de S

Lema: Sea ${\displaystyle (v,s(v))}$ un suffix link atravesado durante el algoritmo de Ukkonen. En ese momento ${\displaystyle profundidad(v)}$ está acotada por ${\displaystyle 1+profundidad(s(v))}$.

Demostración: Cuando el link ${\displaystyle v,s(v))}$ (es atravesado, todo nodo interno ${\displaystyle u}$ ancestro de ${\displaystyle v}$, con etiqueta ${\displaystyle xa}$ (donde ${\displaystyle x}$ es un carácter y ${\displaystyle a}$ una cadena posiblemente vacía) tiene un suffix link hacia un nodo ${\displaystyle s(u)}$, etiquetado con ${\displaystyle a}$, ancestro de ${\displaystyle s(v)}$. Esta correspondencia es además unívoca. El único ancestro que puede tener ${\displaystyle v}$ sin su correspondiente ancestro para ${\displaystyle s(v)}$ es la raíz.

Teorema: Usando el skip/count trick, toda fase del algoritmo de Ukkonen toma un tiempo ${\displaystyle O(n)}$ donde ${\displaystyle |S|=n}$.

Demostración: hay ${\displaystyle i\leq n}$ extensiones en la fase ${\displaystyle i}$, en una extensión el algoritmo sube en el árbol a lo sumo un nodo, atraviesa a lo sumo un suffix link, baja en el árbol cierto número de nodos, aplica la extensión y añada a lo sumo un suffix link. Todas las operaciones distintas del descenso en el árbol toman tiempo constante. Solo necesitamos analizar la suma de los tiempos de realizar los descensos de todas las extensiones en la fase.

Para ello nos centraremos en la profundidad del nodo ${\displaystyle v}$ donde el algoritmo termina la fase. Al inicio de la fase se parte de la raíz, que tiene profundidad ${\displaystyle 0}$, como ${\displaystyle i\leq n}$, en la fase se realizan a lo sumo ${\displaystyle 2*n}$ descensos de profundidad (cuando se sube al padre o se atraviesa un suffix link), pero la profundidad del ${\displaystyle v}$ está acotada por ${\displaystyle n}$, por tanto el número de aumentos de profundidad está acotado por ${\displaystyle 3*n}$ ya que ${\displaystyle 0-2n+3n=n}$, y como cada descenso en el árbol aumenta la profundidad, el número de descensos en toda la fase está acotado por ${\displaystyle 3*n}$. Por tanto el tiempo que toma realizar una fase es ${\displaystyle O(n)}$.

Corolario: El algoritmo de Ukkonen puede ser implementado usando suffix links en tiempo ${\displaystyle O(n^{2})}$.

Extensiones implícitas

Observación: Una vez que la regla 3 aplica en la extensión ${\displaystyle j}$ de la fase ${\displaystyle i}$, la regla 3 aplicará en el resto de las extensiones de la fase ${\displaystyle i}$.

Esto es debido a que cuando la regla 3 aplica, es porque la cadena ${\displaystyle S[j..i]}$ pertenece al árbol antes de realizar la extensión ${\displaystyle j}$ y por tanto las cadenas ${\displaystyle S[j+1..i],...,S[i..i]}$ también pertenecen al árbol, por tanto en las extensiones ${\displaystyle j+1,j+2,...,i}$, la regla 3 también aplicará.

Observación: La extensión ${\displaystyle j+1}$ crea un suffix link solo cuando en la extensión ${\displaystyle j}$ aplica la regla 2.

Stop Trick

Es posible terminar la fase ${\displaystyle i}$ la primera vez que la regla 3 aplique. Si esto ocurre en la extensión ${\displaystyle j}$, se dice que las extensiones ${\displaystyle j+1,...,i}$ se realizaron de forma implícita.

Observación: Sea ${\displaystyle j'}$ la primera extensión de la fase ${\displaystyle i}$ en la que la regla 3 aplica, se cumple que las primeras ${\displaystyle j'-1}$ extensiones de la fase ${\displaystyle i}$ solo pudieron aplicar las reglas 1 o 2. Ambas reglas determinan una hoja etiquetada con el sufijo de ${\displaystyle S[1..i]}$ que se extendió. En la fase ${\displaystyle i+1}$ las primeras ${\displaystyle j'-1}$ extensiones ocurrirán en las hojas determinadas por las primeras j'-1 extensiones de la fase i. Por tanto en las primeras ${\displaystyle j'-1}$ extensiones de la fase ${\displaystyle i+1}$ aplicará la regla 1.

Observación: Cuando la regla 1 aplica en la fase ${\displaystyle i}$, en una hoja ${\displaystyle v}$, se sustituye la etiqueta ${\displaystyle [p,i]}$ de la arista incidente en la hoja ${\displaystyle v}$ por ${\displaystyle [p,i+1]}$. Esto da lugar a la siguiente mejora.

Pointer Trick

Cada vez que una hoja es creada en la fase ${\displaystyle i}$, se etiqueta la arista incidente a dicha hoja con el par ${\displaystyle [p,i]}$, el pointer trick propone etiquetar dicha arista con el par ${\displaystyle [p,e]}$, donde ${\displaystyle e}$ es un puntero al número que identifica la fase actual. De esta forma no es necesario hacer nada cuando aplica la regla 1. Como se tiene que las primeras en las primeras ${\displaystyle j'-1}$ extensiones de la fase ${\displaystyle i+1}$ aplicará la regla 1, es posible comenzar la fase ${\displaystyle i+1}$ a partir de la extensión ${\displaystyle j'}$, dejando que las primeras ${\displaystyle j'-1}$extensiones, se realicen de forma implícita.

Teorema: El algoritmo de Ukkonen construye el árbol de sufijos de ${\displaystyle S}$, con los suffix links con costo espacial y temporal ${\displaystyle O(n)}$.

Demostración: El tiempo para realizar todas las extensiones implícitas a lo largo del algoritmo es constante.

Consideremos el índice ${\displaystyle j}$ correspondiente a la extensión explicita actual, en toda la ejecución del algoritmo de Ukkonen ${\displaystyle j}$ nunca decrece, aunque sí se mantiene invariante cuando pasa de una fase a la siguiente. Como solo hay ${\displaystyle |S|=n}$ fases, el número de extensiones explícitas está acotado por ${\displaystyle n}$. El algoritmo por tanto ejecuta a lo sumo ${\displaystyle 2*n}$ extensiones explícitas.

Como se explicó anteriormente el costo temporal de una extensión explícita depende del costo temporal de realizar el descenso en el árbol en dicha extensión. Para acotar el número de nodos recorridos en los descensos en el árbol durante el algoritmo de Ukkonen, es importante observar, que el nodo actual no varía cuando el algoritmo cambia de fase, la acotación se efectúa de forma análoga a como se hizo en la demostración del teorema anterior.

Algoritmo de Viterbi

algoritmo de Viterbi es un algoritmo de programación dinámica que permite hallar la secuencia más probable de estados ocultos (el llamado camino de Viterbi) que produce una secuencia observada de sucesos, especialmente en el contexto de fuentes de información de Márkov y modelos ocultos de Márkov.

Se aplica de forma general en la descodificación de códigos convolucionales usados en redes de telefonía celular digital GSM y CDMA, módems de líneas conmutadas, satélites, comunicaciones espaciales y redes inalámbricas IEEE 802.11. También se usa en reconocimiento del habla, síntesis de habla, diarización, búsqueda de palabras clave, lingüística computacional y bioinformática.

Introducción

El algoritmo de Viterbi permite encontrar las secuencias de estados más probable en un Modelo oculto de Márkov (MOM), ${\displaystyle S=(q_{1},q_{2},\ldots ,q_{T})}$, a partir de una observación ${\displaystyle O=(o_{1},o_{2},\ldots ,o_{T})}$, es decir, obtiene la secuencia óptima que mejor explica la secuencia de observaciones.

Consideremos la variable ${\displaystyle \delta _{t}{(i)}}$ que se define como:

${\displaystyle \delta _{t}{(i)}=\max _{q_{1},q_{2},\ldots ,q_{t-1}}{P(q_{1},q_{2},\ldots ,q_{t}=i,o_{1},o_{2},\ldots ,o_{t}|\mu )}}$

${\displaystyle \delta _{t}{(i)}}$ es la probabilidad del mejor camino hasta el estado ${\displaystyle i}$ habiendo visto las ${\displaystyle t}$ primeras observaciones. Esta función se calcula para todos los estados e instantes de tiempo.

${\displaystyle \delta _{t+1}{(j)}={\biggl [}\max _{1\leq i\leq N}{\delta _{t}{(i)(a_{ij})}}{\biggr ]}b_{j}(o_{t+1})}$

Puesto que el objetivo es obtener las secuencia de estados más probable, será necesario almacenar el argumento que hace máxima la ecuación anterior en cada instante de tiempo ${\displaystyle t}$ y para cada estado ${\displaystyle j}$ y para ello utilizamos la variable ${\displaystyle \varphi _{t}{(j)}}$.

A continuación se detalla el proceso completo utilizando las funciones ${\displaystyle \delta }$ y ${\displaystyle \varphi }$.

Algoritmo

Inicialización

${\displaystyle \delta _{1}(i)=\pi _{i}b_{i}(o_{1})}$

donde ${\displaystyle 1\leq i\leq N}$

Recursión

${\displaystyle \delta _{t+1}{(j)}={\biggl [}\max _{1\leq i\leq N}{\delta _{t}{(i)}a_{ij}}{\biggr ]}b_{j}(o_{t+1})}$,

donde:

${\displaystyle t=1,2,\ldots ,T-1}$, ${\displaystyle 1\leq j\leq N}$

${\displaystyle \varphi _{t+1}{(j)}=\arg \max _{1\leq i\leq N}{\delta _{t}{(i)a_{ij}}}}$,

donde:

${\displaystyle t=1,2,\ldots ,T-1}$, ${\displaystyle 1\leq j\leq N}$

Terminación

${\displaystyle q_{T}^{*}=\arg \max _{1\leq i\leq N}{\delta _{T}{(i)}}}$

Reconstrucción de la secuencia de estados más probable

${\displaystyle q_{t}^{*}=\varphi _{t+1}{(q_{t+1}^{*})}}$,

donde:

${\displaystyle t=T-1,T-2,\ldots ,1}$

Algunos de los cálculos del algoritmo de Viterbi recuerdan a los del algoritmo forward necesario para calcular eficientemente la probabilidad de una secuencia de observables. Una de las diferencias es la incorporación de la función ${\displaystyle \arg \max }$ (en lugar de sumar las probabilidades) para calcular la secuencia de estados más probable.

Ejemplo de secuencia de estados más probable

La figura muestra un ejemplo de secuencia de estados más probable en un Modelo Oculto de Márkov de 5 estados dada una secuencia de observaciones de longitud 5.

Aplicación del algoritmo de Viterbi

Muy usado para reconocimiento de voz, biología molecular, fonemas, palabras, codificadores entre otros. A cada secuencia de estados le corresponde una secuencia de etiquetas (o labels) de clasificación, es decir, palabras, caracteres, fonemas, sufijos. Dada una secuencia observada, se deduce la más probable secuencia de estados.

Desambiguación léxica categorial

Una de las aplicaciones del algoritmo de Viterbi es en el área de procesamiento del lenguaje natural, más concretamente en el proceso de desambiguación léxica categorial.

En este caso particular, los elementos de un Modelo Oculto de Márkov serían los siguientes:

• El conjunto ${\displaystyle Q}$ de estados sería el conjunto de posibles etiquetas (categorías gramaticales) para las palabras.
• El conjunto ${\displaystyle V}$ de observables en cada uno de los estados corresponde con el conjunto de palabras distintas.
• El conjunto ${\displaystyle A}$ de probabilidades de transiciones entre estados sería la probabilidad de que una determinada categoría categorial siga a otra. Por ejemplo, la probabilidad de que la categoría nombre vaya detrás de la categoría determinante.
• El conjunto ${\displaystyle B}$ de probabilidades de las observaciones correspondería con la probabilidad de pertenencia de una palabra (un observable) a una determinada categoría. Por ejemplo, la probabilidad de que la palabra casa sea verbo, que será menor que la probabilidad de que esta misma palabra tenga la categoría gramatical nombre.

La figura siguiente muestra un ejemplo de etiquetado gramatical para la oración "Coto privado de caza"

En él, los observables son la secuencia de palabras de la oración. Se puede observar como para cada palabra se contempla sólo un conjunto limitado de posibles categorías gramaticales (caza puede ser o nombre o verbo). Este es debido a que la probabilidad de pertenencia de determinadas palabras a una categoría gramatical es nula (como la probabilidad de que la palabra caza sea adverbio). Esto simplifica enormemente los cálculos en el modelo.

Otras preguntas fundamentales

Otros dos problemas que es importante saber resolver para utilizar los MOM son:

1. ¿Cuál es la probabilidad de una secuencia de observaciones ${\displaystyle O=(o_{1},o_{2},\ldots ,o_{T})}$ dado un modelo ${\displaystyle \mu =(\pi ,A,B)}$? Es decir, ¿cómo podemos calcular de forma eficiente ${\displaystyle P(O|\mu )}$?. Para esto se puede usar el algoritmo de avance-retroceso.
2. Dada una secuencia de observaciones ${\displaystyle O=(o_{1},o_{2},\ldots ,o_{T})}$, ¿cómo podemos estimar los parámetros del modelo ${\displaystyle \mu =(\pi ,A,B)}$ para maximizar ${\displaystyle P(O|\mu )}$. En este caso el objetivo es encontrar el modelo que mejor explica la secuencia observada. Para esto se puede usar el algoritmo de Baum-Welch.