Hispanopedia Wiki
Articulo de referencia

Algoritmo de Baum-Welch

En ingeniería eléctrica , computación estadística y bioinformática , el algoritmo de Baum-Welch es un caso especial del algoritmo de expectativa-maximización utilizado para enco...

Hispanopedia WikiContenido en espanolLectura gratuita

En ingeniería eléctrica , computación estadística y bioinformática , el algoritmo de Baum-Welch es un caso especial del algoritmo de expectativa-maximización utilizado para encontrar los parámetros desconocidos de un modelo oculto de Markov (HMM). Utiliza el algoritmo de avance-retroceso para calcular las estadísticas del paso de expectativa. El algoritmo de Baum-Welch, el método principal para la inferencia en modelos ocultos de Markov, es numéricamente inestable debido a su cálculo recursivo de probabilidades conjuntas. A medida que aumenta el número de variables, estas probabilidades conjuntas se vuelven cada vez más pequeñas, lo que provoca que las recursiones hacia adelante se aproximen rápidamente a valores inferiores a la precisión de la máquina. [ 1 ]

Historia

El algoritmo Baum-Welch recibió su nombre de sus inventores, Leonard E. Baum y Lloyd R. Welch . El algoritmo y los modelos ocultos de Markov fueron descritos por primera vez en una serie de artículos por Baum y sus colegas en el Centro IDA para la Investigación de las Comunicaciones, Princeton, a finales de la década de 1960 y principios de la de 1970. [ 2 ] Una de las primeras aplicaciones importantes de los HMM fue en el campo del procesamiento del habla . [ 3 ] En la década de 1980, los HMM emergieron como una herramienta útil en el análisis de sistemas biológicos e información, y en particular información genética . [ 4 ] Desde entonces, se han convertido en una herramienta importante en el modelado probabilístico de secuencias genómicas. [ 5 ]

Descripción

Un modelo oculto de Markov describe la probabilidad conjunta de un conjunto de variables aleatorias discretas, tanto ocultas como observadas. Se basa en la suposición de que la i -ésima variable oculta, dada la ( i -1)-ésima variable oculta, es independiente de las variables ocultas anteriores, y que las variables de observación actuales dependen únicamente del estado oculto actual.

El algoritmo Baum-Welch utiliza el conocido algoritmo EM para encontrar la estimación de máxima verosimilitud de los parámetros de un modelo oculto de Markov, dado un conjunto de vectores de características observadas.

Dejarincógnitat{\displaystyle X_{t}}ser una variable aleatoria oculta discreta connorte{\displaystyle N}valores posibles (es decir, asumimos que haynorte{\displaystyle N}estados en total). Suponemos quePAG(incógnitat∣incógnitat−1){\displaystyle P(X_{t}\mid X_{t-1})}es independiente del tiempot{\displaystyle t}lo que lleva a la definición de la matriz de transición estocástica independiente del tiempo.

A={aij}=PAG(incógnitat=j∣incógnitat−1=i).{\displaystyle A=\{a_{ij}\}=P(X_{t}=j\mid X_{t-1}=i).}

La distribución del estado inicial (es decir, cuandot=1{\displaystyle t=1}) viene dado por

πi=PAG(incógnita1=i).{\displaystyle \pi _{i}=P(X_{1}=i).}

Las variables de observaciónYt{\displaystyle Y_{t}}puede tomar uno deK{\displaystyle K}valores posibles. También asumimos que la observación dado el estado "oculto" es independiente del tiempo. La probabilidad de una observación determinadayi{\displaystyle y_{i}}en ese momentot{\displaystyle t}para el estadoincógnitat=j{\displaystyle X_{t}=j}es dado por

bj(yi)=PAG(Yt=yi∣incógnitat=j).{\displaystyle b_{j}(y_{i})=P(Y_{t}=y_{i}\mid X_{t}=j).}

Teniendo en cuenta todos los valores posibles deYt{\displaystyle Y_{t}}yincógnitat{\displaystyle X_{t}}, obtenemos elnorte×K{\displaystyle N\times K}matrizB={bj(yi)}{\displaystyle B=\{b_{j}(y_{i})\}}dóndebj{\displaystyle b_{j}}pertenece a todos los estados posibles yyi{\displaystyle y_{i}}pertenece a todas las observaciones.

