MEME

Multiple EM for Motif Elicitation ( MEME ) es un algoritmo y una herramienta del mismo nombre, que es una implementación del algoritmo, para buscar motivos en secuencias biológicas de proteínas y ADN . El algoritmo se basa en la aplicación repetida del método de máxima verosimilitud . Un motivo es una secuencia corta de nucleótidos o aminoácidos que es común a algún conjunto de secuencias.

La búsqueda de motivos es una tarea importante en biología, ya que la presencia de un motivo en una secuencia puede servir como señal para el reconocimiento de secuencias de factores de transcripción o endonucleasas de restricción [1] .

Historia

El algoritmo MEME fue desarrollado en 1994 por Timothy Bailey y Charles Elkan [2] . Es una extensión del método de máxima verosimilitud para encontrar motivos , que fue publicado en 1990 por Lawrence y Reilly [3] . El método original hizo posible encontrar un solo motivo en un conjunto de secuencias, y este motivo fue localmente óptimo, ya que el algoritmo depende en gran medida de la elección de los parámetros iniciales. La corrección de su funcionamiento también dependía en gran medida del nivel de ruido en las secuencias consideradas. El método MEME hizo posible eludir estas deficiencias. En 1996, se creó un servidor web que contenía una implementación de MEME, que fue utilizado por alrededor de 800 visitantes únicos entre 2000 y 2006 [4] . Y en 2009, se presentó el paquete MEME Suite, que contiene no solo la implementación de MEME, sino también muchos otros programas relacionados [5] . En total, las siguientes personas trabajaron en la creación de MEME Suite: Timothy Bailey, William Stafford Nobel, Charles Elkan y Michael Gribskov también contribuyeron al proyecto. A partir de 2017, MEME Suite cuenta con el respaldo de una subvención del NIH , y el servidor web también recibe ayuda de Google y Amazon [6] .

Planteamiento del problema

Es necesario identificar uno o más motivos comunes en un conjunto de secuencias de nucleótidos o aminoácidos desalineadas, cada una de las cuales contiene uno, más o ningún motivo. En este caso, consideramos motivos sin lagunas (gaps) que tienen una función biológica común. Por ejemplo, pueden ser dianas de una única proteína de unión al ADN. MEME utiliza la representación de un motivo biológico en forma de matriz de posición-peso (PWM) [2] .

Etapa preparatoria

Preparando secuencias

No es posible detectar un motivo común en ningún conjunto de secuencias, por lo tanto, para que el algoritmo funcione correctamente, las secuencias deben seleccionarse y prepararse cuidadosamente: debe esperarse un motivo común en este conjunto (por ejemplo, se sabe que las secuencias se unen a un solo factor de transcripción ), y las secuencias deben ser tan cortas como sea posible (idealmente <1000 nucleótidos ) [4] .

Elección de parámetros de entrada

De forma predeterminada, la salida MEME no contiene más de tres motivos de longitud de 6 a 50, que se encuentran tanto en la cadena directa como en la inversa de las secuencias de entrada [6] . Si se conoce el significado biológico de los objetos de búsqueda, entonces se puede adivinar y establecer el número y la duración de los motivos que se esperan en este conjunto de secuencias. Esto mejorará la calidad de la predicción en caso de que el motivo no se ajuste a los parámetros predeterminados [4] .

Algoritmo

Algoritmo EM para encontrar secuencias

La entrada al algoritmo EM es:

un conjunto de secuencias pertenecientes al alfabeto ; $L$
la duración del motivo alegado [3] . $W$

El algoritmo devuelve un posible modelo del motivo encontrado [3] .

En cada paso del algoritmo, el motivo está determinado por una matriz de peso de posición (PWM) de tamaño , donde es el tamaño del alfabeto. Cada celda del PVM tiene un peso que depende de la probabilidad de que aparezca una letra en la columna , donde . Estos valores se recalculan durante cada iteración del algoritmo [3] . ${\ estilo de visualización | L | \ veces W}$ $|L|$ ${\ Displaystyle p_ {lc}}$ $yo$ $C$ ${\ estilo de visualización 1 \ leq c \ leq W}$

Dado que inicialmente se desconoce en qué parte de las secuencias se encuentra exactamente el motivo, en cada paso del algoritmo se calculan los valores de la matriz , donde el elemento de la matriz es la probabilidad de que el motivo comience en la secuencia desde la posición [3 ] . $Z$ $z_{{ij}}$ $i$ $j$

Así, el algoritmo consta de la siguiente secuencia de pasos:

