Motivos de Markov ocultos (HMM)
Motivos de Markov ocultos (HMM)
Los HMM son modelos probabilísticos de una secuencia
Motivos de Markov ocultos (HMM)
HMM = cadena de Markov + modelo multinomial
Motivos de Markov ocultos (HMM)
Cada posición de la cadena de Markov está en un estado oculto
Motivos de Markov ocultos (HMM)
Segmentation: Gene and protein sequences may contain distinct regions whose chemical properties differ widely. HMMs can help us to define the exact boundaries of these regions.
Multiple alignment: From a MSA, a so-called profile HMM can be defined against which all new sequences can be
aligned. These profile HMMs also make it possible to assign protein function quickly, and can be regarded both as a
summary of a MSA and as a model for a family of sequences.
Prediction of function: HMMs allow us to make probabilistic statements about the function of proteins, or
let us assign proteins to families of unknown function.
Aplicaciones biológicas de los HMM
Gene finding: If we wish to find eukaryotic genes or pseudogenes we require the flexibility of HMMs.
Motivos de Markov ocultos (HMM)
Probabilidades de transición y de emisión
Motivos de Markov ocultos (HMM)
Los parámetros que definen un HMM
Motivos de Markov ocultos (HMM)
Ejemplo 1: el casino de Nuncaganarás
Probabilidades de emisión
Probabilidades de transición
Motivos de Markov ocultos (HMM)
Los estados ocultos
Conociendo las probabilidades de emisión y de transición se puede determinar la secuencia
más probable de motivos ocultos que ha originado la secuencia observada, es decir, qué dado se ha utilizado en cada tirada
Motivos de Markov ocultos (HMM)
Nature Biotechnology 22 (2004): 1315-1316
Motivos de Markov ocultos (HMM)
Ejemplo 2: separación de exones e intrones
Motivos de Markov ocultos (HMM)
Los estados ocultos más probables: el algoritmo de Viterbi
Motivos de Markov ocultos (HMM)
La secuencia más probable : el algoritmo de avance
Motivos de Markov ocultos (HMM)
Perfiles HMM
Motivos de Markov ocultos (HMM)
A partir de un AMS se puede obtener un perfil HMM
Motivos de Markov ocultos (HMM)
El problema de las expresiones regulares
[AT]-[CG]-[AC]-[ACTG]*-A-[TG]-[GC]Expresión regular:
TGCT - - AGGACAC - - ATCSecuencia consenso Secuencia muy improbable
AMS
Motivos de Markov ocultos (HMM)
Modelo de Markov oculto obtenido a partir del AMS
Los recuadros contienen las
probabilidades de emisión de cada estado
Las flechas indican las
probabilidades de transición de un estado a otro
A partir del AMS se calculan las
probabilidades de transición y de
emisión del modelo
Hay dos estados posibles: estado principal
y estado de inserción (enmarcado en rojo)
Motivos de Markov ocultos (HMM)
HMM = Modelo probabilístico
El HMM permite calcular la probabilidad de que una
secuencia determinada se ajuste al modelo
Motivos de Markov ocultos (HMM)
El HMM permite otorgar una puntuación (que, en realidad, es una probabilidad) a cada secuencia, en función de lo bien o mal que se ajustan al modelo
HMM = Sistema de puntuación
La secuencia excepcional es 2000 veces más improbable que la secuencia consenso
Motivos de Markov ocultos (HMM)
Log odds = logaritmo del cociente de probabilidades
La probabilidad no es la mejor forma de reflejar la puntuación porque depende en gran medida de la
longitud de la secuencia. Es mejor usar el log odds.
Odds =Probabilidad de que la secuencia S se ajuste al HMM
Probabilidad de que S se deba al simple azar (null model)
Motivos de Markov ocultos (HMM)
Las probabilidades de emisión del HMM se
convierten en log odds
Las probabilidades de transición se convierten
en logaritmos
Log odds score: los logaritmos se suman (no se multiplican)
Motivos de Markov ocultos (HMM)Cuando una secuencia se ajusta al modelo, su log-odds score es elevado.
Cuando el modelo neutro (null model) es mejor, el
log-odds es negativo.
Según el cálculo de probabilidades, la secuencia original nº 2 y la secuencia excepcional tienen una puntuación parecida. Sin embargo, el log odds de la secuencia original del alineamiento
es mucho mayor. El log odds tiene mayor poder discriminatorio.
Log odds score vs. probabilidades
Motivos de Markov ocultos (HMM)
Los perfiles HMM permiten caracterizar una familia de proteínas
Motivos de Markov ocultos (HMM)
Un perfil HMM se construye a partir de un AMS
Motivos de Markov ocultos (HMM)
Los distintos estados (ocultos) de un perfil HMM
Estados principales (uno por cada columna de la secuencia ancestral). Cada estado tiene unas probabilidades de emisión distintas.
Estados de inserción que introducen caracteres en el alineamiento (tiene sus propias probabilidades de emisión )
Estados de eliminación que permiten saltar de una posición del alineamiento a otra (no emiten caracteres)
Begin EndEstados obligatorios que marcan el inicio y el final del modelo (no emiten caracteres)
Motivos de Markov ocultos (HMM)
Transiciones de un estado oculto a otro
Secuencia similar a la ancestral (ADGK)
Secuencia con dos huecos en el medio
Secuencia con un hueco al final
Secuencia con dos inserciones en el medio
Motivos de Markov ocultos (HMM)
Cálculo de las probabilidades de emisión y de transición
Para construir el perfil HMM hay que determinar las probabilidades de emisión de cada estado y las probabilidades de transición de un estado a otro. Como estos datos no se conocen, hay que
estimarlos a partir de un AMS.
Lo ideal es partir de un AMS que incluya entre 20 y 100 secuencias homólogas.
Motivos de Markov ocultos (HMM)
Alineamiento de 30 secuencias (dominio SH3)
Main state (1-6)
Main state (7-14)
Indel state
Begin to delete
transition
Main to delete
transition
Main to insert
transition
Insert to main
transition
Motivos de Markov ocultos (HMM)Estado principal (posiciones 1-6)
Estado principal (posiciones 7-14)
Indel state
Perfil HMM correspondiente al alineamiento anterior
Motivos de Markov ocultos (HMM)
Pseudocuentas (1)
En el perfil HMM hay muchos aminoácidos que no están
representados (Paa=0)
Para evitar multiplicar por cero (o el logaritmo de cero) se añaden
pseudocuentas a las probabilidades de emisión de cada estado principal
Motivos de Markov ocultos (HMM)
Pseudocuentas (2)
Una forma de añadir pseudocuentas es sumar 1 a todos los aminoácidos en todas las columnas
También se puede añadir a cada aminoácido un número de pseudocuentas que sea proporcional a su abundancia relativa.
También se puede añadir a cada aminoácido un número de pseudocuentas calculado teniendo en cuenta las sustituciones
más probables en cada posición de la columna (para ello se utiliza una matriz de sustitución como PAM-50 o BLOSUM-62.
Motivos de Markov ocultos (HMM)
Búsquedas en BD con un perfil HMM
Motivos de Markov ocultos (HMM)
Puntuación del alineamiento: Algoritmos de Viterbi y de avance
Motivos de Markov ocultos (HMM)
Distribución de los resultados tras una búsqueda en una BD
Motivos de Markov ocultos (HMM)
Ventajas de los HMM
1.- Realiza AMS tan buenos o mejores que otros métodos
2.- Para hacer AMS no hay que ordenar las secuencias
3.- Es un método sólidamente basado en la teoría de probabilidad
5.- Puede incluir información obtenida experimentalmente:
* Longitud de la secuencia
4.- No hace falta estimar la penalización por indels
* Número, longitud y posición de los indels
* Las frecuencias de los aminoácidos en cada posición
Motivos de Markov ocultos (HMM)
Inconvenientes de los HMM (1)
1.- Hay que estimar un número muy elevado de parámetros:
* Longitud de la secuencia
* Número, longitud y posición de los indels
* Las frecuencias de los aminoácidos en cada posición
* La probabilidad asociada a cada transición de un estado a otro
Por tanto, hace falta:
- un número elevado de secuencias (más de 50) para que el modelo “se entrene” y sea capaz de calcularlos
- Una estimación inicial de todos esos parámetros (prior conditions) para comenzar el ciclo de iteraciones
Cuanto mejor sea la estimación inicial, menor será el número de secuencias necesarias para entrenar el modelo
Motivos de Markov ocultos (HMM)
2.- Es peligroso estimar la distribución de probabilidades de los aminoácidos (aa) a partir de unas pocas secuencias. Para evitar sacar conclusiones importantes a partir de un escaso número de observaciones, se recurre a las pseudocuentas: se aumenta de forma artificial el número de veces que se observa cada aa en cada columna.
Hay varias formas de añadir pseudocuentas:
* Añadir uno a todos los aa (implica que todos pueden presentarse con la misma probabilidad)
* Añadir a cada aa un número proporcional a la frecuencia observada (se admite que no todos los aa aparecen con la misma frecuencia)
* Añadir a cada aa un número de cuentas que refleje la información contenida en una matriz de sustitución (PAM, BLOSUM)
Inconvenientes de los HMM (2)
Motivos de Markov ocultos (HMM)
3.- Es importante que el modelo no sólo refleje las características de las secuencias iniciales, sino también las variaciones que puedan presentar otros miembros de la familia. Si no, será un modelo “superentrenado” que sólo será capaz de reconocer a las secuencias iniciales.
Para evitarlo se recurre a un proceso denominado regularización: Se parte de una distribución de aa cuidadosamente diseñada (mezclas Dirichlet), que se va modificando a medida que el modelo “se entrena”.
Así se genera un modelo más representativo de la familia de proteínas a la que pertenece el conjunto inicial de secuencias porque admite un grado razonable de variaciones que se puedan presentar en secuencias relacionadas.
Inconvenientes de los HMM (3)
Motivos de Markov ocultos (HMM)
4.- A medida que el modelo se entrena y se va ajustando a las secuencias iniciales, es posible que el proceso quede “atrapado” en una solución que se limita a un alineamiento óptimo local en vez de a uno global.
Este problema se puede evitar mediante métodos que inyectan “ruido estadístico” al sistema, como el simulated annealing: En cada ciclo se genera un número de secuencias definido por el usuario y las cuentas (las veces que aparece cada aa en cada posición) se añaden a las de las secuencias iniciales. El ruido generado por este procedimiento disminuye a medida que aumenta el número de ciclos.
Inconvenientes de los HMM (4)
Motivos de Markov ocultos (HMM)
Aplicaciones de los HMM
Motivos de Markov ocultos (HMM)
¿Para qué sirven los HMM?
3.- Para hacer alineamientos múltiples de secuencias (AMS)
4.- Para mejorar AMS obtenidos mediante otros métodos
5.- Para analizar secuencias y generar perfiles HMM característicos de una familia de proteínas
7.- Para predecir genes (predice promotores, los lugares de unión al ribosoma, los ORF, regiones codificantes y no codificantes, las fronteras intrón/exón, etc.)
1.- Para predecir la estructura secundaria de proteínas
6.- Para buscar en las BD más miembros de una familia
2.- Para predecir secuencias señal en proteínas
Motivos de Markov ocultos (HMM)
Predicción de genes mediante HMM (la teoría)
Motivos de Markov ocultos (HMM)
Predicción de genes mediante HMM (la realidad)
Motivos de Markov ocultos (HMM)
Predicción de genes eucariotas usando HMM
http://genes.mit.edu/GENSCAN.html
Motivos de Markov ocultos (HMM)
Predicción de genes
Motivos de Markov ocultos (HMM)
http://opal.biology.gatech.edu/eukhmm.cgi
Predicción de genes eucariotas usando HMM
Motivos de Markov ocultos (HMM)
http://compbio.soe.ucsc.edu/SAM_T08/T08-query.html
Predicción de la estructura secundaria de proteínas
Introduce una secuencia proteica en formato FASTA
Introduce una dirección de E-mail
Motivos de Markov ocultos (HMM)
http://www.cbs.dtu.dk/services/TMHMM-2.0/
Predicción de hélices transmembrana usando HMM
Motivos de Markov ocultos (HMM)
Predicción de hélices transmembrana usando HMM
http://www.enzim.hu/hmmtop/
Motivos de Markov ocultos (HMM)
Búsquedas en BD basadas en HMM
http://hmmer.janelia.org/
Motivos de Markov ocultos (HMM)
Software para construir HMM
http://compbio.soe.ucsc.edu/sam.html
Motivos de Markov ocultos (HMM)
Software para construir HMM
http://pgfe.umassmed.edu/meme/metameme-intro.html