Una secuencia de observaciones viene dada porY=(Y1=y1,Y2=y2,…,YT=yT){\displaystyle Y=(Y_{1}=y_{1},Y_{2}=y_{2},\ldots,Y_{T}=y_{T})}.

Así podemos describir una cadena oculta de Markov medianteθ=(A,B,π){\displaystyle \theta =(A,B,\pi )}El algoritmo de Baum-Welch encuentra un máximo local paraθ∗=argramometroaincógnitaθ⁡PAG(Y∣θ){\displaystyle \theta ^{*}=\operatorname {arg\,max} _{\theta }P(Y\mid \theta )}(es decir, los parámetros HMM)θ{\displaystyle \theta }que maximizan la probabilidad de la observación). [ 6 ]

Algoritmo

Colocarθ=(A,B,π){\displaystyle \theta =(A,B,\pi )}con condiciones iniciales aleatorias. También se pueden establecer utilizando información previa sobre los parámetros, si está disponible; esto puede acelerar el algoritmo y también dirigirlo hacia el máximo local deseado.

Procedimiento de avance

Dejarαi(t)=PAG(Y1=y1,…,Yt=yt,incógnitat=i∣θ){\displaystyle \alpha _{i}(t)=P(Y_{1}=y_{1},\ldots ,Y_{t}=y_{t},X_{t}=i\mid \theta )}, la probabilidad de ver las observacionesy1,y2,…,yt{\displaystyle y_{1},y_{2},\ldots,y_{t}}y estar en el estadoi{\displaystyle i}en ese momentot{\displaystyle t}Esto se encuentra recursivamente:

  1. αi(1)=πibi(y1),{\displaystyle \alpha _{i}(1)=\pi _{i}b_{i}(y_{1}),}
  2. αi(t+1)=bi(yt+1)∑j=1norteαj(t)aji.{\displaystyle \alpha _{i}(t+1)=b_{i}(y_{t+1})\sum _{j=1}^{N}\alpha _{j}(t)a_{ji}.}

Dado que esta serie converge exponencialmente a cero, el algoritmo tendrá un desbordamiento negativo numérico para secuencias más largas. [ 7 ] Sin embargo, esto se puede evitar en un algoritmo ligeramente modificado mediante el escalado.α{\displaystyle \alpha }en el delantero yβ{\displaystyle \beta }en el procedimiento inverso que se describe a continuación.

Procedimiento inverso

Dejarβi(t)=PAG(Yt+1=yt+1,…,YT=yT∣incógnitat=i,θ){\displaystyle \beta _{i}(t)=P(Y_{t+1}=y_{t+1},\ldots ,Y_{T}=y_{T}\mid X_{t}=i,\theta )}esa es la probabilidad de la secuencia parcial finalyt+1,…,yT{\displaystyle y_{t+1},\ldots ,y_{T}}estado inicial dadoi{\displaystyle i}en ese momentot{\displaystyle t}Calculamos.βi(t){\displaystyle \beta _{i}(t)}como,

  1. βi(T)=1,{\displaystyle \beta _{i}(T)=1,}
  2. βi(t)=∑j=1norteβj(t+1)aijbj(yt+1).{\displaystyle \beta _{i}(t)=\sum _{j=1}^{N}\beta _{j}(t+1)a_{ij}b_{j}(y_{t+1}).}

Actualizar

Ahora podemos calcular las variables temporales, según el teorema de Bayes :

γi(t)=PAG(incógnitat=i∣Y,θ)=PAG(incógnitat=i,Y∣θ)PAG(Y∣θ)=αi(t)βi(t)∑j=1norteαj(t)βj(t),{\displaystyle \gamma _{i}(t)=P(X_{t}=i\mid Y,\theta )={\frac {P(X_{t}=i,Y\mid \theta )}{P(Y\mid \theta )}}={\frac {\alpha _{i}(t)\beta _{i}(t)}{\sum _{j=1}^{N}\alpha _{j}(t)\beta _{j}(t)}},}

que es la probabilidad de estar en estadoi{\displaystyle i}en ese momentot{\displaystyle t}dada la secuencia observadaY{\displaystyle Y}y los parámetrosθ{\displaystyle \theta }

