Expectation Maximization (EM) algorithm es usado para estimar motivos consenso en un set de secuencias dado, basándose en un modelo probabilístico en el que diferenciamos dos componentes:
- El motivo común en si.
- El resto de posiciones que no pertenecen al motivo: background.
Consta básicamente de tres pasos:
- Paso O: Inicialización.
- Se selecciona una posición random para cada secuencia a partir de la cual empezará el motivo, de longitud escogida.
- Se alinean los motivos y se calculan las matrices de pesos del motivo y del background por primera vez.
- Paso E: Elección del primer candidato para cada una de las secuencias.
- Mediante las matrices damos una puntuación a cada motivo candidato.
- Normalizar las matrices
- Se escoge el más probable con respecto a la puntuación de los demás candidatos de cada secuencia.
- Paso M: Maximización de la calidad del resultado.
- Actualizar las matrices de pesos del motivo y del background con cada candidato.
- Normalizar las matrices.
Una vez realizados estos tres pasos se repiten los pasos E y M.
El algoritmo se detiene cuando se produce convergencia de los resultados, es decir, cuando tras múltiples iteraciones de los pasos E y M, la calidad no mejora. Esto se realizará mediante un sencillo cálculo que compare la matriz de scores de cada iteración con la de la iteración anterior.
Otro sistema de parar el algoritmo es poner un límite máximo de iteraciones, de modo que cuando llegue a tal límite se detenga. Normalmente se combinan ambos sistemas de forma que se detenga cuando se produzca uno de los dos.
Este es el esquema básico del EM Algorithm, si aún tienes más interés y quieres saber como nuestro programa resuelve cada punto solo tienes que acceder al mismo, donde encontrarás notas explicativas de los pasos que sa van ejecutando.
Ejemplos de la utilización del programa
Aquí dispones de uno de los archivos que tu mismo puedes utilizar como prueba para ejecutar el programa y del cual hemos extraído los ejemplos que mostramos a continuación. Para encontrar todas las secuencias que necesites acude a la sección de bibliografía donde encontrarás links interesantes.
Este es un ejemplo de la tabla de resultados con los candidatos de mayor puntuación de cada secuencia para motivos de 4 y 7 nucleótidos respectivamente obtenidos con un valor de convergencia de 0'01. La columna posición corresponde a la posición del primer nucleótido del motivo teniendo en cuenta que empezamos a contar desde el nucleótido 0 de la secuencia correspondiente.
También encontramos las matrices de scores correspondientes donde nos muestra el score asociado a cada nucleótido según la posición que ocupa en el motivo, de esta tabla hay que destacar que a veces aparecen nucleótidos con puntuaciónes positivas que no están respresentados en los motivos, esto se debe a que en la tabla sólo aparecen aquellos que tienen la puntuación máxima en cada secuencia, es decir que es posible que aparezcan en motivos cuya puntación es menor.
Por último se muestra un ejemplo de la representaci&avute;n gráfica obtenida. En el recuadro de color aparecen los motivos obtenidos en cada secuencia flanqueados por las 15 posiciones anteriores y posteriores, el número que aparece sobre cada secuencia corresponde a la posici&oacut;n -15 respecto del inicio del motivo.
Resultados obtenidos para un motivo de 4 nucleótidos.
Resultados obtenidos para un motivo de 7 nucleótidos.
- Se selecciona una posición random para cada secuencia a partir de la cual empezará el motivo, de longitud escogida.
- Se alinean los motivos y se calculan las matrices de pesos del motivo y del background por primera vez.
- Mediante las matrices damos una puntuación a cada motivo candidato.
- Normalizar las matrices
- Se escoge el más probable con respecto a la puntuación de los demás candidatos de cada secuencia.
- Actualizar las matrices de pesos del motivo y del background con cada candidato.
- Normalizar las matrices.
Aquí dispones de uno de los archivos que tu mismo puedes utilizar como prueba para ejecutar el programa y del cual hemos extraído los ejemplos que mostramos a continuación. Para encontrar todas las secuencias que necesites acude a la sección de bibliografía donde encontrarás links interesantes.
|
Este es un ejemplo de la tabla de resultados con los candidatos de mayor puntuación de cada secuencia para motivos de 4 y 7 nucleótidos respectivamente obtenidos con un valor de convergencia de 0'01. La columna posición corresponde a la posición del primer nucleótido del motivo teniendo en cuenta que empezamos a contar desde el nucleótido 0 de la secuencia correspondiente. También encontramos las matrices de scores correspondientes donde nos muestra el score asociado a cada nucleótido según la posición que ocupa en el motivo, de esta tabla hay que destacar que a veces aparecen nucleótidos con puntuaciónes positivas que no están respresentados en los motivos, esto se debe a que en la tabla sólo aparecen aquellos que tienen la puntuación máxima en cada secuencia, es decir que es posible que aparezcan en motivos cuya puntación es menor. Por último se muestra un ejemplo de la representaci&avute;n gráfica obtenida. En el recuadro de color aparecen los motivos obtenidos en cada secuencia flanqueados por las 15 posiciones anteriores y posteriores, el número que aparece sobre cada secuencia corresponde a la posici&oacut;n -15 respecto del inicio del motivo. |
| Resultados obtenidos para un motivo de 4 nucleótidos. |
|
|
|
| Resultados obtenidos para un motivo de 7 nucleótidos. |
|
|
|
Descarga el programa
El programa que puedes descargarte aquí funciona ligeramente diferente al que se ejecuta desde el navegador.
Los pasos a seguir para ejecutar el programa en tu propio ordenador son los siguientes;
- Descarga el programa aquí
- Una vez guardado en tu ordenador abre el terminal y cambia los derechos de ejecución con el comando: chmod u+x emb.pl
- Ahora sólo queda ejecutar el programa escribiendo: ./emb.pl "nombre del archivo"
- El programa leerá directamente el archivo con las secuencias siempre y cuando esté en formato fasta y además se encuentre en el mismo directorio que el programa
- Una vez comienza la ejecución aparecerá un mensaje que nos pide la longitud deseada para el motivo
- Immediatamente después el programa nos pide el umbral a partir del cual consideramos que la matriz M ha llegado a un punto de convergencia.
Resultados:
Cuando ejecutes el programa una vez te lo hayas bajado, verás aparecer una serie de mensajes a través de tu pantalla desde el terminal:
- Leyendo fichero:
- Escribe la longitud del motivo
- Escribe la similitud minima entre las matrices de score para detener las iteraciones por convergencia
- Y el número de iteraciones que va realizando.
Vas a recuperar los resultador a partir de dos tipos de fichero diferente:
- El archivo resultat.txt: Por un lado te va a situar, indicándote el archivo analizado, la longitud del motivo y la similitud mínima seleccionada para la convergencia. Por otro lado va a proporcionarte la información necesaria para tu análisis:
- Matriz con la frecuencia de cada nucleotido segun su posición en los motivos.
- Una tabla con el motivo seleccionado como candidato más probable, relacionándolo con la secuencia a la que pertenece y su score y posición dentro de esa secuencia.
- Matriz de scores.
- El archivo resultat.html: De nuevo te va a situar para que conozcas a que pertenecen estos resultados, indicándote el archivo analizado, la longitud del motivo y la similitud mí:nima seleccionada para la convergencia. Además de una serie de tablas con la información anterior y, finalmete, una representación gráfica de los resultados.En la tabla resumen con los motivos encontrados sólo se mostrarán aquellos cuya puntuación sea positiva mientras que en la representación gráfica se muestra el candidato de mayor puntuación de cada secuencia, sea esta puntuación positiva o no.
- El canal de error: Otro tipo de información que te va a llegar or el terminal son mensajes de posibles errores provocados por una ejecución incorrecta del programa, y son:
- Para que el programa se ejecute correctamente escribe :./em.pl "nombre del fichero": te indica cómo debes ejecutar el programa sobre el fichero deseado.
- El programa no puede abrir el fichero. Asegúrese que ambos se encuentran en el mismo directorio.
Los pasos a seguir para ejecutar el programa en tu propio ordenador son los siguientes;
- Descarga el programa aquí
- Una vez guardado en tu ordenador abre el terminal y cambia los derechos de ejecución con el comando: chmod u+x emb.pl
- Ahora sólo queda ejecutar el programa escribiendo: ./emb.pl "nombre del archivo"
- El programa leerá directamente el archivo con las secuencias siempre y cuando esté en formato fasta y además se encuentre en el mismo directorio que el programa
- Una vez comienza la ejecución aparecerá un mensaje que nos pide la longitud deseada para el motivo
- Immediatamente después el programa nos pide el umbral a partir del cual consideramos que la matriz M ha llegado a un punto de convergencia.
Resultados:
Cuando ejecutes el programa una vez te lo hayas bajado, verás aparecer una serie de mensajes a través de tu pantalla desde el terminal:
- Leyendo fichero:
- Escribe la longitud del motivo
- Escribe la similitud minima entre las matrices de score para detener las iteraciones por convergencia
- Y el número de iteraciones que va realizando.
- El archivo resultat.txt: Por un lado te va a situar, indicándote el archivo analizado, la longitud del motivo y la similitud mínima seleccionada para la convergencia. Por otro lado va a proporcionarte la información necesaria para tu análisis:
- Matriz con la frecuencia de cada nucleotido segun su posición en los motivos.
- Una tabla con el motivo seleccionado como candidato más probable, relacionándolo con la secuencia a la que pertenece y su score y posición dentro de esa secuencia.
- Matriz de scores.
- El archivo resultat.html: De nuevo te va a situar para que conozcas a que pertenecen estos resultados, indicándote el archivo analizado, la longitud del motivo y la similitud mí:nima seleccionada para la convergencia. Además de una serie de tablas con la información anterior y, finalmete, una representación gráfica de los resultados.En la tabla resumen con los motivos encontrados sólo se mostrarán aquellos cuya puntuación sea positiva mientras que en la representación gráfica se muestra el candidato de mayor puntuación de cada secuencia, sea esta puntuación positiva o no.
- El canal de error: Otro tipo de información que te va a llegar or el terminal son mensajes de posibles errores provocados por una ejecución incorrecta del programa, y son:
- Para que el programa se ejecute correctamente escribe :./em.pl "nombre del fichero": te indica cómo debes ejecutar el programa sobre el fichero deseado.
- El programa no puede abrir el fichero. Asegúrese que ambos se encuentran en el mismo directorio.