stringtranslate.com

Motivo de red

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.

Definiciones

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

Diferentes ocurrencias de un subgrafo en un grafo . (M1 – M4) son diferentes ocurrencias del subgrafo (b) en el grafo (a). Para el concepto de frecuencia F 1 , el conjunto M1, M2, M3, M4 representan todas las coincidencias, por lo que F 1 = 4 . Para F 2 , uno de los dos conjuntos M1, M4 o M2, M3 son posibles coincidencias, F 2 = 2 . Finalmente, para el concepto de frecuencia F 3 , solo se permite una de las coincidencias (M1 a M4), por lo tanto F 3 = 1 . La frecuencia de estos tres conceptos de frecuencia disminuye a medida que se restringe el uso de los elementos de red.

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 .

Historia

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]

Algoritmos de descubrimiento de motivos

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.


Clasificación de algoritmos

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.

Buscador de m

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:

FPF (Mavisto)

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.

Ilustración del árbol de patrones en el algoritmo FPF . [12]

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:

ESU (Fanático)

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:

Buscador de NeMo

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–Kellis

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.

(a) grafo G , (b) ilustración de todos los automorfismos de G que se muestran en (a) . A partir del conjunto AutG podemos obtener un conjunto de condiciones de ruptura de simetría de G dadas por SymG en (c). Solo la primera aplicación en AutG satisface las condiciones SynG; como resultado, al aplicar SymG en el módulo de extensión de isomorfismo, el algoritmo solo enumera cada subgrafo coincidente en la red con G una vez. Nótese que SynG no es necesariamente un conjunto único para un grafo arbitrario G.

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.

Enfoque de codificación por colores

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:

  1. Codificación de colores. Colorea cada vértice de la red de entrada G de forma independiente y uniforme al azar con uno de los k colores.
  2. Conteo. Aplique una rutina de programación dinámica para contar la cantidad de ocurrencias no inducidas de T en las que cada vértice tiene un color único. Para obtener más detalles sobre este paso, consulte [35] .
  3. Repita los dos pasos anteriores O(e k ) veces y sume el número de ocurrencias de T para obtener una estimación del número de sus ocurrencias en G .

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]

MODA

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:

Ilustración del árbol de expansión T4 para grafos de consulta de 4 nodos . En el primer nivel, hay árboles de tamaño k no isomorfos y en cada nivel, se agrega una arista al grafo padre para formar un grafo hijo. En el segundo nivel, hay un grafo con dos aristas alternativas que se muestra con una arista roja discontinua. De hecho, este nodo representa dos grafos expandidos que son isomorfos. [36]

Kavosh

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].

G-Intentos

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 y NemoMap

ParaMODA [42] y NemoMap [43] son ​​algoritmos rápidos publicados en 2017 y 2018, respectivamente. No son tan escalables como muchos otros. [44]

Comparación

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.

Tiempos de ejecución de Grochow–Kellis, mfinder, FANMOD, FPF y MODA para subgrafos desde tres nodos hasta nueve nodos . [36]

Motivos bien establecidos y sus funciones

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.

Autorregulación negativa (NAR)

Representación esquemática de un motivo de autorregulación.

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]

Autorregulación positiva (PAR)

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]

Bucles de retroalimentación (FFL)

Representación esquemática de un motivo de retroalimentación

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.

FFL de tipo 1 coherente (C1-FFL)

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]

FFL tipo 1 incoherente (I1-FFL)

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]

FFL de múltiples salidas

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]

Módulos de entrada única (SIM)

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]

Regulones densos superpuestos (DOR)

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.

Motivos de actividad

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]

Crítica

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]

Véase también