ξij(t)=PAG(incógnitat=i,incógnitat+1=j∣Y,θ)=PAG(incógnitat=i,incógnitat+1=j,Y∣θ)PAG(Y∣θ)=αi(t)aijβj(t+1)bj(yt+1)∑k=1norte∑w=1norteαk(t)akwβw(t+1)bw(yt+1),{\displaystyle \xi _{ij}(t)=P(X_{t}=i,X_{t+1}=j\mid Y,\theta )={\frac {P(X_{t}=i,X_{t+1}=j,Y\mid \theta )}{P(Y\mid \theta )}}={\frac {\alpha _{i}(t)a_{ij}\beta _{j}(t+1)b_{j}(y_{t+1})}{\sum _{k=1}^{N}\sum _{w=1}^{N}\alpha _{k}(t)a_{kw}\beta _{w}(t+1)b_{w}(y_{t+1})}},}

que es la probabilidad de estar en estadoi{\displaystyle i}yj{\displaystyle j}a vecest{\displaystyle t}yt+1{\displaystyle t+1}respectivamente dada la secuencia observadaY{\displaystyle Y}y parámetrosθ{\displaystyle \theta }.

Los denominadores deγi(t){\displaystyle \gamma _{i}(t)}yξij(t){\displaystyle \xi _{ij}(t)}son lo mismo  ; representan la probabilidad de hacer la observaciónY{\displaystyle Y}dados los parámetrosθ{\displaystyle \theta }.

Los parámetros del modelo oculto de Markovθ{\displaystyle \theta }Ahora se puede actualizar:

  • πi∗=γi(1),{\displaystyle \pi _{i}^{*}=\gamma _{i}(1),}

que es la frecuencia esperada que se pasa en el estadoi{\displaystyle i}en ese momento1{\displaystyle 1}.

  • aij∗=∑t=1T−1ξij(t)∑t=1T−1γi(t),{\displaystyle a_{ij}^{*}={\frac {\sum _{t=1}^{T-1}\xi _{ij}(t)}{\sum _{t=1}^{T-1}\gamma _{i}(t)}},}

que es el número esperado de transiciones del estado i al estado j en comparación con el número total esperado de transiciones que comienzan en el estado i , incluyendo las transiciones del estado i a sí mismo. El número de transiciones que comienzan en el estado i es equivalente al número de veces que se observa el estado i en la secuencia desde t  =  1 hasta t  = T − 1.   

  • bi∗(vk)=∑t=1T1yt=vkγi(t)∑t=1Tγi(t),{\displaystyle b_{i}^{*}(v_{k})={\frac {\sum _{t=1}^{T}1_{y_{t}=v_{k}}\gamma _{i}(t)}{\sum _{t=1}^{T}\gamma _{i}(t)}},}

dónde