Se toma el PVM inicial del motivo. Se puede dar o elegir al azar.
Con base en los valores SMP disponibles para cada posición en cada secuencia, los valores de la matriz se calculan utilizando el logaritmo de la función de verosimilitud : ${\ Displaystyle p_ {lc}}$ $Z$ Iniciar sesión ⁡ ( yo i k mi yo i h o o d ) = norte ∑ j = una W ∑ yo ∈ L F yo j Iniciar sesión ⁡ ( pags yo j ) + norte ( k − W ) ∑ yo ∈ L F yo 0 Iniciar sesión ⁡ ( pags yo 0 ) + norte Iniciar sesión ⁡ ( una k − W + una ) , {\displaystyle \log(probabilidad)=N\sum_{j=1}^{W}\sum_{l\in L}f_{lj}\log(p_{lj})+N(KW)\sum _{l\in L}f_{l0}\log(p_{l0})+N\log({\frac {1}{K-W+1))),} $\log(probabilidad)=N\sum_{j=1}^{W}\sum_{l\in L}f_{lj}\log(p_{lj})+N(KW)\sum _{l\in L}f_{l0}\log(p_{l0})+N\log({\frac {1}{K-W+1))),$ donde es el número de secuencias de entrada, es la longitud de las secuencias de entrada, es la longitud del motivo, es el alfabeto, es la probabilidad de que una letra aparezca en la posición del motivo, es la probabilidad de que la letra aparezca en cualquier posición, es la frecuencia observada de la letra en la posición del motivo, es la frecuencia observada de la letra en cualquier posición. $norte$ $k$ $W$ $L$ $p_{lj}$ $yo$ $j$ $p_{l0}$ $yo$ $f_{lj}$ $yo$ $j$ ${\ Displaystyle f_ {l0}}$ $yo$
Para cada secuencia, el máximo de la función de verosimilitud se selecciona de la matriz y se determina la posición en la secuencia correspondiente a este máximo. Se construye la alineación según las posiciones correspondientes, se calculan nuevos valores del PWM según la aparición de letras en las columnas deseadas del motivo [3] . $Z$
Los puntos 2. y 3. se repiten hasta que los cambios en los valores del PVM sean inferiores al umbral establecido inicialmente [3] .

Cálculo de los mejores parámetros de entrada para el algoritmo MEME

Para mejorar el resultado del algoritmo EM, es necesario elegir el conjunto correcto de parámetros iniciales. Hay varias maneras de hacer esto:

Ejecute el algoritmo con varias entradas arbitrarias posibles y luego elija aquellas para las que la función de probabilidad sea la más grande. Este enfoque mejora la calidad de la predicción, pero no garantiza un mejor resultado [3] [7] .
Utilice el método de la subsecuencia [8] .

El método de subsecuencias se basa en el hecho de que el motivo deseado debe corresponder a alguna subsecuencia de longitud en los datos originales. Para cada subsecuencia de este tipo, se construyen PVM, a partir de los cuales comienza cada lanzamiento del algoritmo EM. El mayor valor de la función de probabilidad entre todas las ejecuciones del algoritmo será el máximo global y dará el motivo deseado. Es este principio el que limita la búsqueda de motivos con lagunas [8] . $W$

De acuerdo con una subsecuencia dada, un PSM se puede construir de varias maneras. El algoritmo MEME usa lo siguiente: la frecuencia de la letra correspondiente a la letra en la subsecuencia se toma como , el algoritmo funciona mejor para . Y las probabilidades para todas las demás letras se toman como [8] . ${\ estilo de visualización 0<X<1}$ $0{,}4\leq X\leq 0{,}8$ ${\frac{1-X}{|L|-1}}$

Resulta que al momento de ejecutar el algoritmo para una subsecuencia correspondiente al motivo correcto, el algoritmo EM converge tan rápidamente que una iteración es suficiente. Por lo tanto, para ahorrar tiempo, basta con ejecutar solo una iteración del algoritmo EM cada vez, que se implementa en el algoritmo MEME [8] .

Algoritmo MEME

El algoritmo MEME se basa en la aplicación repetida del algoritmo EM para buscar un motivo en secuencias. La entrada al algoritmo MEME es:

un conjunto de secuencias pertenecientes al alfabeto ; $L$
la duración del motivo alegado ; $W$
el número esperado de copias del motivo;
el número de motivos diferentes [8] .

El algoritmo EM se modifica a lo siguiente:

Los parámetros iniciales se eligen por el método de la subsecuencia.
Para cada conjunto de parámetros de entrada, se realiza una iteración del algoritmo EM. El mayor valor de la función de probabilidad se selecciona de todas las ejecuciones.
El motivo resultante se guarda y se elimina de las secuencias de entrada para buscar las siguientes.
Los ítems 1., 2. y 3. se repiten para buscar un determinado número de motivos [8] .

Los motivos descubiertos a la salida del programa se dan en forma de LOGO .

Tiempo de ejecución del algoritmo

El algoritmo de búsqueda de motivo de longitud MEME toma pasos, donde es una constante desconocida (entre 10 y 100), es el número total de letras del alfabeto dado en las secuencias de entrada [9] . Es decir, la complejidad del algoritmo resulta ser . $W$ ${\ Displaystyle k*W*n^{2))$ $k$ $norte$ ${\ estilo de visualización O (W * n ^ {2})}$

Ventajas

