Los motivos de red son subgrafos o patrones recurrentes y estadísticamente significativos de un gráfico más grande . Todas las redes, incluidas las redes biológicas , las redes sociales, las redes tecnológicas (por ejemplo, redes informáticas y circuitos eléctricos) y más, se pueden representar como gráficos, que incluyen una amplia variedad de subgrafos.
Los motivos de red son subgrafos que se repiten en una red específica o incluso entre varias redes. Cada uno de estos subgrafos, definidos por un patrón particular de interacciones entre vértices, puede reflejar un marco en el que funciones particulares se logran de manera eficiente. De hecho, los motivos son de notable importancia en gran medida porque pueden reflejar propiedades funcionales. Lo han hecho recientemente [ ¿cuándo? ] atrajo mucha atención como un concepto útil para descubrir principios de diseño estructural de redes complejas. [1] Aunque los motivos de la red pueden proporcionar una visión profunda de las capacidades funcionales de la red, su detección es un desafío computacional.
Sean G = (V, E) y G′ = (V′, E′) dos gráficas. El gráfico G′ es un subgráfico del gráfico G (escrito como G′ ⊆ G ) si V′ ⊆ V y E′ ⊆ E ∩ (V′ × V′) . Si G′ ⊆ G y G′ contienen todas las aristas ⟨u, v⟩ ∈ E con u, v ∈ V′ , entonces G′ es un subgrafo inducido de G . Llamamos a G′ y G isomórficos (escritos como G′ ↔ G ), si existe una biyección (correspondencia uno a uno) f:V′ → V con ⟨u, v⟩ ∈ E′ ⇔ ⟨f(u) , f(v)⟩ ∈ E para todo u, v ∈ V′ . El mapeo f se llama isomorfismo entre G y G′ . [2]
Cuando G″ ⊂ G y existe un isomorfismo entre el subgrafo G″ y un gráfico G′ , este mapeo representa una aparición de G′ en G . El número de apariciones del gráfico G′ en G se llama frecuencia F G de G′ en G . Un gráfico se llama recurrente (o frecuente ) en G cuando su frecuencia F G (G′) está por encima de un umbral o valor de corte predefinido. Usamos los términos patrón y subgráfico frecuente en esta revisión indistintamente. Existe un conjunto Ω(G) de gráficos aleatorios correspondientes al modelo nulo asociado a G. Deberíamos elegir N gráficos aleatorios uniformemente de Ω (G) y calcular la frecuencia para un subgráfico frecuente particular G ′ en G. Si la frecuencia de G′ en G es mayor que su frecuencia media aritmética en N gráficos aleatorios Ri , donde 1 ≤ i ≤ N , llamamos significativo a este patrón recurrente y, por lo tanto , tratamos a G′ como un motivo de red para G. Para un gráfico pequeño G′ , la red G y un conjunto de redes aleatorias R(G) ⊆ Ω(R) , donde R(G) = N , la puntuación Z de la frecuencia de G′ viene dada por
donde μ R (G′) y σ R (G′) representan la media y la desviación estándar de la frecuencia en el conjunto R(G) , respectivamente. [3] [4] [5] [6] [7] [8] Cuanto mayor es Z(G′) , más significativo es el subgrafo G′ como motivo. Alternativamente, otra medida en la prueba de hipótesis estadística que se puede considerar en la detección de motivos es el valor p , dado como la probabilidad de F R (G′) ≥ F G (G′) (como su hipótesis nula), donde F R (G′) indica la frecuencia de G' en una red aleatoria. [6] Un subgráfico con un valor p inferior a un umbral (comúnmente 0,01 o 0,05) se tratará como un patrón significativo. El valor p para la frecuencia de G′ se define como
donde N indica el número de redes aleatorias, i se define sobre un conjunto de redes aleatorias y la función delta de Kronecker δ(c(i)) es uno si se cumple la condición c(i) . La concentración [9] [10] de un subgráfico particular de tamaño n G′ en la red G se refiere a la relación entre la apariencia del subgráfico en la red y el total de frecuencias de subgráficos no isomórficos de tamaño n , que está formulado por
donde el índice i se define sobre el conjunto de todos los gráficos de tamaño n no isomórficos. Se define otra medida estadística para evaluar motivos de red, pero rara vez se utiliza en algoritmos conocidos. Esta medida es introducida por Picard et al. en 2008 y utilizó la distribución de Poisson, en lugar de la distribución normal gaussiana que implícitamente se utiliza anteriormente. [11]
Además, se han propuesto tres conceptos específicos de frecuencia de subgráficos. [12] Como ilustra la figura, el primer concepto de frecuencia F 1 considera todas las coincidencias de un gráfico en la red original. Esta definición es similar a la que hemos introducido anteriormente. El segundo concepto F 2 se define como el número máximo de instancias de bordes disjuntos de un gráfico determinado en la red original. Y finalmente, el concepto de frecuencia F 3 implica coincidencias con aristas y nodos disjuntos. Por lo tanto, los dos conceptos F 2 y F 3 restringen el uso de elementos del gráfico y, como se puede inferir, la frecuencia de un subgráfico disminuye al imponer restricciones en el uso de elementos de red. Como resultado, un algoritmo de detección de motivos de red pasaría por alto más subgráficos candidatos si insistimos en los conceptos de frecuencia F 2 y F 3 .
El estudio de los motivos de las redes fue iniciado por Holland y Leinhardt [13] [14] [15] [16], quienes introdujeron el concepto de un censo de redes en tríada. Introdujeron métodos para enumerar varios tipos de configuraciones de subgrafos y probar si los recuentos de subgrafos son estadísticamente diferentes de los esperados en redes aleatorias.
Esta idea fue generalizada aún más en 2002 por Uri Alon y su grupo [17] cuando se descubrieron motivos de red en la red de regulación genética ( transcripción ) de la bacteria E. coli y luego en un gran conjunto de redes naturales. Desde entonces, se han realizado un número considerable de estudios sobre el tema. Algunos de estos estudios se centran en aplicaciones biológicas, mientras que otros se centran en la teoría computacional de motivos de redes.
Los estudios biológicos intentan interpretar los motivos detectados para las redes biológicas. Por ejemplo, en el trabajo siguiente, [17] los motivos de red encontrados en E. coli se descubrieron en las redes de transcripción de otras bacterias [18] , así como en levaduras [19] [20] y organismos superiores. [21] [22] [23] Se identificó un conjunto distinto de motivos de red en otros tipos de redes biológicas, como redes neuronales y redes de interacción de proteínas. [5] [24] [25]
La investigación computacional se ha centrado en mejorar las herramientas de detección de motivos existentes para ayudar en las investigaciones biológicas y permitir el análisis de redes más grandes. Hasta ahora se han proporcionado varios algoritmos diferentes, que se detallan en la siguiente sección en orden cronológico.
Más recientemente, se lanzó la herramienta acc-MOTIF para detectar motivos de red. [26]
Se han propuesto varias soluciones para el desafiante problema del descubrimiento de motivos de red (NM). Estos algoritmos se pueden clasificar según varios paradigmas, como métodos de conteo exacto, métodos de muestreo, métodos de crecimiento de patrones, etc. Sin embargo, el problema de descubrimiento de motivos comprende dos pasos principales: primero, calcular el número de apariciones de un subgráfico y luego, evaluar la importancia del subgráfico. La recurrencia es significativa si es detectable mucho mayor de lo esperado. En términos generales, el número esperado de apariciones de un subgráfico se puede determinar mediante un modelo nulo, que se define mediante un conjunto de redes aleatorias con algunas de las mismas propiedades que la red original.
Hasta 2004, el único método de conteo exacto para la detección de MN era el de fuerza bruta propuesto por Milo et al. . [3] Este algoritmo tuvo éxito para descubrir motivos pequeños, pero usar este método para encontrar motivos de tamaño 5 o 6 no era computacionalmente factible. Por tanto, era necesario un nuevo enfoque para este problema.
Aquí se ofrece una revisión de los aspectos computacionales de los principales algoritmos y se discuten sus ventajas e inconvenientes relacionados desde una perspectiva algorítmica.
La siguiente tabla enumera los algoritmos de descubrimiento de motivos que se describirán en esta sección. Se pueden dividir en dos categorías generales: los que se basan en un recuento exacto y los que utilizan muestreos y estimaciones estadísticas. Debido a que el segundo grupo no cuenta todas las apariciones de un subgrafo en la red principal, los algoritmos que pertenecen a este grupo son más rápidos, pero pueden producir resultados sesgados y poco realistas.
En el siguiente nivel, los algoritmos de conteo exactos se pueden clasificar en métodos centrados en redes y centrados en subgrafos. Los algoritmos de la primera clase buscan en la red dada todos los subgrafos de un tamaño determinado, mientras que los algoritmos de la segunda clase primero generan diferentes gráficos no isomórficos posibles del tamaño dado y luego exploran la red para cada subgrafo generado por separado. Cada enfoque tiene sus ventajas y desventajas que se analizan a continuación.
La tabla también indica si un algoritmo se puede utilizar para redes dirigidas o no dirigidas, así como para subgrafos inducidos o no inducidos. Para obtener más información, consulte los enlaces web o las direcciones de laboratorio proporcionados.
Kashtan et al. publicó mfinder , la primera herramienta de extracción de motivos, en 2004. [9] Implementa dos tipos de algoritmos de búsqueda de motivos: una enumeración completa y el primer método de muestreo.
Su algoritmo de descubrimiento de muestreo se basó en el muestreo de bordes en toda la red. Este algoritmo estima concentraciones de subgrafos inducidos y puede utilizarse para el descubrimiento de motivos en redes dirigidas o no dirigidas. El procedimiento de muestreo del algoritmo comienza desde un borde arbitrario de la red que conduce a un subgráfico de tamaño dos, y luego expande el subgráfico eligiendo un borde aleatorio que incide en el subgráfico actual. Después de eso, continúa eligiendo bordes vecinos aleatorios hasta que se obtiene un subgráfico de tamaño n. Finalmente, el subgráfico muestreado se expande para incluir todos los bordes que existen en la red entre estos n nodos. Cuando un algoritmo utiliza un enfoque de muestreo, tomar muestras imparciales es la cuestión más importante que el algoritmo podría abordar. Sin embargo, el procedimiento de muestreo no toma muestras de manera uniforme y, por lo tanto, Kashtan et al. propuso un esquema de ponderación que asigna diferentes pesos a los diferentes subgráficos dentro de la red. [9] El principio subyacente de la asignación de ponderaciones es explotar la información de la probabilidad de muestreo para cada subgráfico, es decir, los subgráficos probables obtendrán comparativamente menos ponderaciones en comparación con los subgráficos improbables; por lo tanto, el algoritmo debe calcular la probabilidad de muestreo de cada subgráfico que ha sido muestreado. Esta técnica de ponderación ayuda a mfinder a determinar las concentraciones de subgráficos de manera imparcial.
Ampliado para incluir un marcado contraste con la búsqueda exhaustiva, el tiempo de cálculo del algoritmo sorprendentemente es asintóticamente independiente del tamaño de la red. Un análisis del tiempo de cálculo del algoritmo ha demostrado que se necesita O(n n ) para cada muestra de un subgráfico de tamaño n de la red. Por otro lado, no hay ningún análisis en [9] sobre el tiempo de clasificación de los subgrafos muestreados que requiera resolver el problema de isomorfismo del grafo para cada muestra de subgrafo. Además, el cálculo del peso del subgráfico impone un esfuerzo computacional adicional al algoritmo. Pero es inevitable decir que el algoritmo puede muestrear el mismo subgráfico varias veces, pasando tiempo sin recopilar ninguna información. [10] En conclusión, al aprovechar las ventajas del muestreo, el algoritmo funciona de manera más eficiente que un algoritmo de búsqueda exhaustiva; sin embargo, sólo determina las concentraciones de los subgráficos de forma aproximada. Este algoritmo puede encontrar motivos hasta el tamaño 6 debido a su implementación principal y, como resultado, proporciona el motivo más significativo, no todos los demás también. Además, es necesario mencionar que esta herramienta no tiene opción de presentación visual. El algoritmo de muestreo se muestra brevemente:
Schreiber y Schwöbbermeyer [12] propusieron un algoritmo llamado buscador de patrones flexibles (FPF) para extraer subgrafos frecuentes de una red de entrada y lo implementaron en un sistema llamado Mavisto . [27] Su algoritmo explota la propiedad de cierre descendente que es aplicable a los conceptos de frecuencia F 2 y F 3 . La propiedad de cierre descendente afirma que la frecuencia de los subgráficos disminuye monótonamente al aumentar el tamaño de los subgráficos; sin embargo, esta propiedad no se cumple necesariamente para el concepto de frecuencia F 1 . FPF se basa en un árbol de patrones (ver figura) que consta de nodos que representan diferentes gráficos (o patrones), donde el padre de cada nodo es un subgráfico de sus nodos secundarios; en otras palabras, el gráfico correspondiente de cada nodo del árbol de patrón se expande agregando un nuevo borde al gráfico de su nodo padre.
Al principio, el algoritmo FPF enumera y mantiene la información de todas las coincidencias de un subgráfico ubicado en la raíz del árbol de patrones. Luego, uno por uno, construye nodos secundarios del nodo anterior en el árbol de patrones agregando un borde respaldado por un borde coincidente en el gráfico de destino e intenta expandir toda la información anterior sobre las coincidencias al nuevo subgráfico. (nodo hijo). En el siguiente paso, decide si la frecuencia del patrón actual es inferior a un umbral predefinido o no. Si es más bajo y se mantiene el cierre hacia abajo, FPF puede abandonar ese camino y no recorrer más en esta parte del árbol; como resultado, se evitan cálculos innecesarios. Este procedimiento continúa hasta que no queda ningún camino por recorrer.
La ventaja del algoritmo es que no considera subgrafos poco frecuentes e intenta finalizar el proceso de enumeración lo antes posible; por lo tanto, solo dedica tiempo a los nodos prometedores en el árbol de patrones y descarta todos los demás nodos. Como beneficio adicional, la noción de árbol de patrones permite implementar y ejecutar FPF de manera paralela, ya que es posible recorrer cada ruta del árbol de patrones de forma independiente. Sin embargo, FPF es más útil para los conceptos de frecuencia F 2 y F 3 , porque el cierre descendente no es aplicable a F 1 . Sin embargo, el árbol de patrones sigue siendo práctico para F 1 si el algoritmo se ejecuta en paralelo. Otra ventaja del algoritmo es que su implementación no tiene limitación en el tamaño del motivo, lo que lo hace más susceptible de mejoras. El pseudocódigo de FPF (Mavisto) se muestra a continuación:
El sesgo de muestreo de Kashtan et al. [9] proporcionó un gran impulso para diseñar mejores algoritmos para el problema de descubrimiento de NM. Aunque Kashtan et al. Intenté solucionar este inconveniente mediante un esquema de ponderación, este método impuso una sobrecarga no deseada en el tiempo de ejecución, así como una implementación más complicada. Esta herramienta es una de las más útiles, ya que admite opciones visuales y además es un algoritmo eficiente con respecto al tiempo. Pero tiene una limitación en el tamaño del motivo, ya que no permite buscar motivos de tamaño 9 o superior debido a la forma en que está implementada la herramienta.
Wernicke [10] introdujo un algoritmo llamado RAND-ESU que proporciona una mejora significativa con respecto a mfinder . [9] Este algoritmo, que se basa en el algoritmo de enumeración exacta ESU , se ha implementado como una aplicación llamada FANMOD . [10] RAND-ESU es un algoritmo de descubrimiento de NM aplicable tanto para redes dirigidas como no dirigidas, explota eficazmente un muestreo de nodos imparcial en toda la red y evita el conteo excesivo de subgráficos más de una vez. Además, RAND-ESU utiliza un enfoque analítico novedoso llamado DIRECT para determinar la importancia del subgráfico en lugar de utilizar un conjunto de redes aleatorias como modelo nulo. El método DIRECTO estima la concentración del subgráfico sin generar explícitamente redes aleatorias. [10] Empíricamente, el método DIRECTO es más eficiente en comparación con el conjunto de redes aleatorias en el caso de subgrafos con una concentración muy baja; sin embargo, el modelo nulo clásico es más rápido que el método DIRECTO para subgrafos altamente concentrados. [3] [10] A continuación, detallamos el algoritmo ESU y luego mostramos cómo este algoritmo exacto se puede modificar de manera eficiente a RAND-ESU que estima las concentraciones de subgráficos.
Los algoritmos ESU y RAND-ESU son bastante simples y, por tanto, fáciles de implementar. ESU primero encuentra el conjunto de todos los subgráficos inducidos de tamaño k , sea S k este conjunto. ESU se puede implementar como una función recursiva; La ejecución de esta función se puede mostrar como una estructura similar a un árbol de profundidad k , llamada ESU-Tree (ver figura). Cada uno de los nodos del ESU-Tree indica el estado de la función recursiva que implica dos conjuntos consecutivos SUB y EXT. SUB se refiere a nodos en la red de destino que son adyacentes y establecen un subgráfico parcial de tamaño |SUB| ≤k . Si |SUB| = k , el algoritmo ha encontrado un subgrafo completo inducido, por lo que S k = SUB ∪ S k . Sin embargo, si |SUB| < k , el algoritmo debe expandir SUB para lograr la cardinalidad k . Esto lo hace el conjunto EXT que contiene todos los nodos que satisfacen dos condiciones: primero, cada uno de los nodos en EXT debe ser adyacente a al menos uno de los nodos en SUB; en segundo lugar, sus etiquetas numéricas deben ser más grandes que la etiqueta del primer elemento en SUB. La primera condición asegura que la expansión de los nodos SUB produzca un gráfico conectado y la segunda condición hace que las hojas del árbol ESU (ver figura) sean distintas; como resultado, evita el conteo excesivo. Tenga en cuenta que el conjunto EXT no es un conjunto estático, por lo que en cada paso puede expandirse con algunos nodos nuevos que no infrinjan las dos condiciones. El siguiente paso de ESU implica la clasificación de los subgráficos colocados en las hojas del árbol ESU en clases de gráficos de tamaño k no isomórficos; en consecuencia, ESU determina las frecuencias y concentraciones de los subgráficos. Esta etapa se ha implementado simplemente empleando el algoritmo nauty de McKay , [28] [29] que clasifica cada subgrafo realizando una prueba de isomorfismo de gráfico. Por lo tanto, ESU encuentra el conjunto de todos los subgráficos de tamaño k inducidos en un gráfico objetivo mediante un algoritmo recursivo y luego determina su frecuencia utilizando una herramienta eficiente.
El procedimiento de implementación de RAND-ESU es bastante sencillo y es una de las principales ventajas de FANMOD . Se puede cambiar el algoritmo ESU para explorar solo una parte de las hojas del árbol ESU aplicando un valor de probabilidad 0 ≤ p d ≤ 1 para cada nivel del árbol ESU y obligar a ESU a atravesar cada nodo secundario de un nodo en el nivel d. -1 con probabilidad p d . Este nuevo algoritmo se llama RAND-ESU . Evidentemente, cuando p d = 1 para todos los niveles, RAND-ESU actúa como ESU . Para p d = 0 el algoritmo no encuentra nada. Tenga en cuenta que este procedimiento garantiza que las posibilidades de visitar cada hoja del árbol ESU sean las mismas, lo que da como resultado un muestreo imparcial de subgráficos a través de la red. La probabilidad de visitar cada hoja es Π d p d y esto es idéntico para todas las hojas del árbol ESU; por lo tanto, este método garantiza un muestreo imparcial de subgráficos de la red. No obstante, determinar el valor de p d para 1 ≤ d ≤ k es otra cuestión que debe ser determinada manualmente por un experto para obtener resultados precisos de las concentraciones del subgráfico. [8] Si bien no existe una receta lúcida para este asunto, Wernicke proporciona algunas observaciones generales que pueden ayudar a determinar los valores de p_d. En resumen, RAND-ESU es un algoritmo muy rápido para el descubrimiento de NM en el caso de subgrafos inducidos que admiten un método de muestreo insesgado. Aunque el algoritmo principal de ESU y, por tanto, la herramienta FANMOD son conocidos por descubrir subgráficos inducidos, existe una modificación trivial en ESU que hace posible encontrar también subgráficos no inducidos. El pseudocódigo de ESU (FANMOD) se muestra a continuación:
Chen et al. [30] introdujo un nuevo algoritmo de descubrimiento de NM llamado NeMoFinder , que adapta la idea en SPIN [31] para extraer árboles frecuentes y luego los expande en gráficos no isomorfos. [8] NeMoFinder utiliza árboles frecuentes de tamaño n para dividir la red de entrada en una colección de gráficos de tamaño n , luego encuentra subgráficos frecuentes de tamaño n mediante la expansión de árboles frecuentes borde por borde hasta obtener un tamaño completo n. gráfica K norte . El algoritmo encuentra NM en redes no dirigidas y no se limita a extraer únicamente subgrafos inducidos. Además, NeMoFinder es un algoritmo de enumeración exacto y no se basa en un método de muestreo. Como Chen et al. Según afirman, NeMoFinder es aplicable para detectar NM relativamente grandes, por ejemplo, encontrar NM de hasta tamaño 12 de toda la red PPI de S. cerevisiae (levadura) como afirman los autores. [32]
NeMoFinder consta de tres pasos principales. Primero, encontrar árboles frecuentes de tamaño n , luego utilizar árboles repetidos de tamaño n para dividir toda la red en una colección de gráficos de tamaño n y, finalmente, realizar operaciones de unión de subgráficos para encontrar subgráficos frecuentes de tamaño n. [30] En el primer paso, el algoritmo detecta todos los árboles de tamaño n no isomórficos y los mapeos de un árbol a la red. En el segundo paso, los rangos de estos mapeos se emplean para dividir la red en gráficos de tamaño n. Hasta este paso, no hay distinción entre NeMoFinder y un método de enumeración exacto. Sin embargo, todavía queda una gran parte de gráficos de tamaño n no isomórficos. NeMoFinder explota una heurística para enumerar gráficos que no son de tamaño de árbol según la información obtenida en los pasos anteriores. La principal ventaja del algoritmo está en el tercer paso, que genera subgráficos candidatos a partir de subgráficos previamente enumerados. Esta generación de nuevos subgrafos de tamaño n se realiza uniendo cada subgrafo anterior con subgrafos derivados de sí mismo llamados subgrafos primos . Estos nuevos subgráficos contienen una ventaja adicional en comparación con los subgráficos anteriores. Sin embargo, existen algunos problemas al generar nuevos subgrafos: no existe un método claro para derivar primos de un gráfico, unir un subgrafo con sus primos genera redundancia al generar un subgrafo particular más de una vez, y la determinación de primos es realizado mediante una representación canónica de la matriz de adyacencia que no está cerrada bajo la operación de unión. NeMoFinder es un algoritmo eficiente de búsqueda de motivos de red para motivos de hasta tamaño 12 solo para redes de interacción proteína-proteína, que se presentan como gráficos no dirigidos. Y no es capaz de trabajar en redes dirigidas que son tan importantes en el campo de las redes biológicas y complejas. El pseudocódigo de NeMoFinder se muestra a continuación:
Grochow y Kellis [33] propusieron un algoritmo exacto para enumerar apariciones de subgrafos. El algoritmo se basa en un enfoque centrado en motivos , lo que significa que la frecuencia de un subgráfico determinado, llamado gráfico de consulta , se determina exhaustivamente buscando todas las asignaciones posibles del gráfico de consulta a la red más grande. Se afirma [33] que un método centrado en motivos en comparación con los métodos centrados en redes tiene algunas características beneficiosas. En primer lugar, evita la mayor complejidad de la enumeración de subgrafos. Además, al utilizar mapeo en lugar de enumerar, se permite mejorar la prueba de isomorfismo. Para mejorar el rendimiento del algoritmo, dado que es un algoritmo de enumeración exacta ineficiente, los autores introdujeron un método rápido llamado condiciones de ruptura de simetría . Durante las pruebas sencillas de isomorfismo de subgrafos, un subgrafo se puede asignar al mismo subgrafo del gráfico de consulta varias veces. En el algoritmo de Grochow-Kellis (GK), se utiliza la ruptura de simetría para evitar asignaciones tan múltiples. Aquí presentamos el algoritmo GK y la condición de ruptura de simetría que elimina pruebas de isomorfismo redundantes.
El algoritmo GK descubre el conjunto completo de asignaciones de un gráfico de consulta determinado a la red en dos pasos principales. Comienza con el cálculo de las condiciones de ruptura de simetría del gráfico de consulta. A continuación, mediante un método de ramificación y unión, el algoritmo intenta encontrar todas las asignaciones posibles desde el gráfico de consulta a la red que cumpla con las condiciones de ruptura de simetría asociadas. En la figura se muestra un ejemplo del uso de condiciones de ruptura de simetría en el algoritmo GK.
Como se mencionó anteriormente, la técnica de ruptura de simetría es un mecanismo simple que impide perder tiempo buscando un subgráfico más de una vez debido a sus simetrías. [33] [34] Tenga en cuenta que, para calcular las condiciones de ruptura de simetría, es necesario encontrar todos los automorfismos de un gráfico de consulta determinado. Aunque no existe un algoritmo eficiente (o de tiempo polinomial) para el problema del automorfismo gráfico, este problema puede abordarse de manera eficiente en la práctica con las herramientas de McKay. [28] [29] Como se afirma, el uso de condiciones de ruptura de simetría en la detección de NM permite ahorrar una gran cantidad de tiempo de ejecución. Además, de los resultados en [33] [34] se puede inferir que el uso de condiciones de ruptura de simetría da como resultado una alta eficiencia, particularmente para redes dirigidas en comparación con redes no dirigidas. Las condiciones de ruptura de simetría utilizadas en el algoritmo GK son similares a la restricción que el algoritmo ESU aplica a las etiquetas en los conjuntos EXT y SUB. En conclusión, el algoritmo GK calcula el número exacto de apariciones de un gráfico de consulta determinado en una red grande y compleja y la explotación de las condiciones de ruptura de simetría mejora el rendimiento del algoritmo. Además, el algoritmo GK es uno de los algoritmos conocidos que no tiene limitación para el tamaño del motivo en su implementación y potencialmente puede encontrar motivos de cualquier tamaño.
La mayoría de los algoritmos en el campo del descubrimiento de NM se utilizan para encontrar subgrafos inducidos de una red. En 2008, Noga Alon et al. [35] también introdujo un enfoque para encontrar subgrafos no inducidos. Su técnica funciona en redes no dirigidas como las PPI. Además, cuenta árboles no inducidos y subgráficos de ancho de árbol acotados. Este método se aplica para subgráficos de tamaño hasta 10.
Este algoritmo cuenta el número de apariciones no inducidas de un árbol T con k = O(logn) vértices en una red G con n vértices de la siguiente manera:
Como las redes PPI disponibles están lejos de ser completas y libres de errores, este enfoque es adecuado para el descubrimiento de NM para dichas redes. Como el algoritmo de Grochow-Kellis y este son los populares para subgrafos no inducidos, vale la pena mencionar que el algoritmo introducido por Alon et al. Consume menos tiempo que el algoritmo de Grochow-Kellis. [35]
Omidi et al. [36] introdujeron un nuevo algoritmo para la detección de motivos denominado MODA que es aplicable para el descubrimiento de NM inducido y no inducido en redes no dirigidas. Se basa en el enfoque centrado en motivos que se analiza en la sección del algoritmo de Grochow-Kellis. Es muy importante distinguir los algoritmos centrados en motivos como MODA y GK debido a su capacidad para funcionar como algoritmos de búsqueda de consultas. Esta característica permite que dichos algoritmos puedan encontrar una consulta de motivo único o una pequeña cantidad de consultas de motivo (no todos los subgráficos posibles de un tamaño determinado) con tamaños más grandes. A medida que el número de posibles subgrafos no isomorfos aumenta exponencialmente con el tamaño del subgrafo, para motivos de gran tamaño (incluso mayores que 10), los algoritmos centrados en la red, aquellos que buscan todos los subgrafos posibles, enfrentan un problema. Aunque los algoritmos centrados en motivos también tienen problemas para descubrir todos los subgráficos posibles de gran tamaño, su capacidad para encontrar pequeños números de ellos es a veces una propiedad importante.
Utilizando una estructura jerárquica llamada árbol de expansión , el algoritmo MODA es capaz de extraer NM de un tamaño determinado de forma sistemática y similar a FPF que evita enumerar subgráficos poco prometedores; MODA toma en consideración consultas potenciales (o subgráficos candidatos) que darían como resultado subgráficos frecuentes. A pesar de que MODA se parece a FPF en el uso de una estructura similar a un árbol, el árbol de expansión es aplicable simplemente para calcular el concepto de frecuencia F1 . Como veremos a continuación, la ventaja de este algoritmo es que no realiza la prueba de isomorfismo de subgrafos para gráficos de consulta que no son de árbol . Además, utiliza un método de muestreo para acelerar el tiempo de ejecución del algoritmo.
Aquí está la idea principal: mediante un criterio simple se puede generalizar un mapeo de un gráfico de tamaño k en la red a sus supergrafos del mismo tamaño. Por ejemplo, supongamos que hay un mapeo f(G) del gráfico G con k nodos en la red y tenemos un gráfico del mismo tamaño G′ con un borde más &langu, v⟩ ; f G asignará G′ a la red, si hay un borde ⟨f G (u), f G (v)⟩ en la red. Como resultado, podemos explotar el conjunto de mapeo de un gráfico para determinar las frecuencias de sus supergrafos del mismo orden simplemente en tiempo O (1) sin realizar pruebas de isomorfismo de subgráficos. El algoritmo comienza ingeniosamente con gráficos de consulta mínimamente conectados de tamaño k y encuentra sus asignaciones en la red mediante isomorfismo de subgrafos. Después de eso, conservando el tamaño del gráfico, expande los gráficos de consulta previamente considerados borde por borde y calcula la frecuencia de estos gráficos expandidos como se mencionó anteriormente. El proceso de expansión continúa hasta llegar a un gráfico completo K k (completamente conectado con k(k-1) ⁄ 2 arista).
Como se analizó anteriormente, el algoritmo comienza calculando las frecuencias de los subárboles en la red y luego expande los subárboles borde por borde. Una forma de implementar esta idea se llama árbol de expansión T k para cada k . La figura muestra el árbol de expansión para subgráficos de tamaño 4. T k organiza el proceso en ejecución y proporciona gráficos de consulta de forma jerárquica. Estrictamente hablando, el árbol de expansión T k es simplemente un gráfico acíclico dirigido o DAG, donde su número de raíz k indica el tamaño del gráfico existente en el árbol de expansión y cada uno de sus otros nodos contiene la matriz de adyacencia de un gráfico de consulta de tamaño k distinto . Los nodos en el primer nivel de T k son todos árboles distintos de tamaño k y, al atravesar T k en profundidad, los gráficos de consulta se expanden con un borde en cada nivel. Un gráfico de consulta en un nodo es un subgráfico del gráfico de consulta en el hijo de un nodo con una diferencia de borde. El camino más largo en T k consta de (k 2 -3k+4)/2 aristas y es el camino desde la raíz hasta el nodo hoja que contiene el gráfico completo. La generación de árboles de expansión se puede realizar mediante una rutina simple que se explica en [36] .
MODA atraviesa T k y cuando extrae árboles de consulta del primer nivel de T k, calcula sus conjuntos de asignaciones y guarda estas asignaciones para el siguiente paso. Para consultas que no son de árbol de T k , el algoritmo extrae las asignaciones asociadas con el nodo principal en T k y determina cuál de estas asignaciones puede admitir los gráficos de consulta actuales. El proceso continuará hasta que el algoritmo obtenga el gráfico de consulta completo. Las asignaciones del árbol de consultas se extraen mediante el algoritmo de Grochow-Kellis. Para calcular la frecuencia de gráficos de consultas que no son de árbol, el algoritmo emplea una rutina simple que toma O(1) pasos. Además, MODA explota un método de muestreo donde el muestreo de cada nodo en la red es linealmente proporcional al grado del nodo, la distribución de probabilidad es exactamente similar al conocido modelo de conexión preferencial de Barabási-Albert en el campo de redes complejas. [37] Este enfoque genera aproximaciones; sin embargo, los resultados son casi estables en diferentes ejecuciones ya que los subgráficos se agregan alrededor de nodos altamente conectados. [38] El pseudocódigo de MODA se muestra a continuación:
Un algoritmo introducido recientemente llamado Kavosh [39] tiene como objetivo mejorar el uso de la memoria principal. Kavosh se puede utilizar para detectar NM tanto en redes dirigidas como no dirigidas. La idea principal de la enumeración es similar a los algoritmos GK y MODA , que primero encuentran todos los subgrafos de tamaño k en los que participó un nodo en particular, luego eliminan el nodo y posteriormente repiten este proceso para los nodos restantes. [39]
Para contar los subgrafos de tamaño k que incluyen un nodo particular, se construyen implícitamente árboles con una profundidad máxima de k, enraizados en este nodo y basados en la relación de vecindad. Los hijos de cada nodo incluyen nodos adyacentes entrantes y salientes. Para descender del árbol, se elige un niño en cada nivel con la restricción de que un niño en particular sólo puede incluirse si no ha sido incluido en ningún nivel superior. Después de haber descendido al nivel más bajo posible, el árbol asciende nuevamente y el proceso se repite con la estipulación de que los nodos visitados en caminos anteriores de un descendiente ahora se consideran nodos no visitados. Una última restricción en la construcción de árboles es que todos los hijos de un árbol en particular deben tener etiquetas numéricas más grandes que la etiqueta de la raíz del árbol. Las restricciones en las etiquetas de los niños son similares a las condiciones que utilizan los algoritmos GK y ESU para evitar el recuento excesivo de subgráficos.
El protocolo para extraer subgrafos utiliza las composiciones de un número entero. Para la extracción de subgrafos de tamaño k , se deben considerar todas las composiciones posibles del número entero k-1 . Las composiciones de k-1 constan de todas las formas posibles de expresar k-1 como una suma de números enteros positivos. Se consideran distintas las sumatorias en las que difiere el orden de los sumandos. Una composición se puede expresar como k 2 ,k 3 ,...,k m donde k 2 + k 3 + ... + k m = k-1 . Para contar subgráficos según la composición, se seleccionan k i nodos del i -ésimo nivel del árbol para que sean nodos de los subgráficos ( i = 2,3,...,m ). Los k-1 nodos seleccionados junto con el nodo en la raíz definen un subgráfico dentro de la red. Después de descubrir un subgráfico involucrado como coincidencia en la red objetivo, para poder evaluar el tamaño de cada clase según la red objetivo, Kavosh emplea el algoritmo nauty [28] [29] de la misma manera que FANMOD. . La parte de enumeración del algoritmo Kavosh se muestra a continuación:
Recientemente se desarrolló un complemento de Cytoscape llamado CytoKavosh [40] para este software. Está disponible a través de la página web de Cytoscape [1].
En 2010, Pedro Ribeiro y Fernando Silva propusieron una nueva estructura de datos para almacenar una colección de subgrafos, llamada g-trie . [41] Esta estructura de datos, que es conceptualmente similar a un árbol de prefijos, almacena subgráficos de acuerdo con sus estructuras y encuentra apariciones de cada uno de estos subgráficos en un gráfico más grande. Uno de los aspectos notables de esta estructura de datos es que, al llegar al descubrimiento del motivo de la red, es necesario evaluar los subgráficos de la red principal. Por lo tanto, no es necesario encontrar aquellos en la red aleatoria que no están en la red principal. Esta puede ser una de las partes que consumen mucho tiempo en los algoritmos en los que se derivan todos los subgrafos en redes aleatorias.
Un g-trie es un árbol de múltiples vías que puede almacenar una colección de gráficos. Cada nodo del árbol contiene información sobre un único vértice del gráfico y sus bordes correspondientes a los nodos ancestros. Un camino desde la raíz hasta una hoja corresponde a un solo gráfico. Los descendientes de un nodo g-trie comparten un subgrafo común. La construcción de un g-trie se describe bien en [41] Después de construir un g-trie , se lleva a cabo la parte de conteo. La idea principal en el proceso de conteo es retroceder en todos los subgráficos posibles, pero al mismo tiempo realizar las pruebas de isomorfismo. Esta técnica de retroceso es esencialmente la misma técnica empleada por otros enfoques centrados en motivos como los algoritmos MODA y GK . Aprovechar las subestructuras comunes en el sentido de que en un momento dado existe una coincidencia isomórfica parcial para varios subgrafos candidatos diferentes.
Entre los algoritmos mencionados, G-Tries es el más rápido. Pero el uso excesivo de la memoria es el inconveniente de este algoritmo, que podría limitar el tamaño de los motivos detectables por una computadora personal con memoria promedio.
ParaMODA [42] y NemoMap [43] son algoritmos rápidos publicados en 2017 y 2018, respectivamente. No son tan escalables como muchos de los demás. [44]
Las tablas y la figura a continuación muestran los resultados de ejecutar los algoritmos mencionados en diferentes redes estándar. Estos resultados están tomados de las fuentes correspondientes, [36] [39] [41] por lo que deben tratarse individualmente.
Se ha dedicado mucho trabajo experimental a comprender los motivos de las redes reguladoras de genes . Estas redes controlan qué genes se expresan en la célula en respuesta a señales biológicas. La red se define de manera que los genes son nodos y los bordes dirigidos representan el control de un gen por un factor de transcripción (proteína reguladora que se une al ADN) codificada por otro gen. Por tanto, los motivos de red son patrones de genes que regulan la tasa de transcripción de cada uno. Al analizar las redes de transcripción, se ve que los mismos motivos de red aparecen una y otra vez en diversos organismos, desde bacterias hasta humanos. La red de transcripción de E. coli y levadura, por ejemplo, está formada por tres familias de motivos principales, que constituyen casi toda la red. La hipótesis principal es que el motivo de la red fue seleccionado independientemente por procesos evolutivos de manera convergente, [45] [46] ya que la creación o eliminación de interacciones regulatorias es rápida en la escala de tiempo evolutiva, en relación con la velocidad a la que cambian los genes, [ 45] [46] [47] Además, los experimentos sobre la dinámica generada por motivos de red en células vivas indican que tienen funciones dinámicas características. Esto sugiere que el motivo de la red sirve como componente básico de las redes reguladoras de genes que son beneficiosas para el organismo.
Las funciones asociadas con motivos de red comunes en las redes de transcripción fueron exploradas y demostradas mediante varios proyectos de investigación, tanto de forma teórica como experimental. A continuación se muestran algunos de los motivos de red más comunes y su función asociada.
Uno de los motivos de red más simples y abundantes en E. coli es la autorregulación negativa en la que un factor de transcripción (TF) reprime su propia transcripción. Se demostró que este motivo desempeñaba dos funciones importantes. La primera función es la aceleración de respuesta. Se demostró que NAR acelera la respuesta a las señales tanto teóricamente [48] como experimentalmente. Esto se demostró por primera vez en una red de transcripción sintética [49] y más tarde en el contexto natural en el sistema de reparación del ADN SOS de E. coli. [50] La segunda función es aumentar la estabilidad de la concentración del producto genético autorregulado frente al ruido estocástico, reduciendo así las variaciones en los niveles de proteína entre diferentes células. [51] [52] [53]
La autorregulación positiva (PAR) ocurre cuando un factor de transcripción mejora su propia tasa de producción. A diferencia del motivo NAR, este motivo ralentiza el tiempo de respuesta en comparación con una regulación simple. [54] En el caso de un PAR fuerte, el motivo puede conducir a una distribución bimodal de los niveles de proteínas en las poblaciones celulares. [55]
Este motivo se encuentra comúnmente en muchos sistemas genéticos y organismos. El motivo consta de tres genes y tres interacciones reguladoras. El gen diana C está regulado por 2 TF A y B y además TF B también está regulado por TF A. Dado que cada una de las interacciones reguladoras puede ser positiva o negativa, existen posiblemente ocho tipos de motivos FFL. [56] Dos de esos ocho tipos: el FFL tipo 1 coherente (C1-FFL) (donde todas las interacciones son positivas) y el FFL tipo 1 incoherente (I1-FFL) (A activa C y también activa B, que reprime a C) son Se encuentra con mucha más frecuencia en la red de transcripción de E. coli y levadura que los otros seis tipos. [56] [57] Además de la estructura del circuito, también se debe considerar la forma en que el promotor C integra las señales de A y B. En la mayoría de los casos, el FFL es una puerta AND (A y B son necesarios para la activación de C) o una puerta OR (A o B son suficientes para la activación de C), pero también son posibles otras funciones de entrada.
Se demostró que el C1-FFL con una puerta AND tiene una función de elemento de "retraso sensible a signos" y un detector de persistencia tanto teóricamente [56] como experimentalmente [58] con el sistema arabinosa de E. coli . Esto significa que este motivo puede proporcionar filtración de pulsos en el que los pulsos cortos de señal no generarán una respuesta pero las señales persistentes generarán una respuesta después de un breve retraso. El apagado de la salida cuando finalice un pulso persistente será rápido. El comportamiento opuesto surge en el caso de una puerta suma con respuesta rápida y cierre retardado, como se demostró en el sistema de flagelos de E. coli . [59] La evolución de novo de C1-FFL en redes reguladoras de genes se ha demostrado computacionalmente en respuesta a la selección para filtrar un pulso de señal corto idealizado, pero para el ruido no idealizado, se puede utilizar un sistema dinámico de regulación de avance con diferentes en cambio, se favoreció la topología. [60]
El I1-FFL es un generador de impulsos y acelerador de respuesta. Las dos vías de señales del I1-FFL actúan en direcciones opuestas donde una vía activa Z y la otra lo reprime. Cuando la represión es completa, esto conduce a una dinámica similar a un pulso. También se demostró experimentalmente que el I1-FFL puede servir como acelerador de respuesta de forma similar al motivo NAR. La diferencia es que el I1-FFL puede acelerar la respuesta de cualquier gen y no necesariamente un gen del factor de transcripción. [61] Se asignó una función adicional al motivo de la red I1-FFL: se demostró tanto teórica como experimentalmente que el I1-FFL puede generar una función de entrada no monótona tanto en sistemas sintéticos [62] como nativos. [63] Finalmente, las unidades de expresión que incorporan un control de avance incoherente del producto génico proporcionan adaptación a la cantidad de plantilla de ADN y pueden ser superiores a combinaciones simples de promotores constitutivos. [64] La regulación de retroalimentación mostró una mejor adaptación que la retroalimentación negativa , y los circuitos basados en interferencia de ARN fueron los más robustos a la variación en las cantidades de plantilla de ADN. [64] Se ha demostrado computacionalmente la evolución de novo de las I1-FFL en redes reguladoras de genes en respuesta a la selección para generar un pulso, siendo las I1-FFL evolutivamente más accesibles, pero no superiores, en relación con un motivo alternativo en el que es la salida en lugar de la entrada que activa el represor. [65]
En algunos casos los mismos reguladores X e Y regulan varios genes Z del mismo sistema. Al ajustar la fuerza de las interacciones, se demostró que este motivo determina el orden temporal de la activación genética. Esto se demostró experimentalmente en el sistema de flagelos de E. coli . [66]
Este motivo ocurre cuando un solo regulador regula un conjunto de genes sin regulación adicional. Esto es útil cuando los genes llevan a cabo de forma cooperativa una función específica y, por lo tanto, siempre necesitan activarse de manera sincronizada. Al ajustar la fuerza de las interacciones, puede crear un programa de expresión temporal de los genes que regula. [67]
En la literatura, los módulos de entradas múltiples (MIM) surgieron como una generalización del SIM. Sin embargo, las definiciones precisas de SIM y MIM han sido una fuente de inconsistencia. Hay intentos de proporcionar definiciones ortogonales para motivos canónicos en redes biológicas y algoritmos para enumerarlos, especialmente SIM, MIM y Bi-Fan (2x2 MIM). [68]
Este motivo ocurre en el caso de que varios reguladores controlen combinatoriamente un conjunto de genes con diversas combinaciones reguladoras. Este motivo se encontró en E. coli en varios sistemas, como la utilización de carbono, el crecimiento anaeróbico, la respuesta al estrés y otros. [17] [22] Para comprender mejor la función de este motivo, es necesario obtener más información sobre la forma en que los genes integran las múltiples entradas. Kaplan y cols. [69] ha mapeado las funciones de entrada de los genes de utilización del azúcar en E. coli , mostrando diversas formas.
Una generalización interesante de los motivos de red, los motivos de actividad son patrones que se repiten y que se pueden encontrar cuando los nodos y bordes de la red se anotan con características cuantitativas. Por ejemplo, cuando los bordes de una vía metabólica se anotan con la magnitud o el momento de la expresión genética correspondiente, algunos patrones se sobrecurren dada la estructura de la red subyacente. [70]
Una suposición (a veces más a veces menos implícita) detrás de la preservación de una subestructura topológica es que tiene una importancia funcional particular. Esta suposición ha sido cuestionada recientemente. Algunos autores han argumentado que los motivos, como los motivos bi-fan , pueden mostrar una variedad dependiendo del contexto de la red y, por lo tanto, [71] la estructura del motivo no determina necesariamente la función. La estructura de la red ciertamente no siempre indica función; Esta es una idea que existe desde hace algún tiempo; por ejemplo, consulte el operón Sin. [72]
La mayoría de los análisis de la función del motivo se llevan a cabo observando el motivo que opera de forma aislada. Investigaciones recientes [73] proporcionan buena evidencia de que el contexto de la red, es decir, las conexiones del motivo con el resto de la red, es demasiado importante para sacar inferencias sobre la función a partir únicamente de la estructura local; el artículo citado también revisa las críticas y explicaciones alternativas para la datos observados. Se estudia un análisis del impacto de un módulo de motivo único en la dinámica global de una red. [74] Otro trabajo reciente sugiere que ciertas características topológicas de las redes biológicas dan lugar naturalmente a la apariencia común de motivos canónicos, cuestionando así si Las frecuencias de ocurrencias son evidencia razonable de que las estructuras de los motivos se seleccionan por su contribución funcional al funcionamiento de las redes. [75] [76]
{{cite encyclopedia}}: |journal=ignorado ( ayuda )