1yt=vk={1si yt=vk,0de lo contrario{\displaystyle 1_{y_{t}=v_{k}}={\begin{cases}1&{\text{if }}y_{t}=v_{k},\\0&{\text{otherwise}}\end{cases}}}

es una función indicadora ybi∗(vk){\displaystyle b_{i}^{*}(v_{k})}es el número esperado de veces que las observaciones de salida han sido iguales avk{\displaystyle v_{k}}mientras se encuentra en el estadoi{\displaystyle i}sobre el número total esperado de veces en el estadoi{\displaystyle i}.

Estos pasos se repiten ahora de forma iterativa hasta alcanzar el nivel de convergencia deseado.

Nota: Es posible sobreajustar un conjunto de datos en particular . Es decir,PAG(Y∣θfinal)>PAG(Y∣θverdadero){\displaystyle P(Y\mid \theta _{\text{final}})>P(Y\mid \theta _{\text{true}})}El algoritmo tampoco garantiza un máximo global.

Múltiples secuencias

El algoritmo descrito hasta ahora presupone una única secuencia observada.Y=y1,…,yT{\displaystyle Y=y_{1},\ldots ,y_{T}}Sin embargo, en muchas situaciones se observan varias secuencias:Y1,…,YR{\displaystyle Y_{1},\ldots ,Y_{R}}En este caso, se debe utilizar la información de todas las secuencias observadas para actualizar los parámetros.A{\displaystyle A},π{\displaystyle \pi }, yb{\displaystyle b}. Suponiendo que hayas calculadoγir(t){\displaystyle \gamma _{ir}(t)}yξijr(t){\displaystyle \xi _{ijr}(t)}para cada secuenciay1,r,…,ynorter,r{\displaystyle y_{1,r},\ldots ,y_{N_{r},r}}Ahora se pueden actualizar los parámetros:

  • πi∗=∑r=1Rγir(1)R{\displaystyle \pi _{i}^{*}={\frac {\sum _{r=1}^{R}\gamma _{ir}(1)}{R}}}
  • aij∗=∑r=1R∑t=1T−1ξijr(t)∑r=1R∑t=1T−1γir(t),{\displaystyle a_{ij}^{*}={\frac {\sum _{r=1}^{R}\sum _{t=1}^{T-1}\xi _{ijr}(t)}{\sum _{r=1}^{R}\sum _{t=1}^{T-1}\gamma _{ir}(t)}},}
  • bi∗(vk)=∑r=1R∑t=1T1ytr=vkγir(t)∑r=1R∑t=1Tγir(t),{\displaystyle b_{i}^{*}(v_{k})={\frac {\sum _{r=1}^{R}\sum _{t=1}^{T}1_{y_{tr}=v_{k}}\gamma _{ir}(t)}{\sum _{r=1}^{R}\sum _{t=1}^{T}\gamma _{ir}(t)}},}

dónde

1ytr=vk={1si yt,r=vk,0de lo contrario{\displaystyle 1_{y_{tr}=v_{k}}={\begin{cases}1&{\text{if }}y_{t,r}=v_{k},\\0&{\text{otherwise}}\end{cases}}}

es una función indicadora

Ejemplo

Supongamos que tenemos una gallina de la que recogemos huevos al mediodía todos los días. Ahora bien, que la gallina haya puesto huevos o no depende de algunos factores desconocidos que están ocultos. Sin embargo, podemos suponer (para simplificar) que la gallina siempre está en uno de dos estados que influyen en si pone huevos, y que este estado solo depende del estado del día anterior. Ahora bien, no conocemos el estado en el punto de partida inicial, no conocemos las probabilidades de transición entre los dos estados y no conocemos la probabilidad de que la gallina ponga un huevo dado un estado particular. [ 8 ] [ 9 ] Para empezar, primero estimamos las matrices de transición y emisión.

Luego tomamos un conjunto de observaciones (E = huevos, N = sin huevos): N, N, N, N, N, E, E, N, N, N

Esto nos da un conjunto de transiciones observadas entre días: NN, NN, NN, NN, NE, EE, EN, NN, NN

El siguiente paso es estimar una nueva matriz de transición. Por ejemplo, la probabilidad de la secuencia NN y el estado siendo ⁠S1{\displaystyle S_{1}}entonces​​S2{\displaystyle S_{2}}Se da de la siguiente manera :PAG(S1)⋅PAG(norte|S1)⋅PAG(S1→S2)⋅PAG(norte|S2).{\displaystyle P(S_{1})\cdot P(N|S_{1})\cdot P(S_{1}\rightarrow S_{2})\cdot P(N|S_{2}).}

Por lo tanto, la nueva estimación para el ⁠S1{\displaystyle S_{1}}a​​S2{\displaystyle S_{2}}La transición es ahora0,222.4234=0,0908{\displaystyle {\frac {0.22}{2.4234}}=0.0908}(denominadas "Pseudoprobabilidades" en las tablas siguientes). A continuación, calculamos las ⁠S2{\displaystyle S_{2}}a​​S1{\displaystyle S_{1}},​​S2{\displaystyle S_{2}}a​​S2{\displaystyle S_{2}}y​​S1{\displaystyle S_{1}}a​​S1{\displaystyle S_{1}}⁠ probabilidades de transición y normalizamos cada fila de la matriz de transición de modo que las probabilidades de transición desde un estado inicial dado sumen 1. Esto nos da la matriz de transición actualizada:

A continuación, queremos estimar una nueva matriz de emisiones,

La nueva estimación para E proveniente deS1{\displaystyle S_{1}}La emisión es ahora0,23940,2730=0,8769{\displaystyle {\frac {0.2394}{0.2730}}=0.8769}.

Esto nos permite calcular la matriz de emisión como se describe anteriormente en el algoritmo, sumando las probabilidades para las respectivas secuencias observadas. Luego repetimos para si N proviene de ⁠S1{\displaystyle S_{1}}y porque si N y E provenían deS2{\displaystyle S_{2}}y normalizar.

Para estimar las probabilidades iniciales, asumimos que todas las secuencias comienzan con el estado oculto .S1{\displaystyle S_{1}}y calcular la probabilidad más alta y luego repetir paraS2{\displaystyle S_{2}}⁠ . Luego, normalizamos nuevamente para obtener un vector inicial actualizado.

Finalmente, repetimos estos pasos hasta que las probabilidades resultantes converjan satisfactoriamente.

Aplicaciones

Reconocimiento de voz

Los modelos ocultos de Markov (HMM) fueron aplicados por primera vez al reconocimiento de voz por James K. Baker en 1975. [ 10 ] El reconocimiento continuo de voz se produce mediante los siguientes pasos, modelados por un HMM. Primero se realiza un análisis de características en las características temporales y/o espectrales de la señal de voz. Esto produce un vector de observación. Luego, la característica se compara con todas las secuencias de las unidades de reconocimiento de voz. Estas unidades pueden ser fonemas , sílabas o unidades de palabras completas. Se aplica un sistema de decodificación léxica para restringir las rutas investigadas, de modo que solo se investigan las palabras en el léxico (diccionario de palabras) del sistema. De manera similar a la decodificación léxica, la ruta del sistema está además restringida por las reglas de gramática y sintaxis. Finalmente, se aplica el análisis semántico y el sistema produce la locución reconocida. Una limitación de muchas aplicaciones de HMM al reconocimiento de voz es que el estado actual solo depende del estado en el paso de tiempo anterior, lo cual no es realista para el habla, ya que las dependencias a menudo tienen una duración de varios pasos de tiempo. [ 11 ] El algoritmo Baum-Welch también tiene amplias aplicaciones en la resolución de HMM utilizados en el campo de la síntesis de voz . [ 12 ]

Criptoanálisis

El algoritmo Baum-Welch se utiliza a menudo para estimar los parámetros de los HMM en el descifrado de información oculta o ruidosa y, por consiguiente, se emplea frecuentemente en criptoanálisis . En seguridad de datos, un observador desearía extraer información de un flujo de datos sin conocer todos los parámetros de la transmisión. Esto puede implicar la ingeniería inversa de un codificador de canal . [ 13 ] Los HMM y, por consiguiente, el algoritmo Baum-Welch también se han utilizado para identificar frases habladas en llamadas VoIP cifradas. [ 14 ] Además, el criptoanálisis de HMM es una herramienta importante para las investigaciones automatizadas de datos de temporización de caché. Permite el descubrimiento automático del estado crítico del algoritmo, por ejemplo, los valores de las claves. [ 15 ]

Aplicaciones en bioinformática

Encontrar genes

Procariota

El software GLIMMER (Gene Locator and Interpolated Markov ModelER) fue un programa pionero para la búsqueda de genes, utilizado para la identificación de regiones codificantes en el ADN procariota . [ 16 ] [ 17 ] GLIMMER utiliza modelos de Markov interpolados (IMM) para identificar las regiones codificantes y distinguirlas del ADN no codificante . Se ha demostrado que la última versión (GLIMMER3) tiene mayor especificidad y precisión en comparación con sus predecesores con respecto a la predicción de sitios de inicio de la traducción, demostrando una precisión promedio del 99 % en la localización de ubicaciones 3' en comparación con genes confirmados en procariotas. [ 18 ]

Eucariota

El servidor web GENSCAN es un localizador de genes capaz de analizar secuencias eucariotas de hasta un millón de pares de bases (1 Mbp) de longitud. [ 19 ] GENSCAN utiliza un modelo de Markov general, heterogéneo, de quinto orden y tres períodos para las regiones codificantes del ADN. Además, este modelo tiene en cuenta las diferencias en la densidad y estructura de los genes (como la longitud de los intrones) que se producen en diferentes isocoras . Mientras que la mayoría del software integrado de búsqueda de genes (en el momento del lanzamiento de GENSCAN) asumía que las secuencias de entrada contenían exactamente un gen, GENSCAN resuelve un caso general en el que hay genes parciales, completos o múltiples (o incluso ningún gen). [ 20 ] Se demostró que GENSCAN predice con exactitud la ubicación de los exones con una precisión del 90 % y una especificidad del 80 % en comparación con una base de datos anotada. [ 21 ]

Detección de variación del número de copias

Las variaciones del número de copias (CNV) son una forma abundante de variación de la estructura del genoma en humanos. Se utilizó un HMM bivariado de valores discretos (dbHMM) que asigna regiones cromosómicas a siete estados distintos: regiones no afectadas, deleciones, duplicaciones y cuatro estados de transición. La resolución de este modelo utilizando Baum-Welch demostró la capacidad de predecir la ubicación del punto de ruptura de CNV a aproximadamente 300 pb a partir de experimentos de microarrays . [ 22 ] Esta magnitud de resolución permite correlaciones más precisas entre diferentes CNV y entre poblaciones que las que eran posibles anteriormente, lo que permite el estudio de las frecuencias poblacionales de CNV. También demostró un patrón de herencia directa para un CNV en particular .

Implementaciones

Véase también

Referencias

  1. ↑ "Factores de escala para modelos ocultos de Markov" . gregorygundersen.com . Consultado el 19 de octubre de 2024 .
  2. ↑ Rabiner, Lawrence. "De primera mano: El modelo oculto de Markov" . IEEE Global History Network . Consultado el 2 de octubre de 2013 .
  3. ↑ Jelinek, Frederick; Bahl, Lalit R.; Mercer, Robert L. (mayo de 1975). "Diseño de un decodificador estadístico lingüístico para el reconocimiento del habla continua". IEEE Transactions on Information Theory . 21 (3): 250– 6. doi : 10.1109/tit.1975.1055384 .
  4. ↑ Bishop, Martin J.; Thompson, Elizabeth A. (20 de julio de 1986). "Alineación de máxima verosimilitud de secuencias de ADN". Journal of Molecular Biology . 190 (2): 159– 65. doi : 10.1016/0022-2836(86)90289-5 . PMID 3641921 . 
  5. ↑ Durbin, Richard (23 de abril de 1998). Análisis de secuencias biológicas: modelos probabilísticos de proteínas y ácidos nucleicos . Cambridge University Press. ISBN 978-0-521-62041-3.
  6. ↑ Bilmes, Jeff A. (1998). Un tutorial sencillo del algoritmo EM y su aplicación a la estimación de parámetros para modelos de mezcla gaussiana y modelos ocultos de Markov . Berkeley, CA: Instituto Internacional de Ciencias de la Computación. págs. 7–13 . 
  7. ↑ Rabiner, Lawrence (febrero de 1989). "Un tutorial sobre modelos ocultos de Markov y aplicaciones seleccionadas en el reconocimiento de voz" (PDF) . Actas del IEEE . Consultado el 29 de noviembre de 2019 .
  8. ↑ "Aplicaciones de Baum-Welch y HMM" (PDF) . Escuela de Salud Pública Johns Hopkins Bloomberg. Archivado del original (PDF) el 14 de abril de 2021. Consultado el 11 de octubre de 2019 .
  9. ↑ Frazzoli, Emilio. "Introducción a los modelos ocultos de Markov: el algoritmo de Baum-Welch" (PDF) . Aeronáutica y Astronáutica, Instituto Tecnológico de Massachusetts . Consultado el 2 de octubre de 2013 .
  10. ↑ Baker, James K. (1975). "El sistema DRAGON: una visión general". IEEE Transactions on Acoustics, Speech, and Signal Processing . 23 : 24–29 . doi : 10.1109/TASSP.1975.1162650 .
  11. ↑ Rabiner, Lawrence (febrero de 1989). "Un tutorial sobre modelos ocultos de Markov y aplicaciones seleccionadas en el reconocimiento de voz". Actas del IEEE . 77 (2): 257– 286. CiteSeerX 10.1.1.381.3454 . doi : 10.1109/5.18626 . S2CID 13618539 .  
  12. ↑ Tokuda, Keiichi; Yoshimura, Takayoshi; Masuko, Takashi; Kobayashi, Takao; Kitamura, Tadashi (2000). "Algoritmos de generación de parámetros de voz para síntesis de voz basada en HMM". Conferencia Internacional IEEE sobre Acústica, Habla y Procesamiento de Señales . 3 .
  13. ↑ Dingel, Janis; Hagenauer, Joachim (24 de junio de 2007). "Estimación de parámetros de un codificador convolucional a partir de observaciones ruidosas". Simposio Internacional IEEE sobre Teoría de la Información .
  14. ↑ Wright, Charles; Ballard, Lucas; Coull, Scott; Monrose, Fabian; Masson, Gerald (2008). "Encuéntrame si puedes: Descubriendo frases habladas en conversaciones VoIP encriptadas". Simposio Internacional IEEE sobre Seguridad y Privacidad .
  15. ↑ Brumley, Bob; Hakala, Risto (2009). "Ataques de plantillas de temporización de caché". Avances en criptología – ASIACRYPT 2009. Notas de clase en ciencias de la computación. Vol. 5912. págs. 667–684 . doi : 10.1007/978-3-642-10366-7_39 . ISBN   978-3-642-10365-0.
  16. ↑ Salzberg, Steven; Delcher, Arthur L.; Kasif, Simon; White, Owen (1998). "Identificación de genes microbianos mediante modelos de Markov interpolados" . Nucleic Acids Research . 26 (2): 544– 548. doi : 10.1093/nar/26.2.544 . PMC 147303. PMID 9421513 .  
  17. ↑ "Glimmer: Sistema de detección de genes microbianos" . Universidad Johns Hopkins - Centro de Biología Computacional.
  18. ↑ Delcher, Arthur; Bratke, Kirsten A.; Powers, Edwin C.; Salzberg, Steven L. (2007). "Identificación de genes bacterianos y ADN de endosimbiontes con Glimmer" . Bioinformatics . 23 ( 6): 673– 679. doi : 10.1093/bioinformatics/btm009 . PMC 2387122. PMID 17237039 .  
  19. ↑ Burge, Christopher. "El servidor web GENSCAN en el MIT" . Archivado del original el 6 de septiembre de 2013. Recuperado el 2 de octubre de 2013 .
  20. ↑ Burge, Chris; Karlin, Samuel (1997). "Predicción de estructuras genéticas completas en el ADN genómico humano". Journal of Molecular Biology . 268 (1): 78– 94. CiteSeerX 10.1.1.115.3107 . doi : 10.1006/jmbi.1997.0951 . PMID 9149143 .  
  21. ↑ Burge, Christopher; Karlin, Samuel (1998). "Finding the Genes in Genomic DNA" . Current Opinion in Structural Biology . 8 (3): 346– 354. doi : 10.1016/s0959-440x(98)80069-9 . PMID 9666331 . 
  22. ↑ Korbel, Jan ; Urban, Alexander; Grubert, Fabien; Du, Jiang; Royce, Thomas; Starr, Peter; Zhong, Guoneng; Emanuel, Beverly; Weissman, Sherman; Snyder, Michael; Gerstein, Marg (12 de junio de 2007). "Predicción y validación sistemáticas de puntos de ruptura asociados con variaciones del número de copias en el genoma humano" . Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 104 (24): 10110– 5. Bibcode : 2007PNAS..10410110K . doi : 10.1073/pnas.0703834104 . PMC 1891248. PMID 17551006 .  
  • Revisión exhaustiva de los métodos y el software HMM en bioinformática: Perfil de los modelos ocultos de Markov
  • Primeras publicaciones de Baum sobre HMM:
    • Una técnica de maximización que se presenta en el análisis estadístico de funciones probabilísticas de cadenas de Markov.
    • Una desigualdad con aplicaciones a la estimación estadística de funciones probabilísticas de procesos de Markov y a un modelo para la ecología.
    • Inferencia estadística para funciones probabilísticas de cadenas de Markov de estados finitos
  • La conferencia Shannon de Welch, que explica cómo se puede implementar el algoritmo de manera eficiente:
    • Modelos ocultos de Markov y el algoritmo de Baum-Welch , Boletín informativo de la Sociedad de Teoría de la Información del IEEE, diciembre de 2003.
  • Una alternativa al algoritmo Baum-Welch, el algoritmo de conteo de caminos de Viterbi:
    • Davis, Richard IA; Lovell, Brian C.; "Comparación y evaluación de algoritmos de entrenamiento de conjuntos HMM utilizando criterios de entrenamiento y prueba y número de condición" , Pattern Analysis and Applications, vol. 6, n.º 4, págs.  327–336, 2003.
  • Una hoja de cálculo interactiva para enseñar el algoritmo de avance-retroceso (hoja de cálculo y artículo con instrucciones paso a paso).
  • Derivación formal del algoritmo de Baum-Welch. Archivado el 28 de febrero de 2012 en la Wayback Machine.
  • Implementación del algoritmo de Baum-Welch