Los motivos de red son subgrafos o patrones recurrentes y estadísticamente significativos de un grafo más grande . Todas las redes, incluidas las redes biológicas , las redes sociales, las redes tecnológicas (por ejemplo, las redes informáticas y los circuitos eléctricos) y más, se pueden representar como grafos, 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 se logran funciones particulares de manera eficiente. De hecho, los motivos son de notable importancia en gran medida porque pueden reflejar propiedades funcionales. Recientemente [ ¿cuándo? ] han atraído mucha atención como un concepto útil para descubrir principios de diseño estructural de redes complejas. [1] Aunque los motivos de 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 grafos. El grafo G′ es un subgrafo del grafo G (escrito como G′ ⊆ G ) si V′ ⊆ V y E′ ⊆ E ∩ (V′ × V′) . Si G′ ⊆ G y G′ contiene todas las aristas ⟨u, v⟩ ∈ E con u, v ∈ V′ , entonces G′ es un subgrafo inducido de G . Llamamos a G′ y G isomorfos (escritos como G′ ↔ G ), si existe una biyección (correspondencia biunívoca) f:V′ → V con ⟨u, v⟩ ∈ E′ ⇔ ⟨f(u), f(v)⟩ ∈ E para todo u, v ∈ V′ . La aplicación f se llama isomorfismo entre G y G′ . [2]
Cuando G″ ⊂ G y existe un isomorfismo entre el subgrafo G″ y un grafo G′ , este mapeo representa una aparición de G′ en G . El número de apariciones del grafo G′ en G se llama frecuencia F G de G′ en G . Un grafo se llama recurrente (o frecuente ) en G cuando su frecuencia F G (G′) está por encima de un umbral predefinido o valor de corte. En esta revisión usamos los términos patrón y subgrafo frecuente indistintamente. Hay un conjunto Ω(G) de grafos aleatorios correspondientes al modelo nulo asociado a G . Deberíamos elegir N grafos aleatorios uniformemente de Ω(G) y calcular la frecuencia para un subgrafo frecuente particular G′ en G . Si la frecuencia de G′ en G es mayor que su frecuencia media aritmética en N grafos aleatorios R i , donde 1 ≤ i ≤ N , llamamos a este patrón recurrente significativo y, por lo tanto, tratamos a G′ como un motivo de red para G . Para un grafo 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′ está 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 sea 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 subgrafo con un valor p menor que 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 subgrafo G′ particular de tamaño n en la red G se refiere a la relación entre la aparición del subgrafo en la red y las frecuencias totales de los subgrafos no isomorfos de tamaño n , que se formula mediante
donde el índice i se define sobre el conjunto de todos los gráficos de tamaño n no isomorfos. Se define otra medida estadística para evaluar motivos de red, pero rara vez se utiliza en algoritmos conocidos. Esta medida fue introducida por Picard et al. en 2008 y utilizó la distribución de Poisson, en lugar de la distribución normal gaussiana que se utiliza implícitamente anteriormente. [11]
Además, se han propuesto tres conceptos específicos de frecuencia de subgrafos. [12] Como ilustra la figura, el primer concepto de frecuencia F 1 considera todas las coincidencias de un grafo 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 disjuntas en las aristas de un grafo dado 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 grafo y, como se puede inferir, la frecuencia de un subgrafo disminuye al imponer restricciones al uso de elementos de la red. Como resultado, un algoritmo de detección de motivos de red pasaría por alto más subgrafos candidatos si insistimos en los conceptos de frecuencia F 2 y F 3 .
El estudio de los motivos de red fue iniciado por Holland y Leinhardt [13] [14] [15] [16], quienes introdujeron el concepto de un censo de tríadas de redes. Introdujeron métodos para enumerar varios tipos de configuraciones de subgrafos y comprobar 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 una cantidad considerable de estudios sobre el tema. Algunos de estos estudios se centran en las aplicaciones biológicas, mientras que otros se centran en la teoría computacional de los motivos de red.
Los estudios biológicos intentan interpretar los motivos detectados en las redes biológicas. Por ejemplo, en un trabajo posterior [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 a las investigaciones biológicas y permitir el análisis de redes más grandes. Hasta el momento 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 difícil problema del descubrimiento de motivos de red (NM). Estos algoritmos se pueden clasificar en varios paradigmas, como métodos de conteo exacto, métodos de muestreo, métodos de crecimiento de patrones, etc. Sin embargo, el problema del descubrimiento de motivos comprende dos pasos principales: primero, calcular el número de ocurrencias de un subgrafo y luego, evaluar la significancia del subgrafo. La recurrencia es significativa si es detectablemente mucho mayor que la esperada. En términos generales, el número esperado de apariciones de un subgrafo se puede determinar mediante un modelo nulo, que se define por 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 NM era el de fuerza bruta propuesto por Milo et al. [ 3] Este algoritmo fue exitoso para descubrir motivos pequeños, pero usar este método para encontrar motivos de tamaño 5 o 6 no era computacionalmente factible. Por lo tanto, se necesitaba un nuevo enfoque para este problema.
Aquí se ofrece una revisión de los aspectos computacionales de los principales algoritmos y se discuten sus beneficios y desventajas 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 el recuento exacto y los que utilizan, en su lugar, muestreos y estimaciones estadísticas. Debido a que el segundo grupo no cuenta todas las ocurrencias de un subgrafo en la red principal, los algoritmos que pertenecen a este grupo son más rápidos, pero pueden arrojar resultados sesgados y poco realistas.
En el siguiente nivel, los algoritmos de conteo exacto se pueden clasificar en métodos centrados en la red y centrados en los 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 generan primero diferentes posibles grafos no isomorfos 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. publicaron mfinder , la primera herramienta de minería 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 a lo largo de la red. Este algoritmo estima concentraciones de subgrafos inducidos y se puede utilizar 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 subgrafo de tamaño dos, y luego expande el subgrafo eligiendo un borde aleatorio que es incidente al subgrafo actual. Después de eso, continúa eligiendo bordes vecinos aleatorios hasta que se obtiene un subgrafo de tamaño n. Finalmente, el subgrafo 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 el problema 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. propusieron un esquema de ponderación que asigna diferentes pesos a los diferentes subgrafos dentro de la red. [9] El principio subyacente de la asignación de peso es explotar la información de la probabilidad de muestreo para cada subgráfico, es decir, los subgráficos probables obtendrán pesos comparativamente menores en comparación con los subgráficos improbables; por lo tanto, el algoritmo debe calcular la probabilidad de muestreo de cada subgráfico que se haya muestreado. Esta técnica de ponderación ayuda a mfinder a determinar las concentraciones de subgráficos de manera imparcial.
En contraste con la búsqueda exhaustiva, el tiempo computacional del algoritmo sorprendentemente es asintóticamente independiente del tamaño de la red. Un análisis del tiempo computacional del algoritmo ha demostrado que toma O(n n ) para cada muestra de un subgrafo 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 de grafos para cada muestra de subgrafo. Además, el cálculo del peso del subgrafo impone un esfuerzo computacional adicional al algoritmo. Pero es inevitable decir que el algoritmo puede muestrear el mismo subgrafo varias veces, gastando 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, solo determina las concentraciones de subgrafos de manera aproximada. Este algoritmo puede encontrar motivos de hasta 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 cuenta con 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 flexible (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 hacia abajo que es aplicable para los conceptos de frecuencia F 2 y F 3 . La propiedad de cierre hacia abajo afirma que la frecuencia de los subgrafos disminuye monótonamente al aumentar el tamaño de los subgrafos; 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 subgrafo de sus nodos hijos; en otras palabras, el gráfico correspondiente del nodo de cada árbol de patrones se expande agregando una nueva arista al gráfico de su nodo padre.
En primer lugar, el algoritmo FPF enumera y mantiene la información de todas las coincidencias de un subgrafo 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 una arista respaldada por una arista coincidente en el grafo de destino, e intenta expandir toda la información anterior sobre las coincidencias al nuevo subgrafo (nodo secundario). En el siguiente paso, decide si la frecuencia del patrón actual es menor que un umbral predefinido o no. Si es menor y se mantiene el cierre descendente, FPF puede abandonar esa ruta y no recorrer más en esta parte del árbol; como resultado, se evita un cálculo innecesario. Este procedimiento continúa hasta que no haya ninguna ruta restante para recorrer.
La ventaja del algoritmo es que no considera subgrafos poco frecuentes e intenta terminar 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 que FPF se implemente y ejecute de manera paralela, ya que es posible recorrer cada camino 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 . No obstante, el árbol de patrones sigue siendo práctico para F 1 si el algoritmo se ejecuta en paralelo. Otra ventaja del algoritmo es que la implementación de este algoritmo no tiene limitación en el tamaño del motivo, lo que lo hace más susceptible a 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. intentaron resolver 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 también 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 sobre 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 NM aplicable tanto para redes dirigidas como no dirigidas, explota eficazmente un muestreo de nodos imparcial en toda la red y evita el recuento excesivo de subgrafos más de una vez. Además, RAND-ESU utiliza un nuevo enfoque analítico llamado DIRECT para determinar la significancia de los subgrafos en lugar de utilizar un conjunto de redes aleatorias como un modelo nulo. El método DIRECT estima la concentración de subgrafos sin generar explícitamente redes aleatorias. [10] Empíricamente, el método DIRECT 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 DIRECT 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 lo tanto, fáciles de implementar. ESU primero encuentra el conjunto de todos los subgrafos 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 los nodos en la red objetivo que son adyacentes y establecen un subgrafo 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 se hace mediante 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; segundo, 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 produce un gráfico conectado y la segunda condición hace que las hojas del ESU-Tree (ver figura) sean distintas; como resultado, evita el recuento 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 incumplen las dos condiciones. El siguiente paso de ESU implica la clasificación de los subgrafos colocados en las hojas del ESU-Tree en clases de grafos de tamaño k no isomórficos ; en consecuencia, ESU determina las frecuencias y concentraciones de los subgrafos. Esta etapa se ha implementado simplemente empleando el algoritmo nauty de McKay , [28] [29] que clasifica cada subgrafo realizando una prueba de isomorfismo de grafos. 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 ESU-Tree aplicando un valor de probabilidad 0 ≤ p d ≤ 1 para cada nivel del ESU-Tree y obligar a ESU a atravesar cada nodo hijo 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 probabilidades de visitar cada hoja del ESU-Tree sean las mismas, lo que da como resultado un muestreo imparcial de subgrafos a través de la red. La probabilidad de visitar cada hoja es Π d p d y es idéntica para todas las hojas del ESU-Tree; Por lo tanto, este método garantiza un muestreo imparcial de los subgrafos de la red. No obstante, determinar el valor de p d para 1 ≤ d ≤ k es otro problema que debe ser determinado manualmente por un experto para obtener resultados precisos de las concentraciones de subgrafos. [8] Si bien no existe una prescripción 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 imparcial. Aunque el algoritmo principal de ESU y, por lo tanto, la herramienta FANMOD son conocidos por descubrir subgrafos inducidos, existe una modificación trivial de ESU que también permite encontrar subgrafos no inducidos. El pseudocódigo de ESU (FANMOD) se muestra a continuación:
Chen et al. [30] introdujeron un nuevo algoritmo de descubrimiento de NM llamado NeMoFinder , que adapta la idea de SPIN [31] para extraer árboles frecuentes y luego expandirlos 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 , y luego encuentra subgráficos frecuentes de tamaño n mediante la expansión de árboles frecuentes borde por borde hasta obtener un gráfico completo de tamaño n K n . El algoritmo encuentra NM en redes no dirigidas y no se limita a extraer solo subgráficos inducidos. Además, NeMoFinder es un algoritmo de enumeración exacto y no se basa en un método de muestreo. Como afirman Chen et al. , 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 afirmaron los autores. [32]
NeMoFinder consta de tres pasos principales. Primero, encontrar árboles de tamaño n frecuentes, luego utilizar árboles de tamaño n repetidos para dividir toda la red en una colección de grafos de tamaño n , finalmente, realizar operaciones de unión de subgrafos para encontrar subgrafos de tamaño n frecuentes. [30] En el primer paso, el algoritmo detecta todos los árboles de tamaño n no isomorfos y las asignaciones de un árbol a la red. En el segundo paso, se emplean los rangos de estas asignaciones para dividir la red en grafos de tamaño n. Hasta este paso, no hay distinción entre NeMoFinder y un método de enumeración exacta. Sin embargo, aún quedan una gran parte de grafos de tamaño n no isomorfos. NeMoFinder explota una heurística para enumerar grafos de tamaño n que no sean árboles mediante la información obtenida de los pasos anteriores. La principal ventaja del algoritmo está en el tercer paso, que genera subgrafos candidatos a partir de subgrafos enumerados previamente. 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 subgrafos contienen una arista adicional en comparación con los subgrafos anteriores. Sin embargo, existen algunos problemas en la generación de nuevos subgrafos: no existe un método claro para derivar primos de un grafo, unir un subgrafo con sus primos conduce a redundancia en la generación de un subgrafo particular más de una vez, y la determinación de primos se realiza 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 grafos no dirigidos. Y no puede funcionar en redes dirigidas que son tan importantes en el campo de las redes complejas y biológicas. El pseudocódigo de NeMoFinder se muestra a continuación:
Grochow y Kellis [33] propusieron un algoritmo exacto para enumerar las apariencias de los subgrafos. El algoritmo se basa en un enfoque centrado en motivos , lo que significa que la frecuencia de un subgrafo dado, llamado grafo de consulta , se determina exhaustivamente buscando todas las asignaciones posibles del grafo de consulta en la red más grande. Se afirma [33] que un método centrado en motivos en comparación con los métodos centrados en la red tiene algunas características beneficiosas. En primer lugar, evita la mayor complejidad de la enumeración de subgrafos. Además, al usar la asignación en lugar de la enumeración, permite una mejora en la prueba de isomorfismo. Para mejorar el rendimiento del algoritmo, ya que es un algoritmo de enumeración exacta ineficiente, los autores introdujeron un método rápido que se llama condiciones de ruptura de simetría . Durante las pruebas de isomorfismo de subgrafos sencillas, un subgrafo puede asignarse al mismo subgrafo del grafo de consulta varias veces. En el algoritmo Grochow–Kellis (GK) se utiliza la ruptura de simetría para evitar tales asignaciones múltiples. Aquí presentamos el algoritmo GK y la condición de ruptura de simetría que elimina las pruebas de isomorfismo redundantes.
El algoritmo GK descubre todo el conjunto de asignaciones de un gráfico de consulta dado 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 acotación, el algoritmo intenta encontrar todas las asignaciones posibles del gráfico de consulta a la red que cumplan con las condiciones de ruptura de simetría asociadas. En la figura se muestra un ejemplo del uso de las 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 evita gastar tiempo buscando un subgrafo más de una vez debido a sus simetrías. [33] [34] Nótese que, calcular las condiciones de ruptura de simetría requiere encontrar todos los automorfismos de un grafo de consulta dado. Aunque no existe un algoritmo eficiente (o de tiempo polinomial) para el problema del automorfismo de grafos, este problema puede ser abordado eficientemente 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 conduce a un ahorro de una gran cantidad de tiempo de ejecución. Además, se puede inferir de los resultados en [33] [34] que el uso de las 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 compleja de gran tamaño y, al aprovechar 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 limitaciones en cuanto al tamaño de los motivos 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] introdujeron un enfoque para encontrar también subgrafos no inducidos. Su técnica funciona en redes no dirigidas, como las PPI. Además, cuenta árboles no inducidos y subgrafos con ancho de árbol limitado. Este método se aplica para subgrafos de tamaño de hasta 10.
Este algoritmo cuenta el número de ocurrencias 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 NM para dichas redes. Como el algoritmo de Grochow-Kellis y este son los más populares para subgrafos no inducidos, vale la pena mencionar que el algoritmo introducido por Alon et al. requiere 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 analizado en la sección del algoritmo 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 única consulta de motivo o una pequeña cantidad de consultas de motivo (no todos los subgrafos posibles de un tamaño determinado) con tamaños más grandes. Como la cantidad de posibles subgrafos no isomorfos aumenta exponencialmente con el tamaño del subgrafo, para motivos de gran tamaño (incluso mayores de 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 posibles subgrafos de gran tamaño, su capacidad para encontrar una pequeña cantidad de ellos es a veces una propiedad significativa.
Usando una estructura jerárquica llamada árbol de expansión , el algoritmo MODA es capaz de extraer NMs de un tamaño dado sistemáticamente y de manera similar a FPF que evita enumerar subgrafos poco prometedores; MODA toma en consideración consultas potenciales (o subgrafos candidatos) que darían como resultado subgrafos frecuentes. A pesar del hecho de que MODA se parece a FPF al usar una estructura tipo árbol, el árbol de expansión es aplicable únicamente para calcular el concepto de frecuencia F 1 . Como discutiremos a continuación, la ventaja de este algoritmo es que no lleva a cabo la prueba de isomorfismo de subgrafos para grafos de consulta que no son árboles . Además, utiliza un método de muestreo para acelerar el tiempo de ejecución del algoritmo.
Aquí está la idea principal: por un criterio simple uno puede generalizar un mapeo de un grafo de tamaño k en la red a sus supergrafos del mismo tamaño. Por ejemplo, supongamos que hay un mapeo f(G) del grafo G con k nodos en la red y tenemos un grafo del mismo tamaño G′ con una arista más &langu, v⟩ ; f G mapeará G′ en la red, si hay una arista ⟨f G (u), f G (v)⟩ en la red. Como resultado, podemos explotar el conjunto de mapeos de un grafo para determinar las frecuencias de sus supergrafos del mismo orden simplemente en tiempo O(1) sin llevar a cabo pruebas de isomorfismo de subgrafos. El algoritmo comienza ingeniosamente con grafos de consulta mínimamente conectados de tamaño k y encuentra sus mapeos en la red a través del isomorfismo de subgrafos. Después de eso, con la conservación del tamaño del grafo, expande los grafos de consulta considerados previamente borde por borde y calcula la frecuencia de estos grafos expandidos como se mencionó anteriormente. El proceso de expansión continúa hasta alcanzar un grafo completo K k (totalmente conectado con k(k-1) ⁄ 2 arista).
Como se mencionó anteriormente, el algoritmo comienza calculando frecuencias de 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 subgrafos de tamaño 4. T k organiza el proceso de ejecución y proporciona grafos de consulta de manera jerárquica. Estrictamente hablando, el árbol de expansión T k es simplemente un grafo acíclico dirigido o DAG, con su número de raíz k que indica el tamaño del grafo existente en el árbol de expansión y cada uno de sus otros nodos que contiene la matriz de adyacencia de un grafo de consulta de tamaño k distinto . Los nodos en el primer nivel de T k son todos árboles de tamaño k distintos y al recorrer T k en profundidad, los grafos de consulta se expanden con un borde en cada nivel. Un grafo de consulta en un nodo es un subgrafo del grafo de consulta en el hijo de un nodo con una diferencia de borde. El camino más largo en T k consiste en (k 2 -3k+4)/2 aristas y es el camino desde la raíz hasta el nodo hoja que contiene el grafo completo. La generación de árboles de expansión se puede realizar mediante una rutina simple que se explica en [36] .
MODA recorre T k y cuando extrae árboles de consulta del primer nivel de T k calcula sus conjuntos de mapeos y guarda estos mapeos para el siguiente paso. Para consultas que no son árboles de T k , el algoritmo extrae los mapeos asociados con el nodo padre en T k y determina cuál de estos mapeos puede soportar los gráficos de consulta actuales. El proceso continuará hasta que el algoritmo obtenga el gráfico de consulta completo. Los mapeos de árboles de consulta se extraen utilizando el algoritmo Grochow-Kellis. Para calcular la frecuencia de los gráficos de consulta que no son árboles, 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 unió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 subgrafos 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 en particular, se construyen implícitamente árboles con una profundidad máxima de k, con raíz en este nodo y basados en la relación de vecindad. Los hijos de cada nodo incluyen nodos adyacentes entrantes y salientes. Para descender en el árbol, se elige un hijo en cada nivel con la restricción de que un hijo en particular puede incluirse solo si no se ha incluido en ningún nivel superior. Después de haber descendido al nivel más bajo posible, se asciende nuevamente por el árbol y se repite el proceso con la estipulación de que los nodos visitados en rutas anteriores de un descendiente ahora se consideran nodos no visitados. Una restricción final 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 hijos son similares a las condiciones que utilizan los algoritmos GK y ESU para evitar el recuento excesivo de subgrafos.
El protocolo para extraer subgrafos hace uso de las composiciones de un entero. Para la extracción de subgrafos de tamaño k , se deben considerar todas las composiciones posibles del entero k-1 . Las composiciones de k-1 consisten en todas las maneras posibles de expresar k-1 como una suma de enteros positivos. Las sumas en las que el orden de los sumandos difiere se consideran distintas. Una composición se puede expresar como k 2 ,k 3 ,...,k m donde k 2 + k 3 + ... + k m = k-1 . Para contar subgrafos en función de la composición, se seleccionan k i nodos del i -ésimo nivel del árbol para que sean nodos de los subgrafos ( i = 2,3,...,m ). Los k-1 nodos seleccionados junto con el nodo en la raíz definen un subgrafo dentro de la red. Después de descubrir un subgrafo 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 de Kavosh se muestra a continuación:
Recientemente se desarrolló un complemento de Cytoscape llamado CytoKavosh [40] para este software. Está disponible en 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 subgrafos de acuerdo con sus estructuras y encuentra ocurrencias de cada uno de estos subgrafos en un grafo más grande. Uno de los aspectos notables de esta estructura de datos es que al llegar al descubrimiento del motivo de la red, se necesitan evaluar los subgrafos en la red principal. Por lo tanto, no hay necesidad de encontrar los de la red aleatoria que no están en la red principal. Esta puede ser una de las partes que consumen más tiempo en los algoritmos en los que se derivan todos los subgrafos en redes aleatorias.
Un g-trie es un árbol multidireccional que puede almacenar una colección de grafos. Cada nodo del árbol contiene información sobre un único vértice del grafo y sus aristas correspondientes a los nodos ancestros. Un camino desde la raíz hasta una hoja corresponde a un único grafo. 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 , tiene lugar la parte de conteo. La idea principal en el proceso de conteo es retroceder por todos los subgrafos posibles, pero al mismo tiempo hacer 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 . Aprovechando las subestructuras comunes en el sentido de que en un momento dado hay una coincidencia isomórfica parcial para varios subgrafos candidatos diferentes.
Entre los algoritmos mencionados, G-Tries es el más rápido. Sin embargo, el uso excesivo de memoria es el inconveniente de este algoritmo, lo que podría limitar el tamaño de los motivos que puede descubrir un ordenador personal con una memoria media.
ParaMODA [42] y NemoMap [43] son algoritmos rápidos publicados en 2017 y 2018, respectivamente. No son tan escalables como muchos otros. [44]
Las tablas y figuras a continuación muestran los resultados de la ejecución de los algoritmos mencionados en diferentes redes estándar. Estos resultados se han extraído de las fuentes correspondientes, [36] [39] [41] por lo que deben tratarse de forma individual.
Se ha dedicado mucho trabajo experimental a comprender los motivos de red en 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 tal 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) codificado por otro gen. Por lo 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 conforman casi toda la red. La hipótesis principal es que el motivo de red fue seleccionado independientemente por procesos evolutivos de manera convergente, [45] [46] ya que la creación o eliminación de interacciones reguladoras es rápida en la escala de tiempo evolutiva, en relación con la tasa a la que cambian los genes, [45] [46] [47] Además, los experimentos sobre la dinámica generada por los motivos de red en células vivas indican que tienen funciones dinámicas características. Esto sugiere que los motivos de red sirven como bloques de construcción en las redes reguladoras de genes que son beneficiosas para el organismo.
Las funciones asociadas con los motivos de red comunes en las redes de transcripción fueron exploradas y demostradas en varios proyectos de investigación, tanto de manera teórica como experimental. A continuación, se presentan 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 ha demostrado que este motivo cumple dos funciones importantes. La primera función es la aceleración de la respuesta. Se ha demostrado que el NAR acelera la respuesta a las señales tanto teóricamente [48] como experimentalmente. Esto se demostró primero 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 el aumento de la estabilidad de la concentración del producto génico 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) se produce cuando un factor de transcripción aumenta su propia tasa de producción. A diferencia del motivo NAR, este motivo ralentiza el tiempo de respuesta en comparación con la regulación simple. [54] En el caso de una PAR fuerte, el motivo puede conducir a una distribución bimodal de los niveles de proteína 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 objetivo C está regulado por 2 TF A y B y además el TF B también está regulado por el TF A. Dado que cada una de las interacciones reguladoras puede ser positiva o negativa, posiblemente haya ocho tipos de motivos FFL. [56] Dos de esos ocho tipos: el FFL de tipo 1 coherente (C1-FFL) (donde todas las interacciones son positivas) y el FFL de tipo 1 incoherente (I1-FFL) (A activa a C y también activa a B que reprime a C) se encuentran 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 debe considerarse la forma en que las señales de A y B son integradas por el promotor C. En la mayoría de los casos, la FFL es una puerta AND (se requieren A y B 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 ha demostrado que el C1-FFL con una compuerta AND tiene una función de un elemento de "retardo sensible al signo" y un detector de persistencia tanto teóricamente [56] como experimentalmente [58] con el sistema de arabinosa de E. coli . Esto significa que este motivo puede proporcionar filtración de pulsos en la 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 finaliza un pulso persistente será rápido. El comportamiento opuesto emerge en el caso de una compuerta de suma con respuesta rápida y apagado 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 favoreció en cambio un sistema basado en dinámica de regulación de avance con una topología diferente. [60]
El I1-FFL es un generador de pulsos y un acelerador de respuesta. Las dos vías de señalización 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 una manera similar al motivo NAR. La diferencia es que el I1-FFL puede acelerar la respuesta de cualquier gen y no necesariamente de un gen de factor de transcripción. [61] Se asignó una función adicional al motivo de 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 retroalimentación incoherente del producto génico proporcionan adaptación a la cantidad de plantilla de ADN y pueden ser superiores a las combinaciones simples de promotores constitutivos. [64] La regulación de retroalimentación positiva mostró una mejor adaptación que la retroalimentación negativa , y los circuitos basados en la interferencia de ARN fueron los más robustos a la variación en las cantidades de plantilla de ADN. [64] La evolución de novo de I1-FFL en redes reguladoras de genes se ha demostrado computacionalmente en respuesta a la selección para generar un pulso, siendo los I1-FFL más accesibles evolutivamente, pero no superiores, en relación con un motivo alternativo en el que es la salida en lugar de la entrada la 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 activación de los genes. Esto se demostró experimentalmente en el sistema de flagelos de E. coli . [66]
Este motivo se produce cuando un único regulador regula un conjunto de genes sin ninguna regulación adicional. Esto es útil cuando los genes realizan de forma cooperativa una función específica y, por lo tanto, siempre deben activarse de forma 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 entrada múltiple (MIM) surgieron como una generalización de SIM. Sin embargo, las definiciones precisas de SIM y MIM han sido una fuente de inconsistencia. Existen 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 se da 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, uno tiene que obtener más información sobre la forma en que los genes integran las múltiples entradas. Kaplan et al. [69] ha mapeado las funciones de entrada de los genes de utilización de azúcar en E. coli , mostrando diversas formas.
Una generalización interesante de los motivos de red, los motivos de actividad , son patrones de ocurrencia excesiva que se pueden encontrar cuando los nodos y los 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 génica correspondiente, algunos patrones se repiten en exceso dada la estructura de 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 la función; esta es una idea que ha existido durante algún tiempo, para un ejemplo, véase el operón Sin. [72]
La mayoría de los análisis de la función de los motivos se llevan a cabo considerando 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 extraer inferencias sobre la función a partir de la estructura local únicamente; el artículo citado también revisa las críticas y explicaciones alternativas para los datos observados. En [74] se estudia un análisis del impacto de un único módulo de motivo en la dinámica global de una red. Otro trabajo reciente sugiere que ciertas características topológicas de las redes biológicas dan lugar naturalmente a la aparición común de motivos canónicos, lo que cuestiona si las frecuencias de ocurrencia 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 )