A diferencia de EM, MEME le permite trabajar y encontrar motivos de manera eficiente en secuencias que contienen más de una copia de un motivo o que no contienen un motivo. Estos últimos son considerados por el algoritmo como ruido [8] . Una gran ventaja es también la capacidad de buscar varios motivos diferentes en un conjunto de secuencias de entrada [8] y buscar un motivo óptimo global, mientras que EM a menudo se detiene en uno localmente óptimo, que puede no ser un motivo en absoluto [10 ] . Hay una implementación del algoritmo en forma de un programa para una PC y un servidor web con una interfaz conveniente con un conjunto de programas adicionales para seguir trabajando con el motivo encontrado [9] .

Desventajas

El algoritmo MEME reconoce pobremente motivos en secuencias largas, además, una gran longitud de secuencias aumenta considerablemente el tiempo de ejecución del algoritmo [4] [9] . Además, el algoritmo MEME hace una suposición básica importante sobre la equiprobabilidad de la ocurrencia de un motivo en cualquier parte de la secuencia. Este enfoque no es adecuado para buscar un motivo en secuencias de ARN , ya que forman estructuras secundarias y terciarias, lo que hace que la aparición de un motivo sea más o menos probable según la estructura [11] . El algoritmo no permite encontrar motivos con huecos, ya que la propia formulación del problema del algoritmo no implica buscarlos.

Implementación del algoritmo

En base a este algoritmo se implementa la herramienta MEME Suite, disponible en versión web y para PC [6] , a partir del 2017 se encuentra soportada y actualizada.

Notas

↑ Patrik D'haeseleer. ¿Qué son los motivos de secuencia de ADN? (Inglés) // Nature Biotechnology. - 2006-04-01. — vol. 24 , edición. 4 . — págs. 423–425 . — ISSN 1087-0156 . -doi : 10.1038/ nbt0406-423 . Archivado desde el original el 12 de abril de 2017.
↑ 1 2 TL Bailey, C. Elkan. Ajuste de un modelo de mezcla por maximización de expectativas para descubrir motivos en biopolímeros // Procedimientos. Congreso Internacional de Sistemas Inteligentes para Biología Molecular. — 1994-01-01. - T. 2 . — P. 28–36 . — ISSN 1553-0833 . Archivado desde el original el 24 de abril de 2017.
↑ 1 2 3 4 5 6 7 8 Charles E. Lawrence, Andrew A. Reilly. Un algoritmo de maximización de expectativas (EM) para la identificación y caracterización de sitios comunes en secuencias de biopolímeros no alineadas // Proteínas: estructura, función y bioinformática. — 1990-01-01. — vol. 7 , edición. 1 . — págs. 41–51 . — ISSN 1097-0134 . -doi : 10.1002/ prot.340070105 . Archivado desde el original el 15 de abril de 2017.
↑ 1 2 3 4 Timothy L. Bailey, Nadya Williams, Chris Misleh, Wilfred W. Li. MEME: descubrimiento y análisis de motivos de secuencias de ADN y proteínas // Investigación de ácidos nucleicos. - 2006-07-01. - T. 34 , n. supl_2 . — S. W369–W373 . — ISSN 0305-1048 . doi : 10.1093 / nar/gkl198 . Archivado desde el original el 15 de abril de 2017.
↑ Timothy L. Bailey, Mikael Boden, Fabian A. Buske, Martin Frith, Charles E. Grant. MEME Suite: herramientas para el descubrimiento y búsqueda de motivos // Investigación de ácidos nucleicos. — 2009-07-01. - T. 37 , n. Problema con el servidor web . — C. W202–W208 . — ISSN 0305-1048 . -doi : 10.1093 / nar/gkp335 . Archivado desde el original el 11 de diciembre de 2019.
↑ 1 2 3 Introducción - MEME Suite . meme-suite.org. Consultado el 14 de abril de 2017. Archivado desde el original el 26 de abril de 2017. (indefinido)
↑ Algoritmo de maximización de expectativas para identificar sitios de unión a proteínas con longitudes variables de fragmentos de ADN no alineados: ScienceDirect . www.sciencedirect.com. Fecha de acceso: 15 de abril de 2017.
↑ 1 2 3 4 5 6 7 8 Timothy L. Bailey, Charles Elkan. Aprendizaje no supervisado de múltiples motivos en biopolímeros utilizando la maximización de expectativas // Aprendizaje automático. — 1995-10-01. — vol. 21 , edición. 1-2 . — págs. 51–80 . -doi : 10.1023/A : 1022617714621 .
↑ 1 2 3 The MEME Suite: un conjunto de herramientas para encontrar motivos . Suite MEME . rothlab.ucdavis.edu. Consultado el 14 de abril de 2017. Archivado desde el original el 8 de febrero de 2017. (indefinido)
↑ AP Dempster, N. M. Laird, D. B. Rubin. Máxima probabilidad de datos incompletos a través del algoritmo EM // Revista de la Royal Statistical Society. Serie B (Metodológica). — 1977-01-01. - T. 39 , n. 1 . — Pág. 1–38 . Archivado desde el original el 19 de julio de 2017.
↑ Avinash Achar, Pål Sætrom. Descubrimiento de motivos de ARN: una descripción general computacional // Biology Direct. — 2015-01-01. - T. 10 . - art. 61 . — ISSN 1745-6150 . -doi : 10.1186/ s13062-015-0090-5 .