Los motivos de la red son subgráficos o patrones recurrentes y estadísticamente significativos de un gráfico más grande . Todas las redes, incluidas las redes biológicas , las redes sociales, las redes tecnológicas (por ejemplo, las redes de computadoras y los circuitos eléctricos) y más, se pueden representar como gráficos, que incluyen una amplia variedad de subgrafos.
Los motivos de red son subgráficos que se repiten en una red específica o incluso entre varias redes. Cada uno de estos subgráficos, definido por un patrón particular de interacciones entre vértices, puede reflejar un marco en el que determinadas funciones se logran de manera eficiente. De hecho, los motivos son de notable importancia en gran parte porque pueden reflejar propiedades funcionales. Recientemente, 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 la red pueden proporcionar una visión profunda de las capacidades funcionales de la red, su detección es un desafío computacional.
Definición
Sean G = (V, E) y G ′ = (V ′, E ′) dos gráficas. El gráfico G ′ es un subgráfico del gráfico G (escrito como G ′ ⊆ G ) si V ′ ⊆ V y E ′ ⊆ E ∩ (V ′ × V ′) . Si G '⊆ G y G' contiene todos los bordes ⟨u, v⟩ ∈ E con u, v ∈ V ' , entonces G' es una sub-gráfico inducida de G . Llamamos a G ′ y G isomorfos (escritos como G ′ ↔ G ), si existe una biyección (correspondencia uno a uno) f: V ′ → V con ⟨u, v⟩ ∈ E ′ ⇔ ⟨f (u) , f (v)⟩ ∈ E para todo u, v ∈ V ′ . El mapeo f se denomina isomorfismo entre G y G ′ . [2]
Cuando G "⊂ G y existe un isomorfismo entre el sub-gráfico G" y un gráfico de G ' , este mapeo representa un aspecto de G' en G . El número de apariciones de gráfico de G ' en G se denomina frecuencia F G de G' en G . Un gráfico se denomina recurrente (o frecuente ) en G cuando su frecuencia F G (G ′) está por encima de un umbral o valor de corte predefinido. Usamos patrones de términos y subgráficos frecuentes en esta revisión de manera intercambiable. Hay un conjunto Ω (G) de grafos aleatorios correspondientes a la null-modelo asociado a G . Debemos elegir N grafos aleatorios uniformemente de Ω (G) y el cálculo de la frecuencia para una determinada frecuente sub-gráfico 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 esto patrón recurrente significativa y por lo tanto tratar G' como una red motivo para G . Para un pequeño gráfico G ′ , la red G y un conjunto de redes aleatorias R (G) ⊆ Ω (R) , donde R (G) = N , la puntuación Z de la frecuencia de G ′ viene dada por
donde μ R (G ′) y σ R (G ′) representan la desviación media y estándar de la frecuencia en el conjunto R (G) , respectivamente. [3] [4] [5] [6] [7] [8] Cuanto mayor es la Z (G ′) , más significativo es el subgráfico G ′ como motivo. Alternativamente, otra medida en la prueba de hipótesis estadísticas 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 aleatorizada. [6] Un sub-gráfico con un valor de 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 subgráfico de tamaño n particular G ′ en la red G se refiere a la relación entre la apariencia del subgráfico en la red y las frecuencias totales de los subgráficos no isomórficos de tamaño n , que está formulado por
donde el índice i se define sobre el conjunto de todos los gráficos de tamaño n no isomórficos. Se define otra medida estadística para evaluar motivos de red, pero rara vez se utiliza en algoritmos conocidos. Esta medida es introducida por Picard et al. en 2008 y utilizó la distribución de Poisson, en lugar de la distribución normal gaussiana que se utiliza implícitamente anteriormente. [11]
Además, se han propuesto tres conceptos específicos de frecuencia de subgráficos. [12] Como ilustra la figura, el primer concepto de frecuencia F 1 considera todas las coincidencias de un gráfico en la red original. Esta definición es similar a la que hemos introducido anteriormente. El segundo concepto F 2 se define como el número máximo de instancias de borde disjunto de un gráfico dado en la red original. Y finalmente, el concepto de frecuencia F 3 implica coincidencias con bordes y nodos disjuntos. Por lo tanto, los dos conceptos F 2 y F 3 restringen el uso de elementos del gráfico y, como se puede inferir, la frecuencia de un subgráfico disminuye al imponer restricciones al uso de elementos de red. Como resultado, un algoritmo de detección de motivos de red pasaría por encima de más subgráficos candidatos si insistimos en los conceptos de frecuencia F 2 y F 3 .
Historia
El estudio de motivos de redes fue iniciado por Holland y Leinhardt [13] [14] [15] [16], quienes introdujeron el concepto de un censo de redes en tríada. Introdujeron métodos para enumerar varios tipos de configuraciones de subgrafos y probar si los recuentos de subgrafos son estadísticamente diferentes de los esperados en redes aleatorias.
Esta idea fue generalizada aún más en 2002 por Uri Alon y su grupo [17] cuando se descubrieron motivos de red en la red de regulación de genes (transcripción) de la bacteria E. coli y luego en un gran conjunto de redes naturales. Desde entonces, se han realizado un número considerable de estudios sobre el tema. Algunos de estos estudios se centran en las aplicaciones biológicas, mientras que otros se centran en la teoría computacional de motivos de redes.
Los estudios biológicos tratan de interpretar los motivos detectados para redes biológicas. Por ejemplo, en el trabajo siguiente, [17] los motivos de red encontrados en E. coli se descubrieron en las redes de transcripción de otras bacterias [18] , así como 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 las redes neuronales y las 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 ahora se han proporcionado varios algoritmos diferentes, que se desarrollan 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 desafiante problema del descubrimiento de motivos de red (NM). Estos algoritmos se pueden clasificar en varios paradigmas, como métodos de recuento exacto, métodos de muestreo, métodos de crecimiento de patrones, etc. Sin embargo, el problema de descubrimiento de motivos comprende dos pasos principales: primero, calcular el número de ocurrencias de un sub-gráfico y luego, evaluar la importancia del sub-gráfico. La recurrencia es significativa si es detectable mucho más de lo esperado. En términos generales, el número esperado de apariciones de un subgráfico se puede determinar mediante un modelo nulo, que se define mediante un conjunto de redes aleatorias con algunas de las mismas propiedades que la red original.
Hasta 2004, el único método de recuento 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 fue computacionalmente factible. Por lo tanto, se necesitaba un nuevo enfoque para este problema.
Aquí, se da una revisión sobre los aspectos computacionales de los algoritmos principales y se discuten sus beneficios e inconvenientes relacionados desde una perspectiva algorítmica.
mfinder
Kashtan y col. publicó 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 borde en toda la red. Este algoritmo estima las concentraciones de los subgráficos 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 sub-gráfico de tamaño dos, y luego expande el sub-gráfico eligiendo un borde aleatorio que incide en el sub-gráfico actual. Después de eso, continúa eligiendo bordes vecinos aleatorios hasta que se obtiene un sub-gráfico de tamaño n. Finalmente, el sub-gráfico muestreado se expande para incluir todos los bordes que existen en la red entre estos n nodos. Cuando un algoritmo utiliza un enfoque de muestreo, la toma de muestras no sesgadas 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. propuso un esquema de ponderación que asigna diferentes pesos a los diferentes sub-gráficos dentro de la red. [9] El principio subyacente de la asignación del peso es aprovechar la información de la probabilidad de muestreo para cada subgráfico, es decir, los subgráficos probables obtendrán comparativamente menos ponderaciones en comparación con los subgráficos improbables; por lo tanto, el algoritmo debe calcular la probabilidad de muestreo de cada subgráfico que se ha muestreado. Esta técnica de ponderación ayuda a mfinder a determinar las concentraciones de los subgráficos de manera imparcial.
Al expandirse para incluir un fuerte contraste con la búsqueda exhaustiva, el tiempo computacional del algoritmo es sorprendentemente 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 subgráfico de tamaño n de la red. Por otro lado, no hay un análisis en [9] sobre el tiempo de clasificación de los subgráficos muestreados que requiera resolver el problema de isomorfismo del gráfico para cada muestra del subgráfico. Además, el cálculo del peso del sub-gráfico impone un esfuerzo de cálculo adicional al algoritmo. Pero es inevitable decir que el algoritmo puede muestrear el mismo subgráfico varias veces, pasando tiempo sin recopilar 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 exhaustivo; sin embargo, solo determina aproximadamente las concentraciones de los subgráficos. Este algoritmo puede encontrar motivos hasta el tamaño 6 debido a su implementación principal, y como resultado da el motivo más significativo, no todos los demás también. Además, es necesario mencionar que esta herramienta no tiene opción de presentación visual. El algoritmo de muestreo se muestra brevemente:
mfinder |
---|
Definiciones: E s es el conjunto de aristas seleccionadas. V s es el conjunto de todos los nodos que son tocados por los bordes en E . |
Init V s y E s para ser conjuntos vacíos. 1. Elija una arista aleatoria e 1 = (v i , v j ) . Actualizar E s = {e 1 }, V s = {v i , v j } 2. Haga una lista L de todos los bordes vecinos de E s . Omita desde L todos los bordes entre los miembros de V s . 3. Elegir un borde al azar e = {v k , v l } de L . Actualice E s = E s ⋃ {e }, V s = V s ⋃ {v k , v l }. 4. Repita los pasos 2-3 hasta completar un subgrafo de n nodos (hasta | V s | = n ). 5. Calcule la probabilidad de muestrear el subgráfico de n nodos seleccionado. |
FPF (Mavisto)
Schreiber y Schwöbbermeyer [12] propusieron un algoritmo llamado buscador de patrones flexibles (FPF) para extraer subgráficos frecuentes de una red de entrada y lo implementaron en un sistema llamado Mavisto . [27] Su algoritmo explota la propiedad de cierre descendente que es aplicable a los conceptos de frecuencia F 2 y F 3 . La propiedad de cierre hacia abajo afirma que la frecuencia de los subgráficos disminuye monótonamente al aumentar el tamaño de los subgráficos; sin embargo, esta propiedad no se aplica necesariamente al concepto de frecuencia F 1 . FPF se basa en un árbol de patrones (ver figura) que consta de nodos que representan diferentes gráficos (o patrones), donde el padre de cada nodo es un subgráfico de sus nodos hijos; en otras palabras, el gráfico correspondiente del nodo de cada árbol de patrones se expande agregando un nuevo borde al gráfico de su nodo principal.
Al principio, el algoritmo FPF enumera y mantiene la información de todas las coincidencias de un subgráfico ubicado en la raíz del árbol de patrones. Luego, uno por uno, construye nodos secundarios del nodo anterior en el árbol de patrones agregando un borde apoyado por un borde coincidente en el gráfico de destino, e intenta expandir toda la información anterior sobre coincidencias con el nuevo subgráfico (nodo hijo). En el siguiente paso, decide si la frecuencia del patrón actual es menor que un umbral predefinido o no. Si es más bajo y si se mantiene el cierre hacia abajo, FPF puede abandonar ese camino y no atravesar más en esta parte del árbol; como resultado, se evita el cálculo innecesario. Este procedimiento se continúa hasta que no quede ningún camino por recorrer.
La ventaja del algoritmo es que no considera subgráficos infrecuentes e intenta finalizar el proceso de enumeración lo antes posible; por lo tanto, solo dedica tiempo a los nodos prometedores del á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 ruta del árbol de patrones de forma independiente. Sin embargo, FPF es más útil para los conceptos de frecuencia F 2 y F 3 , porque el cierre descendente no es aplicable a F 1 . Sin embargo, el árbol de patrones sigue siendo práctico para F 1 si el algoritmo se ejecuta en paralelo. Otra ventaja del algoritmo es que la implementación de este algoritmo no tiene limitación en el tamaño del motivo, lo que lo hace más susceptible de mejoras. El pseudocódigo de FPF (Mavisto) se muestra a continuación:
Mavisto |
---|
Datos: Gráfico G , tamaño del patrón objetivo t , concepto de frecuencia F Resultado: Establezca R de patrones de tamaño t con la frecuencia máxima. |
R ← φ , f máx ← 0 P ← patrón de inicio p1 de tamaño 1 M p 1 ← todas las coincidencias de p 1 en G Mientras que P ≠ φ hacer P max ← seleccione todos los patrones de P con tamaño máximo. P ← seleccionar patrón con frecuencia máxima de P max Ε = ExtensionLoop (G, p, M p ) Para cada patrón p ∈ E Si F = F 1 entonces f ← tamaño (M p ) Else f ← Conjunto máximo independiente (F, M p ) Final Si tamaño (p) = t entonces Si f = f max entonces R ← R ⋃ {p } De lo contrario, si f> f max, entonces R ← {p }; f máx ← f Final Demás Si F = F 1 o f ≥ f max entonces P ← P ⋃ {p } Final Final Final Final |
ESU (FANMOD)
El sesgo de muestreo de Kashtan et al. [9] proporcionó un gran impulso para diseñar mejores algoritmos para el problema del descubrimiento de NM. Aunque Kashtan et al. Intentado solucionar este inconveniente mediante un esquema de ponderación, este método impuso una sobrecarga no deseada en el tiempo de ejecución, así como una implementación más complicada. Esta herramienta es una de las más útiles, ya que admite opciones visuales y 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 se implementa 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 exacto ESU , se ha implementado como una aplicación llamada FANMOD . [10] RAND-ESU es un algoritmo de descubrimiento de NM aplicable tanto para redes dirigidas como no dirigidas, explota eficazmente un muestreo de nodos no sesgado en toda la red y evita el recuento excesivo de subgráficos más de una vez. Además, RAND-ESU utiliza un enfoque analítico novedoso llamado DIRECTO para determinar la significación del sub-gráfico en lugar de utilizar un conjunto de redes aleatorias como modelo nulo. El método DIRECTO estima la concentración del sub-gráfico sin generar explícitamente redes aleatorias. [10] Empíricamente, el método DIRECTO es más eficiente en comparación con el conjunto de red aleatorio en el caso de subgráficos con una concentración muy baja; sin embargo, el modelo nulo clásico es más rápido que el método DIRECTO para subgráficos 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 los 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 subgráficos inducidos de tamaño k , sea S k este conjunto. ESU se puede implementar como una función recursiva; la ejecución de esta función se puede mostrar como una estructura en forma de árbol de profundidad k , denominada ESU-Tree (ver figura). Cada uno de los nodos 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 de destino que son adyacentes y establecen un sub-gráfico parcial de tamaño | SUB | ≤ k . Si | SUB | = k , el algoritmo ha encontrado un subgráfico completo inducido, por lo que S k = SUB ∪ S k . Sin embargo, si | SUB |
El procedimiento de implementación de RAND-ESU es bastante sencillo y es una de las principales ventajas de FANMOD . Se puede cambiar el algoritmo ESU para explorar solo una parte de las hojas del árbol ESU aplicando un valor de probabilidad 0 ≤ p d ≤ 1 para cada nivel del árbol ESU y obligar a ESU a atravesar cada nodo 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 posibilidades de visitar cada hoja del árbol ESU sean las mismas, lo que da como resultado un muestreo imparcial de los subgráficos 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 árbol ESU; por lo tanto, este método garantiza un muestreo imparcial de los subgráficos de la red. No obstante, la determinación del valor de p d para 1 ≤ d ≤ k es otro tema que debe ser determinado manualmente por un experto para obtener resultados precisos de las concentraciones del sub-gráfico. [8] Si bien no existe una prescripción lúcida para este asunto, el 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 subgráficos inducidos que apoyan el método de muestreo insesgado. Aunque el algoritmo principal de la ESU y, por lo tanto, la herramienta FANMOD es conocida por descubrir subgráficos inducidos, existe una modificación trivial en la ESU que permite encontrar también subgráficos no inducidos. El pseudocódigo de ESU (FANMOD) se muestra a continuación:
Enumeración de ESU (FANMOD) |
---|
EnumerateSubgraphs (G, k) Entrada: Un gráfico G = (V, E) y un número entero 1 ≤ k ≤ | V | . Salida: Todos los tamaño- k subgraphs en G . para cada vértice v ∈ V hacer VExtensión ← {u ∈ N ({v}) | u> v } llamar a ExtendSubgraph ({v}, VExtension, v) fin de |
ExtendSubgraph (VSubgraph, VExtension, v) if | VSubgraph | = K entonces la salida G [VSubgraph] y retorno mientras que VExtension ≠ ∅ hace Eliminar un vértice w elegido arbitrariamente de VExtension VExtension ′ ← VExtension ∪ {u ∈ N excl (w, VSubgraph) | u> v } llamar a ExtendSubgraph (VSubgraph ∪ {w}, VExtension ′, v) regreso |
NeMoFinder
Chen y col. [30] introdujo un nuevo algoritmo de descubrimiento de NM llamado NeMoFinder , que adapta la idea en SPIN [31] para extraer árboles frecuentes y luego los expande en gráficos no isomorfos. [8] NeMoFinder utiliza árboles de tamaño n frecuentes para dividir la red de entrada en una colección de gráficos de tamaño n , y luego encuentra subgráficos de tamaño n frecuentes mediante la expansión de árboles frecuentes borde a borde hasta obtener un tamaño completo n gráfico 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 Chen et al. Afirman que NeMoFinder es aplicable para detectar NM relativamente grandes, por ejemplo, para encontrar NM de hasta tamaño 12 en toda la red de 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 gráficos de tamaño n , finalmente, realizar operaciones de unión de subgráficos para encontrar subgráficos frecuentes de tamaño n. [30] En el primer paso, el algoritmo detecta todos los árboles de tamaño n no isomórficos y las asignaciones de un árbol a la red. En el segundo paso, los rangos de estas asignaciones se emplean para dividir la red en gráficos de tamaño n. Hasta este paso, no hay distinción entre NeMoFinder y un método de enumeración exacto. Sin embargo, todavía queda una gran parte de los gráficos de tamaño n no isomórficos. NeMoFinder explota una heurística para enumerar gráficos sin tamaño de árbol n mediante la información obtenida de los pasos anteriores. La principal ventaja del algoritmo está en el tercer paso, que genera subgráficos candidatos a partir de subgráficos enumerados anteriormente. Esta generación de nuevos sub-gráficos de tamaño n se realiza uniendo cada sub-gráfico anterior con sub-gráficos derivados de sí mismo llamados sub-gráficos primos . Estos nuevos sub-gráficos contienen un borde adicional en comparación con los sub-gráficos anteriores. Sin embargo, existen algunos problemas al generar nuevos sub-gráficos: no existe un método claro para derivar primos de un gráfico, unir un sub-gráfico con sus primos conduce a la redundancia al generar un sub-gráfico particular más de una vez, y la determinación de primos es realizado por una representación canónica de la matriz de adyacencia que no se cierra en la operación de unión. NeMoFinder es un algoritmo de búsqueda de motivos de red eficiente para motivos de hasta el tamaño 12 solo para redes de interacción proteína-proteína, que se presentan como gráficos no dirigidos. Y no es capaz de trabajar en redes dirigidas que son tan importantes en el campo de las redes complejas y biológicas. El pseudocódigo de NeMoFinder se muestra a continuación:
NeMoFinder |
---|
Aporte: G - red PPI; N - Número de redes aleatorias; K - Tamaño máximo del motivo de la red; F - umbral de frecuencia; S - umbral de unicidad; Producción: U - Conjunto de motivos de red repetidos y únicos; D ← ∅ ; para el tamaño de motivo k de 3 a K do T ← FindRepeatedTrees (k) ; GD k ← GraphPartition (G, T) D ← D ∪ T ; D ′ ← T ; i ← k ; mientras que D ′ ≠ ∅ y yo ≤ k × (k - 1) / 2 hacen D ′ ← FindRepeatedGraphs (k, i, D ′) ; D ← D ∪ D ′ ; i ← i + 1 ; terminar mientras final para para el contador i de 1 a N hacer G rand ← RandomizedNetworkGeneration () ; por cada g ∈ D hacer GetRandFrequency (g, G rand ) ; final para final para U ← ∅ ; por cada g ∈ D hacer s ← GetUniqunessValue (g) ; si s ≥ S entonces U ← U ∪ {g }; terminara si final para return U ; |
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 subgráfico determinado, llamado gráfico de consulta , se determina de forma exhaustiva mediante la búsqueda de todas las asignaciones posibles del gráfico de consulta a la red más grande. Se afirma [33] que un método centrado en motivos en comparación con los métodos centrados en la red tiene algunas características beneficiosas. En primer lugar, evita la mayor complejidad de la enumeración de subgráficos. Además, al utilizar mapeo en lugar de enumerar, permite una mejora en la prueba de isomorfismo. Para mejorar el rendimiento del algoritmo, dado que es un algoritmo de enumeración exacta ineficiente, los autores introdujeron un método rápido que se denomina condiciones de ruptura de simetría . Durante las pruebas sencillas de isomorfismo de sub-gráfico, un sub-gráfico se puede mapear al mismo sub-gráfico del gráfico de consulta varias veces. En el algoritmo de Grochow-Kellis (GK) se usa 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, por medio de un método de bifurcación y vinculación, el algoritmo intenta encontrar todas las asignaciones posibles desde el gráfico de consulta a la red que cumpla con las condiciones asociadas de ruptura de simetría. En la figura se muestra un ejemplo del uso de condiciones de ruptura de simetría en el algoritmo GK.
Como se mencionó anteriormente, la técnica de ruptura de simetría es un mecanismo simple que evita perder tiempo buscando un subgráfico más de una vez debido a sus simetrías. [33] [34] Tenga en cuenta que, para calcular las condiciones que rompen la simetría, es necesario encontrar todos los automorfismos de un gráfico de consulta determinado. Aunque no existe un algoritmo eficiente (o de tiempo polinomial) para el problema del automorfismo de grafos, este problema se puede abordar de manera eficiente en la práctica con las herramientas de McKay. [28] [29] Como se afirma, el uso de condiciones de ruptura de simetría en la detección de NM permite ahorrar una gran cantidad de tiempo de ejecución. Además, 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 aparición de un gráfico de consulta dado en una gran red compleja y la explotación de las condiciones de ruptura de simetría mejora el rendimiento del algoritmo. Además, el algoritmo GK es uno de los algoritmos conocidos que no tiene limitación para el tamaño del motivo en la implementación y potencialmente puede encontrar motivos de cualquier tamaño.
Enfoque de codificación de colores
La mayoría de los algoritmos en el campo del descubrimiento de NM se utilizan para encontrar subgráficos inducidos de una red. En 2008, Noga Alon et al. [35] también introdujo un enfoque para encontrar subgráficos no inducidos. Su técnica funciona en redes no dirigidas como las de PPI. Además, cuenta los árboles no inducidos y los subgráficos de ancho de árbol delimitado. Este método se aplica para subgráficos de tamaño 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:
- Código 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.
- Contando. Aplique una rutina de programación dinámica para contar el número 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]
- Repita los dos pasos anteriores O (e k ) veces y sumar el número de ocurrencias de T para obtener una estimación del número de sus apariciones en G .
Dado que las redes PPI disponibles están lejos de ser completas y libres de errores, este enfoque es adecuado para el descubrimiento de NM para tales redes. Como el algoritmo de Grochow-Kellis y este son los más populares para los subgráficos no inducidos, vale la pena mencionar que el algoritmo introducido por Alon et al. consume menos tiempo que el algoritmo de Grochow-Kellis. [35]
MODA
Omidi y col. [36] introdujo un nuevo algoritmo para la detección de motivos llamado MODA que es aplicable para el descubrimiento de NM inducidos y no inducidos en redes no dirigidas. Se basa en el enfoque centrado en motivos discutido en la sección del algoritmo de Grochow-Kellis. Es muy importante distinguir los algoritmos centrados en motivos como el algoritmo 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 subgráficos posibles de un tamaño determinado) con tamaños más grandes. A medida que el número de posibles subgráficos no isomórficos aumenta exponencialmente con el tamaño del subgráfico, para motivos de gran tamaño (incluso mayores de 10), los algoritmos centrados en la red, aquellos que buscan todos los subgráficos posibles, se enfrentan a un problema. Aunque los algoritmos centrados en motivos también tienen problemas para descubrir todos los posibles subgráficos de gran tamaño, su capacidad para encontrar un pequeño número 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 NM de un tamaño dado de manera sistemática y similar a FPF que evita enumerar sub-gráficos poco prometedores; MODA toma en consideración las consultas potenciales (o subgráficos candidatos) que resultarían en subgráficos frecuentes. A pesar del hecho de que MODA se parece a FPF en el uso de una estructura similar a un árbol, el árbol de expansión es aplicable simplemente para calcular el concepto de frecuencia F 1 . Como discutiremos a continuación, la ventaja de este algoritmo es que no realiza la prueba de isomorfismo de sub-gráfico para gráficos de consulta que no son de árbol . Además, utiliza un método de muestreo para acelerar el tiempo de ejecución del algoritmo.
Aquí está la idea principal: con un criterio simple, se puede generalizar un mapeo de un gráfico de tamaño k en la red a supergráficos del mismo tamaño. Por ejemplo, suponga que hay un mapeo f (G) del gráfico G con k nodos en la red y tenemos un gráfico del mismo tamaño G ′ con un borde más & langu, v⟩ ; f G será mapa G ' en la red, si hay un borde ⟨f G (u), f G (v)⟩ en la red. Como resultado, podemos explotar el conjunto de mapeo de un gráfico para determinar las frecuencias de sus supergráficos del mismo orden simplemente en el tiempo O (1) sin realizar pruebas de isomorfismo de sub-gráfico. El algoritmo comienza ingeniosamente con gráficos de consulta mínimamente conectados de tamaño k y encuentra sus asignaciones en la red a través del isomorfismo de sub-gráficos. Después de eso, con la conservación del tamaño del gráfico, expande los gráficos de consulta previamente considerados borde por borde y calcula la frecuencia de estos gráficos expandidos como se mencionó anteriormente. El proceso de expansión continúa hasta llegar a un gráfico completo K k (totalmente conectado con k (k-1) ⁄ 2 borde).
Como se discutió anteriormente, el algoritmo comienza calculando las frecuencias de los subárboles en la red y luego expande los subárboles borde a 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 los subgráficos de tamaño 4. T k organiza el proceso en ejecución y proporciona gráficos de consulta de manera jerárquica. Estrictamente hablando, el árbol de expansión T k es simplemente un gráfico acíclico dirigido o DAG, con su número raíz k que indica el tamaño del gráfico existente en el árbol de expansión y cada uno de sus otros nodos contiene la matriz de adyacencia de un gráfico de consulta de tamaño k distinto . Los nodos en el primer nivel de T k son árboles distintos de tamaño k y, al atravesar T k en profundidad, los gráficos de consulta se expanden con un borde en cada nivel. Un gráfico de consulta en un nodo es un subgráfico del gráfico de consulta en el hijo de un nodo con una diferencia de borde. La ruta más larga en T k consta de (k 2 -3k + 4) / 2 bordes y es la ruta desde la raíz hasta el nodo hoja que contiene el gráfico completo. La generación de árboles de expansión se puede realizar mediante una rutina simple que se explica en. [36]
MODA atraviesa T k y cuando extrae árboles de consulta del primer nivel de T k , calcula sus conjuntos de mapeo y guarda estos mapeos para el siguiente paso. Para consultas que no son de árbol de T k , el algoritmo extrae las asignaciones asociadas con el nodo padre en T k y determina cuál de estas asignaciones puede soportar los gráficos de consulta actuales. El proceso continuará hasta que el algoritmo obtenga el gráfico de consulta completo. Las asignaciones del árbol de consultas se extraen mediante el algoritmo de Grochow-Kellis. Para calcular la frecuencia de los gráficos de consulta que no son de árbol, el algoritmo emplea una rutina simple que toma O (1) pasos. Además, MODA explota un método de muestreo donde el muestreo de cada nodo en la red es linealmente proporcional al grado del nodo, la distribución de probabilidad es exactamente similar al conocido modelo de apego preferencial de Barabási-Albert en el campo de redes complejas. [37] Este enfoque genera aproximaciones; sin embargo, los resultados son casi estables en diferentes ejecuciones ya que los subgráficos se agregan alrededor de nodos altamente conectados. [38] El pseudocódigo de MODA se muestra a continuación:
MODA |
---|
Entrada: G : gráfico de entrada, k : tamaño del sub-gráfico, Δ : valor de umbral Resultado: Lista de subgrafos frecuentes: Lista de todos los subgrafos frecuentes de tamaño k Nota: F G : conjunto de asignaciones de G en el gráfico de entrada G buscar T k hacer G ′ = Get-Next-BFS (T k ) // G ′ es un gráfico de consulta si | E (G ′) | = (k - 1) llamar al módulo de mapeo (G ′, G) demás llamar al módulo de enumeración (G ′, G, T k ) terminara si guardar F 2 si | F G | > Δ entonces agregue G ′ en la lista de subgrafos frecuentes terminara si Hasta | E (G ') | = (k - 1) / 2 volver Lista de subgrafos frecuentes |
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 subgráficos de tamaño k en los que participó un nodo en particular, luego eliminan el nodo y luego repiten este proceso para los nodos restantes. [39]
Para contar los subgráficos de tamaño k que incluyen un nodo en particular, se construyen implícitamente árboles con una profundidad máxima de k, enraizados en este nodo y basados en la relación de vecindad. Los hijos de cada nodo incluyen nodos adyacentes entrantes y salientes. Para descender del árbol, se elige un niño en cada nivel con la restricción de que un niño en particular puede ser incluido solo si no ha sido incluido en ningún nivel superior. Después de haber descendido al nivel más bajo posible, el árbol se vuelve a ascender y el proceso se repite con la estipulación de que los nodos visitados en las 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 niños son similares a las condiciones que utilizan los algoritmos GK y ESU para evitar el recuento excesivo de los subgráficos.
El protocolo para extraer subgráficos utiliza las composiciones de un número entero. Para la extracción de subgráficos de tamaño k , se deben considerar todas las posibles composiciones del número entero k-1 . Las composiciones de k-1 consisten en todas las formas posibles de expresar k-1 como una suma de números enteros positivos. Las sumas en las que difiere el orden de los sumandos 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 los sub-gráficos basados en la composición, k i nodos se seleccionan del i -ésimo nivel del árbol para ser nodos de los sub-gráficos ( i = 2,3,…, m ). Los k-1 nodos seleccionados junto con el nodo en la raíz definen un sub-gráfico dentro de la red. Después de descubrir un sub-gráfico involucrado como coincidencia en la red de destino, para poder evaluar el tamaño de cada clase de acuerdo con la red de destino, 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:
Enumeración de Kavosh |
---|
Enumerate_Vertex (G, u, S, resto, i) Entrada: G : Gráfico de entrada u : Vértice raíz S : selección ( S = {S 0 , S 1 , ..., S k-1 } es una matriz del conjunto de todos los S i ) Resto : número de vértices restantes para ser seleccionado i : profundidad actual del árbol. Resultado: todos los subgráficos de tamaño k del gráfico G con raíz en u . si Resto = 0 entonces de regreso más ValList ← Validar (G, S i-1 , u) n i ← Min (| ValList |, el resto) para k i = 1 a n i do C ← Initial_Comb (ValList, k i ) ( Hacer la primera selección de combinación de vértices de acuerdo) repetir S i ← C Enumerate_Vertex (G, u, S, Resto-k i , i + 1) Next_Comb (ValList, k i ) (Hacer la siguiente selección de combinación de vértices de acuerdo) hasta C = NILL final para cada v ∈ ValList do Visited [v] ← falso final para final si |
Validar (G, padres, u) Entrada: G : gráfico de entrada, Padres : vértices seleccionados de la última capa, u : vértice raíz. ValList ← NILL |
Recientemente, se desarrolló un complemento Cytoscape llamado CytoKavosh [40] para este software. Está disponible a través de la página web de Cytoscape [1] .
G-Tries
En 2010, Pedro Ribeiro y Fernando Silva propusieron una estructura de datos novedosa para almacenar una colección de subgráficos, llamada g-trie . [41] Esta estructura de datos, que es conceptualmente similar a un árbol de prefijos, almacena sub-gráficos de acuerdo con sus estructuras y encuentra ocurrencias de cada uno de estos sub-gráficos en un gráfico más grande. Uno de los aspectos notables de esta estructura de datos es que, al llegar al descubrimiento del motivo de la red, es necesario evaluar los subgráficos de la red principal. Por lo tanto, no es necesario encontrar los que están en una red aleatoria que no están en la red principal. Esta puede ser una de las partes que requieren mucho tiempo en los algoritmos en los que se derivan todos los subgráficos en redes aleatorias.
Un g-trie es un árbol de múltiples vías que puede almacenar una colección de gráficos. Cada nodo de árbol contiene información sobre un único vértice de gráfico y sus bordes correspondientes a los nodos ancestros. Un camino desde la raíz hasta una hoja corresponde a un solo gráfico. Los descendientes de un nodo g-trie comparten un subgráfico común. La construcción de un g-trie está bien descrita 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 subgráficos 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 . Aprovechar las subestructuras comunes en el sentido de que en un momento dado hay una coincidencia isomórfica parcial para varios subgráficos candidatos diferentes.
Entre los algoritmos mencionados, G-Tries es el más rápido. Pero el uso excesivo de memoria es el inconveniente de este algoritmo, que podría limitar el tamaño de los motivos detectables por una computadora personal con memoria promedio.
ParaMODA 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 la figura a continuación muestran los resultados de ejecutar los algoritmos mencionados en diferentes redes estándar. Estos resultados se toman de las fuentes correspondientes, [36] [39] [41] por lo que deben tratarse individualmente.
La red | Tamaño | Red original del censo | Censo promedio en redes aleatorias | ||||
---|---|---|---|---|---|---|---|
FANMOD | G K | G-Trie | FANMOD | G K | G-Trie | ||
Delfines | 5 | 0,07 | 0,03 | 0,01 | 0,13 | 0,04 | 0,01 |
6 | 0,48 | 0,28 | 0,04 | 1,14 | 0,35 | 0,07 | |
7 | 3,02 | 3,44 | 0,23 | 8,34 | 3,55 | 0,46 | |
8 | 19.44 | 73,16 | 1,69 | 67,94 | 37,31 | 4.03 | |
9 | 100,86 | 2984.22 | 6,98 | 493,98 | 366,79 | 24,84 | |
Circuito | 6 | 0,49 | 0,41 | 0,03 | 0,55 | 0,24 | 0,03 |
7 | 3,28 | 3,73 | 0,22 | 3,53 | 1,34 | 0,17 | |
8 | 17,78 | 48,00 | 1,52 | 21.42 | 7,91 | 1.06 | |
Social | 3 | 0,31 | 0,11 | 0,02 | 0,35 | 0,11 | 0,02 |
4 | 7.78 | 1,37 | 0,56 | 13.27 | 1,86 | 0,57 | |
5 | 208.30 | 31,85 | 14,88 | 531,65 | 62,66 | 22.11 | |
Levadura | 3 | 0,47 | 0,33 | 0,02 | 0,57 | 0,35 | 0,02 |
4 | 10.07 | 2,04 | 0,36 | 12,90 | 2,25 | 0,41 | |
5 | 268.51 | 34,10 | 12,73 | 400,13 | 47.16 | 14,98 | |
Energía | 3 | 0,51 | 1,46 | 0,00 | 0,91 | 1,37 | 0,01 |
4 | 1,38 | 4.34 | 0,02 | 3,01 | 4,40 | 0,03 | |
5 | 4,68 | 16,95 | 0,10 | 12.38 | 17.54 | 0,14 | |
6 | 20,36 | 95,58 | 0,55 | 67,65 | 92,74 | 0,88 | |
7 | 101.04 | 765,91 | 3.36 | 408.15 | 630,65 | 5.17 |
Tamaño → | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|
Redes ↓ | Algoritmos ↓ | ||||||||
E. coli | Kavosh | 0,30 | 1,84 | 14,91 | 141,98 | 1374.0 | 13173.7 | 121110.3 | 1120560.1 |
FANMOD | 0,81 | 2,53 | 15,71 | 132,24 | 1205,9 | 9256.6 | - | - | |
Mavisto | 13532 | - | - | - | - | - | - | - | |
Mfinder | 31.0 | 297 | 23671 | - | - | - | - | - | |
Electrónico | Kavosh | 0,08 | 0,36 | 8.02 | 11.39 | 77,22 | 422,6 | 2823,7 | 18037,5 |
FANMOD | 0,53 | 1.06 | 4.34 | 24,24 | 160 | 967,99 | - | - | |
Mavisto | 210,0 | 1727 | - | - | - | - | - | - | |
Mfinder | 7 | 14 | 109,8 | 2020.2 | - | - | - | - | |
Social | Kavosh | 0,04 | 0,23 | 1,63 | 10.48 | 69,43 | 415,66 | 2594.19 | 14611.23 |
FANMOD | 0,46 | 0,84 | 3,07 | 17,63 | 117,43 | 845,93 | - | - | |
Mavisto | 393 | 1492 | - | - | - | - | - | - | |
Mfinder | 12 | 49 | 798 | 181077 | - | - | - | - |
Clasificación de algoritmos
Como se ve en la tabla, los algoritmos de descubrimiento de motivos se pueden dividir en dos categorías generales: los que se basan en el conteo exacto y los que usan muestreo estadístico y estimaciones en su lugar. Debido a que el segundo grupo no cuenta todas las apariciones de un subgrafo en la red principal, los algoritmos que pertenecen a este grupo son más rápidos, pero pueden producir resultados sesgados y poco realistas.
En el siguiente nivel, los algoritmos de recuento exactos se pueden clasificar en métodos centrados en la red y centrados en subgrafos. Los algoritmos de la primera clase buscan en la red dada todos los subgrafos de un tamaño dado, mientras que los algoritmos que pertenecen a la segunda clase primero generan diferentes gráficos no isomórficos posibles del tamaño dado, y luego exploran la red para cada subgrafo generado por separado. Cada enfoque tiene sus ventajas y desventajas que se comentan anteriormente.
Por otro lado, los métodos de estimación pueden utilizar el enfoque de codificación por colores como se describió anteriormente. Otros enfoques utilizados en esta categoría generalmente omiten algunos subgrafos durante la enumeración (por ejemplo, como en FANMOD) y basan su estimación en los subgrafos enumerados.
Además, la tabla indica si un algoritmo se puede utilizar para redes dirigidas o no dirigidas, así como subgrafos inducidos o no inducidos. Para obtener más información, consulte los enlaces web o las direcciones de laboratorio proporcionados.
Método de conteo | Base | Nombre | Dirigido / No dirigido | Inducido / No inducido |
---|---|---|---|---|
Exacto | Centrado en la red | mfinder | Ambas cosas | Inducido |
ESU (FANMOD) | Ambas cosas | Inducido | ||
Kavosh (utilizado en CytoKavosh ) | Ambas cosas | Inducido | ||
G-Tries | Ambas cosas | Inducido | ||
PGD | No dirigido | Inducido | ||
Centrado en subgrafos | FPF (Mavisto) | Ambas cosas | Inducido | |
NeMoFinder | No dirigido | Inducido | ||
Grochow – Kellis | Ambas cosas | Ambas cosas | ||
MODA | Ambas cosas | Ambas cosas | ||
Estimación / muestreo | Enfoque de codificación de colores | N. Alon y col. Algoritmo de | No dirigido | No inducido |
Otros enfoques | mfinder | Ambas cosas | Inducido | |
ESU (FANMOD) | Ambas cosas | Inducido |
Algoritmo | Nombre del laboratorio / departamento | Departamento / Escuela | Instituto | Habla a | |
---|---|---|---|---|---|
mfinder | Grupo de Uri Alon | Departamento de Biología Celular Molecular | Instituto de Ciencias Weizmann | Rehovot, Israel, Wolfson, Rm. 607 | urialon en weizmann.ac.il |
FPF (Mavisto) | ---- | ---- | Leibniz-Institut für Pflanzengenetik und Kulturpflanzenforschung (IPK) | Corrensstraße 3, D-06466 Stadt Seeland, OT Gatersleben, Alemania | schreibe en ipk-gatersleben.de |
ESU (FANMOD) | Lehrstuhl Theoretische Informatik I | Institut für Informatik | Friedrich-Schiller-Universität Jena | Ernst-Abbe-Platz 2, D-07743 Jena, Alemania | sebastian.wernicke en gmail.com |
NeMoFinder | ---- | Escuela de Computación | Universidad Nacional de Singapur | Singapur 119077 | chenjin en comp.nus.edu.sg |
Grochow – Kellis | Grupo de teoría CS y grupo de sistemas complejos | Ciencias de la Computación | Universidad de Colorado, Boulder | 1111 Engineering Dr. ECOT 717, 430 UCB Boulder, CO 80309-0430 EE. UU. | jgrochow en colorado.edu |
N. Alon y col. Algoritmo de | Departamento de Matemáticas Puras | Facultad de Ciencias Matemáticas | Universidad de tel aviv | Tel Aviv 69978, Israel | nogaa en post.tau.ac.il |
MODA | Laboratorio de Biología de Sistemas y Bioinformática (LBB) | Instituto de Bioquímica y Biofísica (IBB) | Universidad de Teherán | Enghelab Square, Enghelab Ave, Teherán, Irán | amasoudin en ibb.ut.ac.ir |
Kavosh (utilizado en CytoKavosh ) | Laboratorio de Biología de Sistemas y Bioinformática (LBB) | Instituto de Bioquímica y Biofísica (IBB) | Universidad de Teherán | Enghelab Square, Enghelab Ave, Teherán, Irán | amasoudin en ibb.ut.ac.ir |
G-Tries | Centro de Investigación en Sistemas Informáticos Avanzados | Ciencias de la Computación | Universidad de Porto | Rua Campo Alegre 1021/1055, Oporto, Portugal | pribeiro en dcc.fc.up.pt |
PGD | Laboratorio de descubrimiento y aprendizaje en red | Departamento de Ciencias de la Computación | Universidad de Purdue | Universidad Purdue, 305 N University St, West Lafayette, IN 47907 | [email protected] |
Motivos bien establecidos y sus funciones.
Se ha dedicado mucho trabajo experimental a comprender los motivos de la 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 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 la 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 la 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 componen casi toda la red. La hipótesis principal es que el motivo de la red se seleccionó de forma independiente mediante 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 velocidad a la que cambian los genes, [ 45] [46] [47] Además, los experimentos sobre la dinámica generada por motivos de red en células vivas indican que tienen funciones dinámicas características. Esto sugiere que el motivo de la red sirve como bloques de construcción en las redes reguladoras de genes que son beneficiosas para el organismo.
Las funciones asociadas con motivos de red comunes en redes de transcripción fueron exploradas y demostradas por varios proyectos de investigación tanto teórica como experimentalmente. A continuación se muestran algunos de los motivos de red más comunes y su función asociada.
Autorregulación negativa (NAR)
Uno de los motivos de red más simples y abundantes en E. coli es la autorregulación negativa en la que un factor de transcripción (TF) reprime su propia transcripción. Se demostró que este motivo realiza dos funciones importantes. La primera función es la aceleración de la respuesta. Se demostró que la NAR acelera la respuesta a las señales tanto teóricamente [48] como experimentalmente. Esto se mostró por primera vez en una red de transcripción sintética [49] y más tarde en el contexto natural en el sistema de reparación del ADN SOS de E. coli. [50] La segunda función es una mayor estabilidad de la concentración del producto génico autorregulado contra el ruido estocástico, reduciendo así las variaciones en los niveles de proteínas 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. Frente al motivo NAR, este motivo ralentiza el tiempo de respuesta en comparación con la regulación simple. [54] En el caso de un PAR fuerte, el motivo puede conducir a una distribución bimodal de los niveles de proteína en las poblaciones celulares. [55]
Bucles de alimentación hacia adelante (FFL)
Este motivo se encuentra comúnmente en muchos sistemas y organismos genéticos. 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, TF B también está regulado por TF A. Dado que cada una de las interacciones reguladoras puede ser positiva o negativa, existen posiblemente ocho tipos de motivos FFL. [56] Dos de esos ocho tipos: el FFL de tipo 1 coherente (C1-FFL) (donde todas las interacciones son positivas) y el FFL de tipo 1 incoherente (I1-FFL) (A activa C y también activa B que reprime C) son encontrado 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 de los circuitos, también se debe considerar la forma en que el promotor C integra las señales de A y B. En la mayoría de los casos, el FFL es una puerta Y (se requieren A y B para la activación de C) o una puerta O (A o B son suficientes para la activación de C) pero también son posibles otras funciones de entrada.
Coherente tipo 1 FFL (C1-FFL)
Se demostró que el C1-FFL con una puerta 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 arabinosa de E. coli . Esto significa que este motivo puede proporcionar una 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 surge en el caso de una puerta 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, un sistema basado en la dinámica de regulación de avance con diferentes en cambio, se favoreció la topología. [60]
Incoherente tipo 1 FFL (I1-FFL)
El I1-FFL es un generador de impulsos y un acelerador de respuesta. Las dos vías de señal del I1-FFL actúan en direcciones opuestas donde una vía activa Z y la otra la reprime. Cuando la represión se 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 un gen de factor de transcripción. [61] Se asignó una función adicional al motivo de la red I1-FFL: se demostró tanto teórica como experimentalmente que I1-FFL puede generar una función de entrada no monótona tanto en sistemas sintéticos [62] como nativos. [63] Por último, las unidades de expresión que incorporan un control de avance incoherente del producto génico proporcionan una 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 la retroalimentación mostró una mejor adaptación que la retroalimentación negativa, y los circuitos basados en la interferencia del ARN fueron los más resistentes a la variación en las cantidades de la plantilla de ADN. [64]
FFL de salida múltiple
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 genes. Esto se demostró experimentalmente en el sistema de flagelos de E. coli . [sesenta y cinco]
Módulos de entrada única (SIM)
Este motivo ocurre cuando un solo regulador regula un conjunto de genes sin regulación adicional. Esto es útil cuando los genes están desempeñando cooperativamente una función específica y, por lo tanto, siempre deben activarse de manera sincronizada. Al ajustar la fuerza de las interacciones, puede crear un programa de expresión temporal de los genes que regula. [66]
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. Hay intentos de proporcionar definiciones ortogonales para motivos canónicos en redes biológicas y algoritmos para enumerarlos, especialmente SIM, MIM y Bi-Fan (2x2 MIM). [67]
Regulones densos superpuestos (DOR)
Este motivo ocurre en el caso de que varios reguladores controlen combinatoriamente un conjunto de genes con diversas combinaciones reguladoras. Este motivo se encontró en E. coli en varios sistemas como la utilización del carbono, el crecimiento anaeróbico, la respuesta al estrés y otros. [17] [22] Para comprender mejor la función de este motivo, es necesario obtener más información sobre la forma en que los genes integran las múltiples entradas. Kaplan y col. [68] ha mapeado las funciones de entrada de los genes de utilización del azúcar en E. coli , mostrando diversas formas.
Motivos de actividad
Una generalización interesante de los motivos de la red, los motivos de actividad son patrones de ocurrencia excesiva que se pueden encontrar cuando los nodos y bordes en la red se anotan con características cuantitativas. Por ejemplo, cuando los bordes en las vías metabólicas se anotan con la magnitud o el momento de la expresión del gen correspondiente, algunos patrones están ocurriendo en exceso dada la estructura de red subyacente. [69]
Motivos socio-técnicos
Braha [70] analizó la frecuencia de los subgrafos de tres y cuatro nodos en diversas redes complejas sociotécnicas . Los resultados muestran una fuerte correlación entre una propiedad dinámica de los subgrafos de la red — la sincronizabilidad — y la frecuencia y el significado de estos subgrafos en las redes sociotécnicas . Se sugirió que la propiedad de sincronizabilidad de los subgrafos de las redes también podría explicar los principios organizativos en otras redes de procesamiento de información, incluidas las redes biológicas y sociales .
Motivos socioeconómicos
Se han encontrado motivos en redes de compra-venta. [71] Por ejemplo, si dos personas compran al mismo vendedor y una de ellas también compra a un segundo vendedor, existe una alta probabilidad de que el segundo comprador compre al segundo vendedor.
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, [72] la estructura del motivo no necesariamente determina la función. La estructura de la red ciertamente no siempre indica función; esta es una idea que ha existido durante algún tiempo, por ejemplo, vea el operón Sin. [73]
La mayoría de los análisis de la función del motivo se llevan a cabo mirando el motivo que opera de forma aislada. Investigaciones recientes [74] proporcionan una 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 solo a partir de la estructura local; el documento citado también revisa las críticas y explicaciones alternativas para la datos observados. Se estudia un análisis del impacto de un solo módulo de motivo en la dinámica global de una red. [75] 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, cuestionando así si Las frecuencias de ocurrencias son evidencia razonable de que las estructuras de los motivos se seleccionan por su contribución funcional al funcionamiento de las redes. [76] [77]
Mientras que el estudio de motivos se aplicó principalmente a redes complejas estáticas, la investigación de redes complejas temporales [78] sugirió una reinterpretación significativa de motivos de redes e introdujo el concepto de motivos de redes temporales . Braha y Bar-Yam [79] estudiaron la dinámica de la estructura de motivos locales en redes temporales / dependientes del tiempo, y encontraron patrones recurrentes que podrían proporcionar evidencia empírica de los ciclos de interacción social. En contra de la perspectiva de motivos estables y perfiles de motivos en redes complejas, demostraron que para las redes temporales la estructura local es dependiente del tiempo y podría evolucionar con el tiempo. Braha y Bar-Yam sugirieron además que el análisis de la estructura local temporal podría proporcionar información importante sobre la dinámica de la tarea y la funcionalidad a nivel del sistema.
Ver también
- Clique (teoría de grafos)
- Modelo grafico
Referencias
- ^ Masoudi-Nejad A, Schreiber F, Razaghi MK Z (2012). "Bloques de construcción de redes biológicas: una revisión de los algoritmos de descubrimiento de motivos de red principales". Biología de sistemas IET . 6 (5): 164–74. doi : 10.1049 / iet-syb.2011.0011 . PMID 23101871 .
- ^ Diestel R (2005). "Teoría de Grafos (Textos de Posgrado en Matemáticas)". 173 . Nueva York: Springer-Verlag Heidelberg. Cite journal requiere
|journal=
( ayuda ) - ^ a b c 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". Ciencia . 298 (5594): 824–827. Código Bibliográfico : 2002Sci ... 298..824M . CiteSeerX 10.1.1.225.8750 . doi : 10.1126 / science.298.5594.824 . PMID 12399590 .
- ^ 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 . Código Bibliográfico : 2002RvMP ... 74 ... 47A . CiteSeerX 10.1.1.242.4753 . doi : 10.1103 / RevModPhys.74.47 . S2CID 60545 .
- ^ a b 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" . Ciencia . 303 (5663): 1538-1542. Código Bibliográfico : 2004Sci ... 303.1538M . doi : 10.1126 / science.1089167 . PMID 15001784 . S2CID 14760882 .
- ^ a b Schwöbbermeyer, H (2008). "Motivos de red". En Junker BH, Schreiber F (ed.). Análisis de redes biológicas . Hoboken, Nueva Jersey: John Wiley & Sons. págs. 85-108.
- ^ Bornholdt, S; Schuster, HG (2003). "Manual de gráficos y redes: del genoma a Internet". Manual de gráficos y redes: del genoma a Internet . pag. 417. bibcode : 2003hgnf.book ..... B .
- ^ a b c Ciriello G, Guerra C (2008). "Una revisión sobre modelos y algoritmos para el descubrimiento de motivos en redes de interacción proteína-proteína" . Sesiones informativas sobre genómica funcional y proteómica . 7 (2): 147-156. doi : 10.1093 / bfgp / eln015 . PMID 18443014 .
- ^ a b c d e f Kashtan N, Itzkovitz S, Milo R, Alon U (2004). "Algoritmo de muestreo eficiente para estimar concentraciones de sub-gráfico y detectar motivos de red" . Bioinformática . 20 (11): 1746-1758. doi : 10.1093 / bioinformatics / bth163 . PMID 15001476 .
- ^ a b c d e f 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 .
- ^ Picard F, Daudin JJ, Schbath S , Robin S (2005). "Evaluación de la excepcionalidad de los motivos de la red". J. Comp. Bio . 15 (1): 1–20. CiteSeerX 10.1.1.475.4300 . doi : 10.1089 / cmb.2007.0137 . PMID 18257674 .
- ^ a b c Schreiber F, Schwöbbermeyer H (2005). "Conceptos de frecuencia y detección de patrones para el análisis de motivos en redes". Transacciones en Biología de Sistemas Computacionales III . Apuntes de conferencias en Ciencias de la Computación. 3737 . págs. 89-104. CiteSeerX 10.1.1.73.1130 . doi : 10.1007 / 11599128_7 . ISBN 978-3-540-30883-6. Falta o vacío
|title=
( ayuda ) - ^ Holanda, PW y Leinhardt, S. (1974). El análisis estadístico de la estructura local en redes sociales. Documento de trabajo núm. 44, Oficina Nacional de Investigaciones Económicas.
- ^ Hollandi, P. y Leinhardt, S. (1975). El análisis estadístico de lo local. Estructura en Redes Sociales. Metodología sociológica, David Heise, ed. San Francisco: Josey-Bass.
- ^ Holanda, PW y Leinhardt, S. (1976). Estructura local en redes sociales. Metodología sociológica, 7, 1-45.
- ^ Holanda, PW y Leinhardt, S. (1977). Un método para detectar estructura en datos sociométricos. En las redes sociales (págs. 411-432). Prensa académica.
- ^ a b c 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 .
- ^ Eichenberger P, Fujita M, Jensen ST y col. (Octubre de 2004). "El programa de transcripción de genes para un solo tipo de célula diferenciadora durante la esporulación en Bacillus subtilis " . PLOS Biología . 2 (10): e328. doi : 10.1371 / journal.pbio.0020328 . PMC 517825 . PMID 15383836 .
- ^ 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". Ciencia . 298 (5594): 824–7. Código Bibliográfico : 2002Sci ... 298..824M . CiteSeerX 10.1.1.225.8750 . doi : 10.1126 / science.298.5594.824 . PMID 12399590 .
- ^ Lee TI, Rinaldi NJ, Robert F y col. (Octubre de 2002). "Redes reguladoras de la transcripción en Saccharomyces cerevisiae". Ciencia . 298 (5594): 799–804. Código Bibliográfico : 2002Sci ... 298..799L . doi : 10.1126 / science.1075090 . PMID 12399584 . S2CID 4841222 .
- ^ Odom DT, Zizlsperger N, Gordon DB y col. (Febrero de 2004). "Control de la expresión de genes de hígado y páncreas por factores de transcripción de HNF" . Ciencia . 303 (5662): 1378–81. Código Bibliográfico : 2004Sci ... 303.1378O . doi : 10.1126 / science.1089769 . PMC 3012624 . PMID 14988562 .
- ^ a b Boyer LA, Lee TI, Cole MF y col. (Septiembre de 2005). "Circuito regulador transcripcional básico en células madre embrionarias humanas" . Celular . 122 (6): 947–56. doi : 10.1016 / j.cell.2005.08.020 . PMC 3006442 . PMID 16153702 .
- ^ Iranfar N, Fuller D, Loomis WF (febrero de 2006). "Regulación transcripcional de genes de post-agregación en Dictyostelium por un bucle de alimentación hacia adelante que involucra a GBF y LagC" . Dev. Biol . 290 (2): 460–9. doi : 10.1016 / j.ydbio.2005.11.035 . PMID 16386729 .
- ^ 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" . Ciencia . 309 (5737): 1078–83. Código Bibliográfico : 2005Sci ... 309.1078M . doi : 10.1126 / science.1108876 . PMC 3032439 . PMID 16099987 .
- ^ Ptacek J, Devgan G, Michaud G y col. (Diciembre de 2005). "Análisis global de la fosforilación de proteínas en levadura" (PDF) . Nature (manuscrito enviado). 438 (7068): 679–84. Código Bibliográfico : 2005Natur.438..679P . doi : 10.1038 / nature04187 . PMID 16319894 . S2CID 4332381 .
- ^ "Acc-Motif: detección acelerada de motivos" .
- ^ 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 .
- ^ a b c McKay BD (1981). "Isomorfismo gráfico práctico". Congressus Numerantium . 30 : 45–87. arXiv : 1301.1493 . Código bibliográfico : 2013arXiv1301.1493M .
- ^ a b c McKay BD (1998). "Generación exhaustiva libre de isomorfos". Revista de algoritmos . 26 (2): 306–324. doi : 10.1006 / jagm.1997.0898 .
- ^ a b Chen J, Hsu W, Li Lee M y col. (2006). NeMoFinder: disección de interacciones proteína-proteína en todo el genoma con motivos de red de mesoescala . la 12ª conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos. Filadelfia, Pensilvania, Estados Unidos. págs. 106-115.
- ^ Huan J, Wang W, Prins J y col. (2004). SPIN: extracción de subgráficos máximos frecuentes de bases de datos de gráficos . la décima conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos. págs. 581–586.
- ^ Uetz P, Giot L, Cagney G y col. (2000). "Un análisis completo de las interacciones proteína-proteína en Saccharomyces cerevisiae". Naturaleza . 403 (6770): 623–627. Código Bibliográfico : 2000Natur.403..623U . doi : 10.1038 / 35001009 . PMID 10688190 . S2CID 4352495 .
- ^ a b c d Grochow JA, Kellis M (2007). Descubrimiento de motivos de red mediante enumeración de subgráficos y ruptura de simetría (PDF) . RECOMBAR. págs. 92-106. doi : 10.1007 / 978-3-540-71681-5_7 .
- ^ a b Grochow JA (2006). Sobre la estructura y evolución de las redes de interacción de proteínas (PDF) . Tesis M. Eng., Instituto de Tecnología de Massachusetts, Departamento de Ingeniería Eléctrica y Ciencias de la Computación.
- ^ a b c Alon N; Dao P; Hajirasouliha I; Hormozdiari F; Sahinalp SC (2008). "Recuento de motivos de red biomolecular y descubrimiento por codificación de colores" . Bioinformática . 24 (13): i241 – i249. doi : 10.1093 / bioinformatics / btn163 . PMC 2718641 . PMID 18586721 .
- ^ a b c d e 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 .
- ^ Barabasi AL, Albert R (1999). "Aparición del escalado en redes aleatorias". Ciencia . 286 (5439): 509–512. arXiv : cond-mat / 9910332 . Código Bibliográfico : 1999Sci ... 286..509B . doi : 10.1126 / science.286.5439.509 . PMID 10521342 . S2CID 524106 .
- ^ 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 . Código bibliográfico : 2004PNAS..10117940V . doi : 10.1073 / pnas.0406024101 . PMC 539752 . PMID 15598746 .
- ^ a b c d 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" . BMC Bioinformática . 10 (318): 318. doi : 10.1186 / 1471-2105-10-318 . PMC 2765973 . PMID 19799800 .
- ^ 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. Código Bibliográfico : 2012PLoSO ... 743287M . doi : 10.1371 / journal.pone.0043287 . PMC 3430699 . PMID 22952659 .
- ^ a b c d Ribeiro P, Silva F (2010). G-Tries: una estructura de datos eficiente para descubrir motivos de red . 25º Simposio de Computación Aplicada de ACM - Pista de Bioinformática. Sierre, Suiza. págs. 1559-1566.
- ^ Mbadiwe, Somadina; Kim, Wooyoung (noviembre de 2017). "ParaMODA: mejorar la búsqueda de patrón de subgrafo centrado en motivos en redes PPI" . 2017 Conferencia Internacional IEEE sobre Bioinformática y Biomedicina (BIBM) : 1723-1730. doi : 10.1109 / BIBM.2017.8217920 . ISBN 978-1-5090-3050-7. S2CID 5806529 .
- ^ "NemoMap: algoritmo de descubrimiento de motivo de red centrado en motivos mejorado" . Revista de Avances en Ciencia, Tecnología y Sistemas de Ingeniería . 2018 . Consultado el 11 de septiembre de 2020 .
- ^ Patra, Sabyasachi; Mohapatra, Anjali (2020). "Revisión de herramientas y algoritmos para el descubrimiento de motivos de red en redes biológicas" . Biología de sistemas IET . 14 (4): 171–189. doi : 10.1049 / iet-syb.2020.0004 . ISSN 1751-8849 . PMID 32737276 .
- ^ a b Babu MM, Luscombe NM, Aravind L, Gerstein M, Teichmann SA (junio de 2004). "Estructura y evolución de redes reguladoras transcripcionales". Opinión actual en biología estructural . 14 (3): 283–91. CiteSeerX 10.1.1.471.9692 . doi : 10.1016 / j.sbi.2004.05.004 . PMID 15193307 .
- ^ a b 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 .
- ^ Dekel E, Alon U (julio de 2005). "Optimidad y sintonía evolutiva del nivel de expresión de una proteína". Naturaleza . 436 (7050): 588–92. Código Bib : 2005Natur.436..588D . doi : 10.1038 / nature03842 . PMID 16049495 . S2CID 2528841 .
- ^ Zabet NR (septiembre de 2011). "Retroalimentación negativa y límites físicos de los genes". Revista de Biología Teórica . 284 (1): 82–91. arXiv : 1408.1869 . CiteSeerX 10.1.1.759.5418 . doi : 10.1016 / j.jtbi.2011.06.021 . PMID 21723295 . S2CID 14274912 .
- ^ 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 .
- ^ Camas FM, Blázquez J, Poyatos JF (agosto de 2006). "Control de respuesta autógeno y no autógeno en una red genética" . Proc. Natl. Acad. Sci. USA . 103 (34): 12718–23. Código bibliográfico : 2006PNAS..10312718C . doi : 10.1073 / pnas.0602119103 . PMC 1568915 . PMID 16908855 .
- ^ Becskei A, Serrano L (junio de 2000). "Ingeniería de estabilidad en redes de genes por autorregulación". Naturaleza . 405 (6786): 590–3. Código Bibliográfico : 2000Natur.405..590B . doi : 10.1038 / 35014651 . PMID 10850721 . S2CID 4407358 .
- ^ Dublanche Y, Michalodimitrakis K, Kümmerer N, Foglierini M, Serrano L (2006). "Ruido en bucles de retroalimentación negativa de transcripción: simulación y análisis experimental" . Mol. Syst. Biol . 2 (1): 41. doi : 10.1038 / msb4100081 . PMC 1681513 . PMID 16883354 .
- ^ Shimoga V, White J, Li Y, Sontag E, Bleris L (2013). "Autorregulación negativa transgénica de mamífero sintético" . Mol. Syst. Biol . 9 : 670. doi : 10.1038 / msb.2013.27 . PMC 3964311 . PMID 23736683 .
- ^ 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 .
- ^ Becskei A, Séraphin B, Serrano L (mayo de 2001). "Retroalimentación positiva en redes de genes eucariotas: diferenciación celular por conversión de respuesta graduada a binaria" . EMBO J . 20 (10): 2528–35. doi : 10.1093 / emboj / 20.10.2528 . PMC 125456 . PMID 11350942 .
- ^ a b c Mangan S, Alon U (octubre de 2003). "Estructura y función del motivo de la red de bucle de alimentación" . Proc. Natl. Acad. Sci. USA . 100 (21): 11980–5. Código Bibliográfico : 2003PNAS..10011980M . doi : 10.1073 / pnas.2133841100 . PMC 218699 . PMID 14530388 .
- ^ 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" . Ácidos nucleicos Res . 32 (22): 6643–9. doi : 10.1093 / nar / gkh1009 . PMC 545451 . PMID 15604458 .
- ^ Mangan S, Zaslaver A, Alon U (noviembre de 2003). "El bucle de retroalimentación coherente sirve como un elemento de retardo sensible al signo 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 .
- ^ Kalir S, Mangan S, Alon U (2005). "Un bucle de avance 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 .
- ^ Xiong, Kun; Lancaster, Alex K .; Siegal, Mark L .; Masel, Joanna (3 de junio de 2019). "La regulación feed-forward evoluciona de forma adaptativa a través de la dinámica en lugar de la topología cuando hay ruido intrínseco" . Comunicaciones de la naturaleza . 10 (1): 2418. Bibcode : 2019NatCo..10.2418X . doi : 10.1038 / s41467-019-10388-6 . PMC 6546794 . PMID 31160574 .
- ^ Mangan S, Itzkovitz S, Zaslaver A, Alon U (marzo de 2006). "El bucle de avance 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 .
- ^ 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 feed-forward incoherentes" . Syst Synth Biol . 1 (3): 119–28. doi : 10.1007 / s11693-007-9008-6 . PMC 2398716 . PMID 19003446 .
- ^ Kaplan S, Bren A, Dekel E, Alon U (2008). "El bucle de avance 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 .
- ^ a b Bleris L, Xie Z, Glass D, Adadey A, Sontag E, Benenson Y (2011). "Los circuitos de alimentación sintéticos incoherentes muestran una 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 .
- ^ Kalir S, McClure J, Pabbaraju K, et al. (Junio de 2001). "Ordenar genes en una vía de flagelos mediante el análisis de la cinética de expresión de bacterias vivas". Ciencia . 292 (5524): 2080–3. doi : 10.1126 / science.1058758 . PMID 11408658 . S2CID 14396458 .
- ^ 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 .
- ^ Konagurthu AS, Lesk AM (2008). "Módulos de entrada única y múltiple en redes regulatorias". Las proteínas . 73 (2): 320–324. doi : 10.1002 / prot.22053 . PMID 18433061 . S2CID 35715566 .
- ^ Kaplan S, Bren A, Zaslaver A, Dekel E, Alon U (marzo de 2008). "Diversas funciones de entrada bidimensionales controlan los genes del azúcar bacteriano" . Mol. Celular . 29 (6): 786–92. doi : 10.1016 / j.molcel.2008.01.021 . PMC 2366073 . PMID 18374652 .
- ^ Chechik G, Oh E, Rando O, Weissman J, Regev A, Koller D (noviembre de 2008). "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 .
- ↑ Braha, D. (2020). Patrones de vínculos en redes de resolución de problemas y sus propiedades dinámicas . Informes científicos, 10 (1), 1-22.
- ^ X. Zhang, S. Shao, HE Stanley, S. Havlin (2014). "Motivos dinámicos en redes socioeconómicas". Europhys. Lett . 108 (5): 58001. Bibcode : 2014EL .... 10858001Z . doi : 10.1209 / 0295-5075 / 108/58001 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ 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 .
- ^ Voigt CA, Wolf DM, Arkin AP (marzo de 2005). "El operón sin Bacillus subtilis : un motivo de red evolutiva" . Genética . 169 (3): 1187–202. doi : 10.1534 / genetics.104.031955 . PMC 1449569 . PMID 15466432 .
- ^ Knabe JF, Nehaniv CL, Schilstra MJ (2008). "¿Los motivos reflejan la función evolucionada? —No evolución convergente de topologías de subgraph de red reguladora genética". BioSystems . 94 (1–2): 68–74. doi : 10.1016 / j.biosystems.2008.05.012 . PMID 18611431 .
- ^ Taylor D, Restrepo JG (2011). "Conectividad de red durante fusiones y crecimiento: Optimización de la incorporación de un módulo". Revisión E física . 83 (6): 66112. arXiv : 1102.4876 . Código bibliográfico : 2011PhRvE..83f6112T . doi : 10.1103 / PhysRevE.83.066112 . PMID 21797446 . S2CID 415932 .
- ^ Konagurthu, Arun S .; Lesk, Arthur M. (23 de abril de 2008). "Módulos de entrada única y múltiple en redes regulatorias". Proteínas: estructura, función y bioinformática . 73 (2): 320–324. doi : 10.1002 / prot.22053 . PMID 18433061 . S2CID 35715566 .
- ^ 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 .
- ^ Braha, D. y Bar ‐ Yam, Y. (2006). De la centralidad a la fama temporal: centralidad dinámica en redes complejas . Complejidad, 12 (2), 59-63.
- ^ Braha D., Bar-Yam Y. (2009) Redes complejas dependientes del tiempo: centralidad dinámica, motivos dinámicos y ciclos de interacciones sociales . En: Gross T., Sayama H. (eds) Adaptive Networks. Comprensión de sistemas complejos. Springer, Berlín, Heidelberg
enlaces externos
- Una herramienta de software que puede detectar motivos de red.
- MOTIVOS DE RED biofísica-wiki
- FANMOD: una herramienta para la detección rápida de motivos de red
- MAVisto: herramienta de visualización y análisis de motivos de red
- NeMoFinder
- Grochow – Kellis
- MODA
- Kavosh
- CytoKavosh
- G-Tries
- herramienta de detección acc-MOTIF