Referencias

  1. ^ Masoudi-Nejad A, Schreiber F, Razaghi MK Z (2012). "Bloques de construcción de redes biológicas: una revisión de los principales algoritmos de descubrimiento de motivos de red". IET Systems Biology . 6 (5): 164–74. doi :10.1049/iet-syb.2011.0011. PMID  23101871.
  2. ^ Diestel, Reinhard (2005). Teoría de grafos (3.ª ed.). Berlín: Springer. ISBN 9783540261827.
  3. ^ abc Milo R, Shen-Orr SS, Itzkovitz S, Kashtan N, Chklovskii D, Alon U (2002). "Motivos de red: bloques de construcción simples de redes complejas". Science . 298 (5594): 824–827. Bibcode :2002Sci...298..824M. CiteSeerX 10.1.1.225.8750 . doi :10.1126/science.298.5594.824. PMID  12399590. S2CID  9884096. 
  4. ^ Albert R, Barabási AL (2002). "Mecánica estadística de redes complejas". Reseñas de Física Moderna . 74 (1): 47–49. arXiv : cond-mat/0106096 . Bibcode :2002RvMP...74...47A. CiteSeerX 10.1.1.242.4753 . doi :10.1103/RevModPhys.74.47. S2CID  60545. 
  5. ^ ab Milo R, Itzkovitz S, Kashtan N, Levitt R, Shen-Orr S, Ayzenshtat I, Sheffer M, Alon U (2004). "Superfamilias de redes diseñadas y evolucionadas". Science . 303 (5663): 1538–1542. Bibcode :2004Sci...303.1538M. doi :10.1126/science.1089167. PMID  15001784. S2CID  14760882.
  6. ^ ab Schwöbbermeyer, H (2008). "Network Motifs". En Junker BH, Schreiber F (ed.). Análisis de redes biológicas . Hoboken, Nueva Jersey: John Wiley & Sons. págs. 85–108.
  7. ^ Bornholdt, S; Schuster, HG (2003). Manual de grafos y redes: del genoma a Internet . p. 417. Bibcode :2003hgnf.book.....B. {{cite encyclopedia}}: |journal=ignorado ( ayuda )
  8. ^ abc Ciriello G, Guerra C (2008). "Una revisión de modelos y algoritmos para el descubrimiento de motivos en redes de interacción proteína-proteína". Briefings in Functional Genomics and Proteomics . 7 (2): 147–156. doi : 10.1093/bfgp/eln015 . PMID  18443014.
  9. ^ abcdef Kashtan N, Itzkovitz S, Milo R, Alon U (2004). "Algoritmo de muestreo eficiente para estimar concentraciones de subgrafos y detectar motivos de red". Bioinformática . 20 (11): 1746–1758. doi : 10.1093/bioinformatics/bth163 . PMID  15001476.
  10. ^ abcdef Wernicke S (2006). "Detección eficiente de motivos de red". Transacciones IEEE/ACM sobre biología computacional y bioinformática . 3 (4): 347–359. CiteSeerX 10.1.1.304.2576 . doi :10.1109/tcbb.2006.51. PMID  17085844. S2CID  6188339. 
  11. ^ Picard F, Daudin JJ, Schbath S , Robin S (2005). "Evaluación de la excepcionalidad de los motivos de red". J. Comp. Bio . 15 (1): 1–20. CiteSeerX 10.1.1.475.4300 . doi :10.1089/cmb.2007.0137. PMID  18257674. 
  12. ^ abc Schreiber F, Schwöbbermeyer H (2005). "Conceptos de frecuencia y detección de patrones para el análisis de motivos en redes". Transactions on Computational Systems Biology III . Apuntes de clase en informática. Vol. 3737. págs. 89–104. CiteSeerX 10.1.1.73.1130 . doi :10.1007/11599128_7. ISBN  978-3-540-30883-6.
  13. ^ Holland, PW y Leinhardt, S. (1974). El análisis estadístico de la estructura local en las redes sociales. Documento de trabajo n.º 44, Oficina Nacional de Investigación Económica.
  14. ^ Holland, P. y Leinhardt, S. (1975). El análisis estadístico de la estructura local en redes sociales. Metodología sociológica, David Heise, ed. San Francisco: Josey-Bass.
  15. ^ Holland, PW, y Leinhardt, S. (1976). Estructura local en redes sociales. Metodología sociológica, 7, 1-45.
  16. ^ Holland, PW y Leinhardt, S. (1977). Un método para detectar la estructura en datos sociométricos. En Social Networks (pp. 411-432). Academic Press.
  17. ^ abc Shen-Orr SS, Milo R, Mangan S, Alon U (mayo de 2002). "Motivos de red en la red de regulación transcripcional de Escherichia coli". Nat. Genet . 31 (1): 64–8. doi : 10.1038/ng881 . PMID :  11967538. S2CID  : 2180121.
  18. ^ Eichenberger P, Fujita M, Jensen ST, et al. (octubre de 2004). "El programa de transcripción génica para un único tipo de célula diferenciadora durante la esporulación en Bacillus subtilis". PLOS Biology . 2 (10): e328. doi : 10.1371/journal.pbio.0020328 . PMC 517825 . PMID  15383836.  Icono de acceso abierto
  19. ^ Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U (octubre de 2002). "Motivos de red: bloques de construcción simples de redes complejas". Science . 298 (5594): 824–7. Bibcode :2002Sci...298..824M. CiteSeerX 10.1.1.225.8750 . doi :10.1126/science.298.5594.824. PMID  12399590. S2CID  9884096. 
  20. ^ Lee TI, Rinaldi NJ, Robert F, et al. (octubre de 2002). "Redes reguladoras de la transcripción en Saccharomyces cerevisiae". Science . 298 (5594): 799–804. Bibcode :2002Sci...298..799L. doi :10.1126/science.1075090. PMID  12399584. S2CID  4841222.
  21. ^ Odom DT, Zizlsperger N, Gordon DB, et al. (febrero de 2004). "Control de la expresión génica del páncreas y el hígado mediante factores de transcripción HNF". Science . 303 (5662): 1378–81. Bibcode :2004Sci...303.1378O. doi :10.1126/science.1089769. PMC 3012624 . PMID  14988562. 
  22. ^ ab Boyer LA, Lee TI, Cole MF, et al. (septiembre de 2005). "Circuitos reguladores de la transcripción central en células madre embrionarias humanas". Cell . 122 (6): 947–56. doi :10.1016/j.cell.2005.08.020. PMC 3006442 . PMID  16153702. 
  23. ^ Iranfar N, Fuller D, Loomis WF (febrero de 2006). "Regulación transcripcional de genes post-agregación en Dictyostelium por un ciclo de retroalimentación que involucra GBF y LagC". Dev. Biol . 290 (2): 460–9. doi : 10.1016/j.ydbio.2005.11.035 . PMID  16386729.
  24. ^ Ma'ayan A, Jenkins SL, Neves S, et al. (agosto de 2005). "Formación de patrones reguladores durante la propagación de señales en una red celular de mamíferos". Science . 309 (5737): 1078–83. Bibcode :2005Sci...309.1078M. doi :10.1126/science.1108876. PMC 3032439 . PMID  16099987. 
  25. ^ Ptacek J, Devgan G, Michaud G, et al. (diciembre de 2005). "Análisis global de la fosforilación de proteínas en levaduras" (PDF) . Nature (manuscrito enviado). 438 (7068): 679–84. Bibcode :2005Natur.438..679P. doi :10.1038/nature04187. PMID  16319894. S2CID  4332381.
  26. ^ "Acc-Motif: Detección acelerada de motivos".
  27. ^ Schreiber F, Schwobbermeyer H (2005). "MAVisto: una herramienta para la exploración de motivos de red". Bioinformática . 21 (17): 3572–3574. doi : 10.1093/bioinformatics/bti556 . PMID  16020473.
  28. ^ abc McKay BD (1981). "Isomorfismo gráfico práctico". Congressus Numerantium . 30 : 45–87. arXiv : 1301.1493 . Código Bibliográfico :2013arXiv1301.1493M.
  29. ^ abc McKay BD (1998). "Generación exhaustiva sin isomorfos". Revista de algoritmos . 26 (2): 306–324. doi :10.1006/jagm.1997.0898.
  30. ^ ab Chen J, Hsu W, Li Lee M, et al. (2006). NeMoFinder: disección de interacciones proteína-proteína en todo el genoma con motivos de red a escala meso . 12.ª conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos. Filadelfia, Pensilvania, EE. UU., págs. 106-115.
  31. ^ Huan J, Wang W, Prins J, et al. (2004). SPIN: minería de subgrafos de máxima frecuencia a partir de bases de datos de grafos . Décima conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos. págs. 581–586.
  32. ^ Uetz P, Giot L, Cagney G, et al. (2000). "Un análisis exhaustivo de las interacciones proteína-proteína en Saccharomyces cerevisiae". Nature . 403 (6770): 623–627. Bibcode :2000Natur.403..623U. doi :10.1038/35001009. PMID  10688190. S2CID  4352495.
  33. ^ abcd Grochow JA, Kellis M (2007). Descubrimiento de motivos de red mediante enumeración de subgrafos y ruptura de simetría (PDF) . RECOMB. págs. 92–106. doi :10.1007/978-3-540-71681-5_7.
  34. ^ ab Grochow JA (2006). Sobre la estructura y evolución de las redes de interacción de proteínas (PDF) . Tesis de maestría en ingeniería, Instituto Tecnológico de Massachusetts, Departamento de Ingeniería Eléctrica y Ciencias de la Computación.
  35. ^ abc Alon N; Dao P; Hajirasouliha I; Hormozdiari F; Sahinalp SC (2008). "Recuento y descubrimiento de motivos de redes biomoleculares mediante codificación de colores". Bioinformática . 24 (13): i241–i249. doi :10.1093/bioinformatics/btn163. PMC 2718641 . PMID  18586721. 
  36. ^ abcde Omidi S, Schreiber F, Masoudi-Nejad A (2009). "MODA: un algoritmo eficiente para el descubrimiento de motivos de red en redes biológicas". Genes Genet Syst . 84 (5): 385–395. doi : 10.1266/ggs.84.385 . PMID  20154426.
  37. ^ Barabasi AL, Albert R (1999). "Aparición del escalamiento en redes aleatorias". Science . 286 (5439): 509–512. arXiv : cond-mat/9910332 . Bibcode :1999Sci...286..509B. doi :10.1126/science.286.5439.509. PMID  10521342. S2CID  524106.
  38. ^ Vázquez A, Dobrin R, Sergi D, et al. (2004). "La relación topológica entre los atributos a gran escala y los patrones de interacción local de redes complejas". PNAS . 101 (52): 17940–17945. arXiv : cond-mat/0408431 . Bibcode :2004PNAS..10117940V. doi : 10.1073/pnas.0406024101 . PMC 539752 . PMID  15598746. 
  39. ^ abcd Kashani ZR, Ahrabian H, Elahi E, Nowzari-Dalini A, Ansari ES, Asadi S, Mohammadi S, Schreiber F, Masoudi-Nejad A (2009). "Kavosh: un nuevo algoritmo para encontrar motivos de red". Bioinformática BMC . 10 (318): 318. doi : 10.1186/1471-2105-10-318 . PMC 2765973 . PMID  19799800.  Icono de acceso abierto
  40. ^ Ali Masoudi-Nejad; Mitra Anasariola; Ali Salehzadeh-Yazdi; Sahand Khakabimamaghani (2012). "CytoKavosh: un complemento de Cytoscape para encontrar motivos de red en grandes redes biológicas". PLOS ONE . ​​7 (8): e43287. Bibcode :2012PLoSO...743287M. doi : 10.1371/journal.pone.0043287 . PMC 3430699 . PMID  22952659.  Icono de acceso abierto
  41. ^ abcd Ribeiro P, Silva F (2010). G-Tries: una estructura de datos eficiente para descubrir motivos de red. ACM 25th Symposium On Applied Computing - Bioinformatics Track. Sierre, Suiza. págs. 1559–1566.
  42. ^ Mbadiwe, Somadina; Kim, Wooyoung (noviembre de 2017). "ParaMODA: mejora de la búsqueda de patrones de subgrafos centrados en motivos en redes PPI". Conferencia internacional IEEE sobre bioinformática y biomedicina (BIBM) de 2017. págs. 1723–1730. doi :10.1109/BIBM.2017.8217920. ISBN 978-1-5090-3050-7. S2CID  5806529. Archivado desde el original el 4 de febrero de 2023. Consultado el 11 de septiembre de 2020 .
  43. ^ "NemoMap: algoritmo mejorado de descubrimiento de motivos de redes centradas en motivos". Revista Advances in Science, Technology and Engineering Systems . 2018. Archivado desde el original el 2023-02-04 . Consultado el 2020-09-11 .
  44. ^ Patra, Sabyasachi; Mohapatra, Anjali (2020). "Revisión de herramientas y algoritmos para el descubrimiento de motivos de red en redes biológicas". IET Systems Biology . 14 (4): 171–189. doi : 10.1049/iet-syb.2020.0004 . ISSN  1751-8849. PMC 8687426 . PMID  32737276. 
  45. ^ ab Babu MM, Luscombe NM, Aravind L, Gerstein M, Teichmann SA (junio de 2004). "Estructura y evolución de las redes reguladoras de la transcripción". Current Opinion in Structural Biology . 14 (3): 283–91. CiteSeerX 10.1.1.471.9692 . doi :10.1016/j.sbi.2004.05.004. PMID  15193307. 
  46. ^ ab Conant GC, Wagner A (julio de 2003). "Evolución convergente de circuitos genéticos". Nat. Genet . 34 (3): 264–6. doi :10.1038/ng1181. PMID  12819781. S2CID  959172.
  47. ^ Dekel E, Alon U (julio de 2005). "Optimalidad y ajuste evolutivo del nivel de expresión de una proteína". Nature . 436 (7050): 588–92. Bibcode :2005Natur.436..588D. doi :10.1038/nature03842. PMID  16049495. S2CID  2528841.
  48. ^ Zabet NR (septiembre de 2011). "Retroalimentación negativa y límites físicos de los genes". Journal of Theoretical Biology . 284 (1): 82–91. arXiv : 1408.1869 . Bibcode :2011JThBi.284...82Z. CiteSeerX 10.1.1.759.5418 . doi :10.1016/j.jtbi.2011.06.021. PMID  21723295. S2CID  14274912. 
  49. ^ Rosenfeld N, Elowitz MB, Alon U (noviembre de 2002). "La autorregulación negativa acelera los tiempos de respuesta de las redes de transcripción". J. Mol. Biol . 323 (5): 785–93. CiteSeerX 10.1.1.126.2604 . doi :10.1016/S0022-2836(02)00994-4. PMID  12417193. 
  50. ^ Camas FM, Blázquez J, Poyatos JF (agosto de 2006). "Control autógeno y no autógeno de la respuesta en una red genética". Proc. Natl. Sci. USA . 103 (34): 12718–23. Bibcode :2006PNAS..10312718C. doi : 10.1073/pnas.0602119103 . PMC 1568915 . PMID  16908855. 
  51. ^ Becskei A, Serrano L (junio de 2000). "Ingeniería de la estabilidad en redes genéticas mediante autorregulación". Nature . 405 (6786): 590–3. Bibcode :2000Natur.405..590B. doi :10.1038/35014651. PMID  10850721. S2CID  4407358.
  52. ^ Dublanche Y, Michalodimitrakis K, Kümmerer N, Foglierini M, Serrano L (2006). "Ruido en bucles de retroalimentación negativa de la transcripción: simulación y análisis experimental". Mol. Syst. Biol . 2 (1): 41. doi :10.1038/msb4100081. PMC 1681513. PMID  16883354 . 
  53. ^ Shimoga V, White J, Li Y, Sontag E, Bleris L (2013). "Autorregulación negativa de transgenes sintéticos en mamíferos". Mol. Syst. Biol . 9 : 670. doi :10.1038/msb.2013.27. PMC 3964311. PMID  23736683 . 
  54. ^ Maeda YT, Sano M (junio de 2006). "Dinámica reguladora de redes de genes sintéticos con retroalimentación positiva". J. Mol. Biol . 359 (4): 1107–24. doi :10.1016/j.jmb.2006.03.064. PMID  16701695.
  55. ^ Becskei A, Séraphin B, Serrano L (mayo de 2001). "Retroalimentación positiva en redes génicas eucariotas: diferenciación celular mediante conversión de respuesta gradual a binaria". EMBO J . 20 (10): 2528–35. doi :10.1093/emboj/20.10.2528. PMC 125456 . PMID  11350942. 
  56. ^ abc Mangan S, Alon U (octubre de 2003). "Estructura y función del motivo de red de bucle de alimentación hacia adelante". Proc. Natl. Sci. USA . 100 (21): 11980–5. Bibcode :2003PNAS..10011980M. doi : 10.1073/pnas.2133841100 . PMC 218699 . PMID  14530388. 
  57. ^ Ma HW, Kumar B, Ditges U, Gunzer F, Buer J, Zeng AP (2004). "Una red reguladora transcripcional extendida de Escherichia coli y análisis de su estructura jerárquica y motivos de red". Nucleic Acids Res . 32 (22): 6643–9. doi :10.1093/nar/gkh1009. PMC 545451 . PMID  15604458. 
  58. ^ Mangan S, Zaslaver A, Alon U (noviembre de 2003). "El bucle de retroalimentación coherente sirve como un elemento de retardo sensible a la señal en las redes de transcripción". J. Mol. Biol . 334 (2): 197–204. CiteSeerX 10.1.1.110.4629 . doi :10.1016/j.jmb.2003.09.049. PMID  14607112. 
  59. ^ Kalir S, Mangan S, Alon U (2005). "Un bucle de retroalimentación coherente con una función de entrada SUM prolonga la expresión de flagelos en Escherichia coli". Mol. Syst. Biol . 1 (1): E1–E6. doi :10.1038/msb4100010. PMC 1681456. PMID  16729041 . 
  60. ^ Xiong, Kun; Lancaster, Alex K.; Siegal, Mark L.; Masel, Joanna (3 de junio de 2019). "La regulación de avance evoluciona de forma adaptativa a través de la dinámica en lugar de la topología cuando hay ruido intrínseco". Nature Communications . 10 (1): 2418. Bibcode :2019NatCo..10.2418X. doi :10.1038/s41467-019-10388-6. PMC 6546794 . PMID  31160574. 
  61. ^ Mangan S, Itzkovitz S, Zaslaver A, Alon U (marzo de 2006). "El bucle de retroalimentación incoherente acelera el tiempo de respuesta del sistema gal de Escherichia coli ". J. Mol. Biol . 356 (5): 1073–81. CiteSeerX 10.1.1.184.8360 . doi :10.1016/j.jmb.2005.12.003. PMID  16406067. 
  62. ^ Entus R, Aufderheide B, Sauro HM (agosto de 2007). "Diseño e implementación de tres sensores de concentración biológica basados ​​en motivos de retroalimentación incoherente". Syst Synth Biol . 1 (3): 119–28. doi :10.1007/s11693-007-9008-6. PMC 2398716 . PMID  19003446. 
  63. ^ Kaplan S, Bren A, Dekel E, Alon U (2008). "El bucle de retroalimentación incoherente puede generar funciones de entrada no monótonas para los genes". Mol. Syst. Biol . 4 (1): 203. doi :10.1038/msb.2008.43. PMC 2516365. PMID  18628744 . 
  64. ^ ab Bleris L, Xie Z, Glass D, Adadey A, Sontag E, Benenson Y (2011). "Los circuitos de retroalimentación incoherente sintéticos muestran adaptación a la cantidad de su plantilla genética". Mol. Syst. Biol . 7 (1): 519. doi :10.1038/msb.2011.49. PMC 3202791. PMID  21811230 . 
  65. ^ Xiong, Kun; Gerstein, Mark; Masel, Joanna (5 de noviembre de 2021). "Las diferencias en la accesibilidad evolutiva determinan qué motivo regulador igualmente eficaz evoluciona para generar pulsos". Genética . 219 (3): iyab140. doi :10.1093/genetics/iyab140. PMC 8570775 . PMID  34740240. 
  66. ^ Kalir S, McClure J, Pabbaraju K, et al. (junio de 2001). "Ordenamiento de genes en una vía de flagelos mediante análisis de la cinética de expresión de bacterias vivas". Science . 292 (5524): 2080–3. doi :10.1126/science.1058758. PMID  11408658. S2CID  14396458.
  67. ^ Zaslaver A, Mayo AE, Rosenberg R, et al. (mayo de 2004). "Programa de transcripción justo a tiempo en vías metabólicas". Nat. Genet . 36 (5): 486–91. doi : 10.1038/ng1348 . PMID:  15107854.
  68. ^ Konagurthu AS, Lesk AM (2008). "Módulos de entrada únicos y múltiples en redes reguladoras". Proteínas . 73 (2): 320–324. doi :10.1002/prot.22053. PMID  18433061. S2CID  35715566.
  69. ^ Kaplan S, Bren A, Zaslaver A, Dekel E, Alon U (marzo de 2008). "Diversas funciones de entrada bidimensionales controlan los genes de azúcar bacterianos". Mol. Cell . 29 (6): 786–92. doi :10.1016/j.molcel.2008.01.021. PMC 2366073 . PMID  18374652. 
  70. ^ Chechik G, Oh E, Rando O, Weissman J, Regev A, Koller D (noviembre de 2008). "Los motivos de actividad revelan principios de sincronización en el control transcripcional de la red metabólica de la levadura". Nat. Biotechnol . 26 (11): 1251–9. doi :10.1038/nbt.1499. PMC 2651818. PMID 18953355  . 
  71. ^ Ingram PJ, Stumpf MP, Stark J (2006). "Motivos de red: la estructura no determina la función". BMC Genomics . 7 : 108. doi : 10.1186/1471-2164-7-108 . PMC 1488845 . PMID  16677373.  Icono de acceso abierto
  72. ^ Voigt CA, Wolf DM, Arkin AP (marzo de 2005). "El operón sin de Bacillus subtilis: un motivo de red evolutivo". Genética . 169 (3): 1187–202. doi :10.1534/genetics.104.031955. PMC 1449569 . PMID  15466432. Archivado desde el original el 2023-02-04 . Consultado el 2011-02-26 . 
  73. ^ Knabe JF, Nehaniv CL, Schilstra MJ (2008). "¿Reflejan los motivos una función evolucionada? No hay evolución convergente de las topologías de subgrafos de redes reguladoras genéticas". BioSystems . 94 (1–2): 68–74. Bibcode :2008BiSys..94...68K. doi :10.1016/j.biosystems.2008.05.012. PMID  18611431.
  74. ^ Taylor D, Restrepo JG (2011). "Conectividad de red durante fusiones y crecimiento: Optimización de la adición de un módulo". Physical Review E . 83 (6): 66112. arXiv : 1102.4876 . Bibcode :2011PhRvE..83f6112T. doi :10.1103/PhysRevE.83.066112. PMID  21797446. S2CID  415932.
  75. ^ Konagurthu, Arun S.; Lesk, Arthur M. (23 de abril de 2008). "Módulos de entrada únicos y múltiples en redes reguladoras". Proteínas: estructura, función y bioinformática . 73 (2): 320–324. doi :10.1002/prot.22053. PMID  18433061. S2CID  35715566.
  76. ^ Konagurthu AS, Lesk AM (2008). "Sobre el origen de los patrones de distribución de motivos en redes biológicas". BMC Syst Biol . 2 : 73. doi : 10.1186/1752-0509-2-73 . PMC 2538512 . PMID  18700017.  Icono de acceso abierto

Enlaces externos