ARS Avanzado: Complejo clique

Complejo clique
Wikipedia



El complejo clique de un grafo. Los grupos de tamaño uno se muestran como pequeños discos rojos; grupos de tamaño 2 se muestran como segmentos de líneas negras; grupos de tamaño 3 se muestran como triángulos de color azul claro; y grupos de tamaño 4 o tetraedros se muestran de color azul oscuro.


Los complejos cliques, complejos de bandera, e hipergrafos conformales son objetos matemáticos que están relacionados estrechamente con la teoría de grafos y la topología geométrica que cada uno describen camarillas (subgrafos completos) de un grafo no dirigido.

El complejo clique  X(G) de un grafo no dirigido G es un complejo simplicial abstracto (es decir, una familia de conjuntos finitos cerrados bajo la operación de toma de subconjuntos), formada por los conjuntos de vértices en las camarillas de G. Cualquier subconjunto de una camarilla es en sí misma una camarilla, por lo que esta familia de conjuntos cumple con el requisito de un complejo simplicial abstracto en el que cada subconjunto de un conjunto en la familia también debe estar en la familia. El complejo clique también puede ser visto como un espacio topológico en el que cada camarilla de k vértices está representado por un simplex de dimensión k - 1. El 1-esqueleto de X (G) (también conocido como el grafo subyacente del complejo) es un grafo no dirigido con un vértice por cada conjunto de 1 elemento en la familia y un enlace para cada conjunto de 2 elementos en la familia; es isomorfo a G. [1]

Los complejos clique son también conocidos como complejos de Whitney. Una triangulación Whitney o triangulación limpio de un colector (manifold) de dos dimensiones es una incrustación de un grafo de G en el colector de tal manera que cada cara es un triángulo y cada triángulo es una cara. Si un grafo G tiene una triangulación Whitney, debe formar un complejo de célula que es isomorfo al complejo Whitney de G. En este caso, el complejo (visto como un espacio topológico) es homeomorfo al colector subyacente. Un grafo G tiene un complejo clique de 2 colectores (manifold), y puede ser incrustado como una triangulación Whitney, si y sólo si G es localmente cíclico; esto significa que, para cada vértice v en el grafo, el subgrafo inducido formado por los vecinos de v forma un solo ciclo. [2]

Complejo de independencia

El complejo independencia I (G) de un grafo G se forma de la misma manera como el complejo camarilla de los conjuntos independientes de G. Es el complejo camarilla del grafo complemento de G.

Complejo de bandera

En un complejo simplicial abstracto, un conjunto S de vértices que no es en sí parte del complejo, pero de tal manera que cada par de vértices en S pertenece a algún simplex en el complejo, que se llama un simplex vacío. Mikhail Gromov define la condición de no-Δ ser la condición de que un complejo no tienen simplices vacías. Un complejo bandera es un complejo simplicial abstracto que no tiene simplices vacías; es decir, que es la condición no-Δ un complejo de Gromov satisfacer. Cualquier complejo bandera es el complejo de su camarilla 1-esqueleto. Por lo tanto, los complejos y los complejos bandera camarilla son esencialmente la misma cosa. Sin embargo, en muchos casos puede ser conveniente definir un complejo bandera directamente de algunos datos distintos de un grafo, en lugar de indirectamente como el complejo clique de un grafo derivado de los datos. [3]

Conforme de hipergrafo

El grafo primario G (H) de un hipergrafo es el grafo en el mismo conjunto de vértices que tiene como sus enlaces los pares de vértices que aparecen juntos en la misma hiperenlace. Un hipergrafo se dice que es conforme si cada camarilla máxima de su grafo es un hipernelace primitivo, o equivalentemente, si cada camarilla de su grafo primario está contenida en alguna hiperenlace. [4] Si se requiere el hipergrafo sea descendente cerrado (por lo que contiene todos los hiperenlaces que se contienen en algunos hiperenlaces) entonces el hipergrafo es conforme con precisión cuando se trata de un complejo de bandera. Esto se relaciona el lenguaje de hipergrafos al lenguaje del complejo simplicial.

Ejemplos y aplicaciones

La subdivisión baricéntrica de cualquier complejo C de células es un complejo de bandera que tiene un vértice por célula de C. Una colección de vértices de la subdivisión baricéntrica formar un simplex si y sólo si la colección correspondiente de células de C forman una bandera (una cadena en el inclusión de pedido de las células). [3] En particular, la subdivisión barycentric de un complejo celular en un 2-colector da lugar a una triangulación Whitney del colector.

El complejo orden de un conjunto parcialmente ordenado se compone de las cadenas (subconjuntos totalmente ordenado) del orden parcial. Si cada par de algún subconjunto es en sí mismo ordenó, entonces todo el subconjunto es una cadena, por lo que los complejos satisface la condición de la orden de no-Δ. Se puede interpretar como el complejo camarilla del grafo de la comparabilidad de la orden parcial. [3]

El complejo de empardamiento (matching complex) de un grafo consiste en los conjuntos de enlaces ninguno de cuyos pares comparten un punto final; de nuevo, esta familia de conjuntos satisface la condición de no-Δ. Puede ser visto como el complejo camarilla del grafo complemento del grafo de líneas del grafo dado. Cuando el complejo juego se denomina sin ninguna representación grafo concreta como contexto, significa el complejo juego de un grafo completo. El complejo juego de un grafo bipartito completo K_m,n es conocida como un complejo de tablero de ajedrez. Es el clique de del grafo complemento del grafo de una torre, [5] y cada uno de sus simplices representa una colocación de torres en un tablero de m × n de ajedrez de tal manera que no hay dos de las torres atacan entre sí. Cuando m = n ± 1, las formas complejas de tablero de ajedrez una pseudo-colector.

El complejo Vietoris-Rips de un conjunto de puntos en un espacio métrico es un caso especial de un complejo clique, formado a partir del grafo de disco unidad de los puntos; Sin embargo, cada complejo clique X(G) puede ser interpretada como el complejo Vietoris-Rips de la métrica camino más corto en el grafo subyacente G.

Hodkinson y Otto (2003) describen una aplicación de hipergrafos conformales en la lógica de las estructuras relacionales. En ese contexto, el grafo de Gaifman de una estructura relacional es el mismo que el grafo subyacente del hipergrafo que representa la estructura, y una estructura esté vigilado si corresponde a un hipergrafo conformal.

Gromov mostró que un complejo cúbico (es decir, una familia de hipercubos intersección cara a cara) forma un CAT (0) espacio si y sólo si el complejo está simplemente conectado y el enlace de cada vértice forma un complejo bandera. Una reunión compleja cúbica estas condiciones a veces se llama una cubicación o un espacio con paredes. [1] [6]

Referencias

1. Bandelt, H.-J.; Chepoi, V. (2008), "Metric graph theory and geometry: a survey", in Goodman, J. E.; Pach, J.; Pollack, R., Surveys on Discrete and Computational Geometry: Twenty Years Later (PDF), Contemporary Mathematics, 453, Providence, RI: AMS, pp. 49–86.
2. Berge, C. (1989), Hypergraphs: Combinatorics of Finite Sets, North-Holland, ISBN 0-444-87489-5.
3. Chatterji, I.; Niblo, G. (2005), "From wall spaces to CAT(0) cube complexes", International Journal of Algebra and Computation, 15 (5–6): 875–885, arXiv:math.GT/0309036, doi:10.1142/S0218196705002669.
4. Davis, M. W. (2002), "Nonpositive curvature and reflection groups", in Daverman, R. J.; Sher, R. B., Handbook of Geometric Topology, Elsevier, pp. 373–422.
5. Dong, X.; Wachs, M. L. (2002), "Combinatorial Laplacian of the matching complex", Electronic Journal of Combinatorics, 9: R17.
6. Hartsfeld, N.; Ringel, Gerhard (1991), "Clean triangulations", Combinatorica, 11 (2): 145–155, doi:10.1007/BF01206358.
7. Hodkinson, I.; Otto, M. (2003), "Finite conformal hypergraph covers and Gaifman cliques in finite structures", The Bulletin of Symbolic Logic, 9 (3): 387–405, doi:10.2178/bsl/1058448678.
8. Larrión, F.; Neumann-Lara, V.; Pizaña, M. A. (2002), "Whitney triangulations, local girth and iterated clique graphs", Discrete Mathematics, 258: 123–135, doi:10.1016/S0012-365X(02)00266-2.
9. Malnič, A.; Mohar, B. (1992), "Generating locally cyclic triangulations of surfaces", Journal of Combinatorial Theory, Series B, 56 (2): 147–164, doi:10.1016/0095-8956(92)90015-P.

Cliques en redes de proteínas

Complejos de proteínas y módulos funcionales en las redes moleculares
Victor Spirin y Leonid A. Mirny *
PNAS

Editado por Lawrence A. Shepp, Rutgers, la Universidad Estatal de Nueva Jersey en New Brunswick, Piscataway, NJ, y aprobada en 5 de agosto de 2003 (recibido por opinión 22 abril de 2003)

Resumen

Las proteínas, ácidos nucleicos, y pequeñas moléculas forman una densa red de interacciones moleculares en una célula. Las moléculas son nodos de esta red, y las interacciones entre ellos se encuentran los enlaces. La arquitectura de las redes moleculares puede revelar importantes principios de organización y función celular, de manera similar a la forma en que la estructura de proteínas nos dice acerca de la función y la organización de una proteína. Análisis computacional de las redes moleculares ha ocupado principalmente de grado nodal [Wagner, A. y Fell, D. A. (2001) Proc. R. Soc. London Ser. B 268, 1803-1810; Jeong, H., Tombor, B., Albert, R., Oltvai, ZN y Barabási, AL (2000), Nature 407, 651-654] o correlación grado [Maslov, S. & Sneppen, K. (2002), Science 296 , 910-913], y por lo tanto se centró en las propiedades individuales / de dos cuerpos de estas redes. Aquí, mediante el análisis de la estructura multicuerpo de la red de interacciones proteína-proteína, descubrimos módulos moleculares que están conectados densamente dentro de sí mismos pero escasamente conectados con el resto de la red. La comparación con los datos experimentales y la anotación funcional de genes mostró dos tipos de módulos: (i) complejos de proteínas (maquinaria de empalme, factores de transcripción, etc.) y (ii) unidades funcionales dinámicos (cascadas de señalización, la regulación del ciclo celular, etc.). módulos descubiertos son estadísticamente muy significativa, como se desprende de la comparación con los grafos aleatorios, y son robustos al ruido en los datos. Nuestros resultados proporcionan un fuerte apoyo al principio de la modularidad de red introducida por Hartwell et al. [Hartwell, L. H., Hopfield, J. J., Leibler, S. y Murray, A. W. (1999) Nature 402, C47-C52], lo que sugiere que los módulos que se encuentran constituyen los "bloques de construcción" de las redes moleculares.

Los experimentos a gran escala y la integración de los datos publicados (1) han proporcionado mapas de varias redes biológicas tales como las redes metabólicas (2, 3), proteína-proteína (4, 5) y la proteína-DNA (6, 7), etc. Aunque incompleta y, tal vez, inexacta (8-11), estos mapas se convirtió en un punto focal de una búsqueda de los principios generales que rigen la organización de las redes moleculares (12-16). características estadísticas importantes de tales redes incluyen la distribución de ley de potencia (P (k) ~ k-γ) (por ejemplo,. refs 16 y 17) o una distribución similar del grado del nodo k (es decir, el número de enlaces de un nodo) ; la propiedad del mundo pequeño (11, 13, 16) (es decir, un alto coeficiente de agrupación y un pequeño camino más corto entre cada par de nodos); anticorrelación en el nodo de grado de nodos conectados (15) (es decir, altamente interactuar nodos tienden a ser conectado a los de bajo interactuar); y otras propiedades.

Estas propiedades hacen evidentes cuando cientos o miles de moléculas y sus interacciones se estudian juntos. motivos recientemente descubiertos (7, 18) que constan de tres a cuatro nodos constituyen el otro extremo del espectro. características a gran escala son generalmente atribuidos a los procesos evolutivos masivos que dan forma a la red (6, 14), mientras que muchos motivos pequeña escala representan la contribución y los bucles de alimentación directa en la regulación celular (18, 19). Sin embargo, los procesos biológicos más importantes, tales como la transducción de señales, regulación de la celda de destino, la transcripción y la traducción implican más de cuatro, pero mucho menos de cientos de proteínas. La mayoría de los procesos pertinentes de las redes biológicas corresponden a la mesoescala (5-25 genes / proteínas). propiedades meso-escala de las redes biológicas han sido en su mayoría difícil de alcanzar debido a las dificultades de cálculo en la enumeración de las subredes de tamaño medio (por ejemplo, una red de 1.000 nodos contiene 1 × 1023 posibles conjuntos de 10 nodos).

A continuación, presentamos una exploración a fondo de las redes moleculares en el nivel meso-escala. Nos centramos en las interacciones multicuerpo y realizaron búsquedas de conjuntos de proteínas que tienen muchas más interacciones entre ellos que con el resto de la red (clusters). Hemos desarrollado varios algoritmos para encontrar este tipo de agrupaciones en una red arbitraria. Se analizó una red de levadura de interacciones proteína-proteína (20) y encontramos> 50 grupos de proteínas conocidas y previamente no. Se analizaron anotación funcional de estos grupos y se encontró que la mayoría de grupos identificados corresponden a cualquiera de los dos tipos de módulos celulares: los complejos de proteínas o módulos funcionales (ver Discusión). complejos de proteínas son grupos de proteínas que interactúan entre sí al mismo tiempo y lugar, formando una sola máquina multimolecular. Los ejemplos de complejos de proteínas identificadas incluyen varios complejos grandes factor de transcripción, el complejo promotor de la anafase, el empalme de ARN y la maquinaria de poliadenilación, complejos de exportación de proteínas y de transporte, etc. módulos funcionales, en contraste, se componen de proteínas que participan en un proceso celular particular, mientras que la unión entre sí en un momento diferente y colocar (diferentes condiciones o fases del ciclo celular, en diferentes compartimentos celulares, etc). Ejemplos de módulos funcionales identificados incluyen el módulo de CDK / ciclina responsable de la progresión del ciclo celular, la ruta de respuesta de la levadura de feromonas, cascadas de señalización MAP, etc. Los complejos y módulos descubiertos tienen una alta significación estadística y anotación funcional consistente (si está disponible), y combinar muy bien al obtenido experimentalmente complejos de proteínas (21, 22). Es importante destacar que, al basarse en interacciones multicuerpo, nuestro método es robusto a las interacciones falsos positivos presentes en la red.

La red de interacciones de proteínas (20) se representa como un grafo no dirigido con proteínas como nodos y las interacciones proteína como enlaces no dirigidos. La idea clave de nuestro análisis fue identificar subgrafos altamente conectados (clusters) que tienen más interacciones dentro de sí mismos y menos con el resto del grafo. Un subgrafo totalmente conectado, o camarilla, que no es una parte de cualquier otra clique es un ejemplo de un grupo de este tipo. En general, no requieren agrupaciones para ser totalmente conectada; En su lugar, la densidad de las conexiones de la agrupación se midió por el parámetro Q = 2 m / (n (n - 1)), donde n es el número de proteínas en el clúster y m es el número de interacciones entre ellos. Hemos desarrollado algoritmos que pueden identificar grupos de suficientemente alta Q en un grafo arbitrario. Tenga en cuenta que, a pesar de alguna similitud, el problema de subgraphs densas no es idéntico al problema de los objetos de agrupación en un espacio métrico y no puede ser resuelto por técnicas de agrupamiento tradicionales.

Métodos

Identificación de los conjuntos muy conectados. Nuestro primer enfoque fue identificar todos los subgrafos totalmente conectados (camarillas o cliques) por enumeración completa. Debido a que el grafo es muy escasa, esto se podría hacer rápidamente. De hecho, para encontrar grupos de tamaño n se necesita para enumerar solamente los grupos de tamaño n - 1 (para más detalles, véase el texto de apoyo, que se publica como información de apoyo en el sitio web de PNAS, www.pnas.org). Empezamos con n = 3 y continuó hasta no se encontraron más camarillas en el grafo. La camarilla más grande encontrado contiene 14 nodos.

El segundo método utiliza una técnica de agrupación que trabaja sobre puntos no incluidos en un espacio métrico. Un potente algoritmo de este tipo es la agrupación superparamagnético (SPC) (23). En pocas palabras, este enfoque asigna un "giro" a cada nodo en el grafo. Cada giro puede ser en varias (más de dos) estados. Giros pertenecientes a los nodos conectados interactuar y tener la energía más baja cuando se encuentran en el mismo estado. El sistema (conocido como el modelo de Potts) está sujeta a equilibrio a temperatura distinta de cero, haciendo giros fluctúan. El concepto detrás de este método es que los giros que pertenecen a un grupo altamente conectado fluctúan de una manera correlacionada. Mediante la detección de giros correlacionados, el algoritmo puede identificar nodos que pertenecen a un área altamente conectado del grafo. Domany y compañeros de trabajo presentó un sistema de este tipo para los puntos de la agrupación en un espacio arbitrario (23) y con éxito se aplican a una variedad de problemas de agrupamiento (24, 25). Aquí, hemos aplicado SPC para identificar grupos en un grafo.

En el tercer método, formulamos el problema de encontrar conjuntos altamente conectadas de nodos como un problema de optimización: encontrar un conjunto de n nodos que maximiza la función Q (m, n) = 2 m / (n (n - 1)), donde m es el número de interacciones entre n nodos. El parámetro (0 ≤ Q ≤ 1) caracteriza la densidad de un clúster. Para un conjunto de nodos totalmente conectado, Q = 1, y para un conjunto no conectadas entre sí, Q = 0. El Monte Carlo procedimiento de optimización (MC) comienza con un conjunto conexo de n nodos seleccionados al azar en el grafo y los ingresos por "movimiento" nodos seleccionados a lo largo de los enlaces del grafo para maximizar se mueve Q. se aceptan de acuerdo a los criterios de Metropolis. También hemos desarrollado un algoritmo que minimiza la suma de las distancias más cortas entre los nodos seleccionados. Ambos algoritmos son muy eficientes y convergen rápido para identificar un grupo muy conectado. Ambos algoritmos requieren que el tamaño del conglomerado buscado como un parámetro de entrada. Aunque la tasa de convergencia de MC depende de la temperatura efectiva, el algoritmo converge rápidamente a una amplia gama de temperaturas (Fig. 6, que se publica como información de apoyo en el sitio web de PNAS). Comparación de algoritmos MC y SPC han mostrado un mejor comportamiento de MC para los clústeres que comparten nodos comunes y para los grafos de alta densidad, mientras SPC tiene una ventaja identificar los grupos que tienen muy pocas conexiones con el resto del grafo (Fig. 7, la cual es publicada como información de apoyo en el sitio web de PNAS).

Los grupos encontrados se sometieron después a una limpieza más profunda, la fusión y la selección de acuerdo con los criterios de significación estadística (véase el texto de apoyo para más detalles).

Significancia estadística. Para estimar la significación estadística de un clúster que tiene n las proteínas y las interacciones m entre ellos, uno tendría que calcular el número esperado de estas agrupaciones E (n, m) en un grafo al azar comparable (es decir, grafo al azar que satisfaga ciertas restricciones, es decir, , fijar nodo de grado). Debido a la explosión combinatoria de posibles subgrafos, el cálculo directo de E (n, m) en los grafos aleatorios es computacionalmente inviable para n> 4. Hemos desarrollado dos procedimientos estadísticos que estimar el valor esperado E (n, m) y la probabilidad P (n, m ) para evaluar la significación estadística de los grupos identificados. Aunque Q es una buena medida de la densidad de las interacciones en un manojo, a su significación estadística depende mucho del tamaño de clúster, n. Un grupo de tres proteínas con Q = 1 es probable que se encuentre en un grafo de azar, mientras que un conjunto de 10 proteínas con Q = 0.26 puede ser muy poco probable en el mismo grafo aleatorio. Introdujimos dos medidas de significación estadística que se basan en la probabilidad de encontrar un clúster en un grafo de azar comparable (15, 18, 26, 27). Para calcular la significación estadística, se generó por primera vez 1.000 grafos aleatorios en los que se conserva el número de interacciones de cada proteína. A continuación, para cada grupo de n proteínas y m interacciones, se calculó el valor P como la probabilidad de tener más de m conexiones entre las mismas proteínas en los grafos correspondientes al azar. Un valor de p calculado de esta manera da la probabilidad de que tengan m (o más) las interacciones entre un grupo particular de proteínas, dado el número de interacciones que cada una de estas proteínas tiene. Aunque esta probabilidad puede ser muy pequeño, el número de posibles grupos Ωn comparables de proteínas n es enorme. Para tener esto en cuenta que computa el valor E = E PΩn como el número esperado de n grupos de proteínas que tienen m (o más) las interacciones. El número de posibles grupos comparables se estima

donde N es el número total de nodos en los grafos y N (d> DC) es el número de nodos con mayor grado que la CC. Hemos establecido la CC sea el grado medio en el grupo de interés. De esta manera, el valor E tiene en cuenta tanto el número de proteínas en los grupos y el número de interacciones cada uno de ellos tiene.

Huelga decir que todos los valores de P y E son aproximados y su cálculo directo es prohibitivamente costoso computacionalmente. Por último, mediante la aplicación de los algoritmos de búsqueda de los grafos aleatorios, también estima que el valor Pevd como la probabilidad de encontrar cualquier conjunto de n nodos con m o más conexiones. Debido a que nuestros algoritmos buscan maximizar m, el valor Pevd obedece a la distribución de valor extremo Fisher-Tippett (EVD) Pevd (m) = exp (-exp (-α (m - u))). Parámetros alpha y se obtuvieron u de esta distribución por 1000 MC se ejecuta en cada uno de 1.000 grafos aleatorios, generados como se describe anteriormente. Hemos observado escalado lineal simple de α-1 = A1N + a2 y u = U1N + u2, que permite un fácil cálculo de Pevd para grupos de cualquier tamaño. Por lo tanto, mediante el establecimiento de Pevd <Pcutoff, se puede obtener Q de corte (n) para grupos de cualquier tamaño n, tal que un clúster con Q> Q (n) de corte se consideró estadísticamente significativa (ver Apoyo de texto y la Fig. 8 para detalles). Para nuestro análisis de los complejos y los módulos, se seleccionaron los grupos altamente significativas con E <0,1, P <1 × 10-4, y Pevd <1 × 10-4. Higo. 1B muestra la comparación de la cantidad de complejos que se encuentran de un tamaño dado y Q frente al número de complejos de este tamaño y Q esperado en un grafo aleatorio.


Fig. 1.
La significación estadística de los complejos y módulos. (A) Número de camarillas completos (Q = 1) en función del tamaño de la camarilla enumerado en la red de interacciones entre proteínas (rojo) y en los grafo reconectados al azar (azul, un promedio de> 1.000 grafos). El recuadro muestra la misma parcela en escala logarítmica normal. Tenga en cuenta el enriquecimiento espectacular en el número de camarillas en el grafo de la proteína-interacción. La mayoría de estas camarillas son partes de los complejos y los módulos más grandes. (B) Distribución de Q de clusters encontrados por el procedimiento de búsqueda de MC en los grafos reconectados al azar (barras azules). La línea azul muestra aproximación de esta distribución por el Fisher-Tippett distribución de valor extremo (EVD) con dos parámetros de ajuste. Las barras rojas muestran los complejos que se encuentran en la red original de las interacciones proteína. Los tamaños de los subgrafos son n = 8, 10, y 16. Nota que los complejos reales tienen muchas más interacciones que los complejos más estrechos que se encuentran en los grafos reconectados al azar.

Un método similar utilizado por Milo et al. (18) para identificar pequeños motivos de la red requiere la enumeración exacta de los motivos en los grafos aleatorios. Tal enumeración es computacionalmente imposible que los grupos y los módulos más grandes. Nuestro enfoque, en contraste, no implica tal enumeración y por lo tanto se puede ampliar a grupos de cualquier tamaño.

También usamos importancia muestreo MC para estimar E (n, m). Tomamos muestras de un conjunto de n proteínas en E azar y obtenido (m | n) de distribución. Para realizar un muestreo más eficiente, tomamos muestras de proteínas con la probabilidad proporcional a su grado, es decir, la probabilidad de escoger una proteína i: Pi = di / Σi = 1 ... N di. Se encontró | (n m) estimada mediante el uso de muestreo de importancia para ser lineal con log (m) y puede ser extrapolado a una mayor precisión m E. Este método se utilizó para estimar el número de camarillas en el grafo aleatorio (Fig. 1 A, azul).

Resultados

Para el estudio de la estructura a gran escala de la red de interacción de proteínas, lo primero que enumeramos todos los grupos de tamaño 3 y más grande. La escasez relativa del grafo (N = 3.992 nodos y M = 6.500 enlaces) permitió la enumeración exacta de las camarillas. Para la comparación, se construyeron 1.000 grafos aleatorios del mismo tamaño y grado de distribución (véase más adelante) y los utilizó para calcular el número esperado de camarillas. El grafo de las interacciones proteína es conocida por ser un grafo muy especial con una distribución de ley potencial de grados de los nodos. Para descartar la posibilidad de que una estructura de este tipo cliquish es un resultado de la arquitectura de ley de potencia, construimos nuestros grafos aleatorios usando el procedimiento de Maslov-Sneppen (15), que conserva el número de enlaces de cada nodo. En otras palabras, los grupos de proteínas obtenidos se controlan para el número de interacciones que cada proteína tiene. Higo. 1 A presenta estos resultados, demostrando un enriquecimiento abrumadora en camarillas de todos los tamaños en el grafo de la proteína en comparación con los grafos aleatorios. La comparación de los números observados y esperados de camarillas también muestra que la gran mayoría de camarillas (97% para n = 4, 99,8% para n = 5, etc.) de tamaño 4 y mayor son, de hecho, estadísticamente significativa. La alta densidad de las interacciones en las camarillas y su significación estadística muestran que estas camarillas no surgieron por casualidad, que señala en alguna función biológica que llevan. El enriquecimiento en el número de camarillas revela una modularidad esencial en la estructura de la red, lo que sugiere que muchas de estas interacciones de proteínas son responsables de la formación de complejos de proteínas y módulos funcionales. Para explorar más a fondo esta estructura modular de la red, se realizaron búsquedas en el grafo para los clústeres multiproteicos que no son camarillas (es decir, Q <1).

La construcción de algoritmos rápidos para determinar las propiedades estructurales de los grafos es un reto clásico en la matemática discreta y la informática teórica. Tales problemas son fáciles de estado e ilustran, pero a menudo son demostrablemente difícil en el sentido de ser NP-duro (problemas NP-duros son aquellos para los que no hay algoritmos conocidos pueden encontrar una solución en tiempo polinomial en el tamaño del problema, aunque hay algoritmos que pueden verificar una solución propuesta en ese momento). El problema de encontrar la mayor camarilla, o incluso de aproximar su tamaño, es NP-duro (28). En este caso, el objetivo fue encontrar camarillas que no esté totalmente conectados, un problema aún más difícil. Aunque los algoritmos estocásticos que desarrollamos no se puede garantizar para encontrar todas las soluciones, que son eficientes cuando se aplica a los grafos relativamente escasos, tales como una red de interacciones entre proteínas.

Se han utilizado dos métodos para estudiar más a fondo la modularidad de la red y encontrar grupos multiproteicos altamente conectados: la técnica de optimización MC y el algoritmo SPC como el desarrollado por Domany y compañeros de trabajo (23, 24). Estos métodos son capaces de encontrar grupos que están muy conectados, pero no necesariamente conectadas totalmente (Q <1). El uso de estas técnicas, se identificaron> 50 grupos de proteínas de tamaños de 4 a 35. grafos aleatorios comparables, por el contrario, contenida muy pocas, si alguna, estas agrupaciones. Higo. 1B presenta distribuciones de densidad de Q de los grupos del mismo tamaño que se encuentran en los grafos aleatorios (barras azules) y en la red de proteínas (barras rojas). Esta distribución de los grafos aleatorios puede encajar bien por el Fisher-Tippett (29) de distribución de valor extremo (EVD) (también conocida como la distribución de Gumbel) (Fig. 1B, línea azul), lo que nos permite estimar la significación estadística de la proteína clusters (ver Métodos). Sorprendentemente, las agrupaciones en la red de proteínas tienen muchas más interacciones que sus contrapartes en los grafos aleatorios: la probabilidad de encontrar grupos comparables en los grafos aleatorios es inferior a 1 × 10-4 (Pevd <1 × 10-4). Estos resultados demuestran que, además de numerosos camarillas, la red de proteínas contiene muchos cúmulos densos significativamente de las proteínas que interactúan. Higo. 2 muestra tres grupos altamente conectados y el fragmento de red que les rodea, que ilustra la dificultad de encontrar tales grupos. Estos grupos proporcionan una fuerte evidencia adicional que respalde la arquitectura modular de redes biológicas.


Fig. 2.
Fragmento de la red de proteínas. Los nodos y las interacciones en grupos descubiertos se muestran en negrita. Los nodos se colorean por categorías funcionales en MIPS (20): rojo, regulación de la transcripción; azul, el ciclo celular / control de la celda de destino; verde, el procesamiento del ARN; y el amarillo, el transporte de proteínas. Complejos se muestran en la SAGA / complejo TFIID (rojo), el promotor de la anafase complejo (azul), y el complejo Trapp (amarillo).

¿Cuál es el papel biológico de estas agrupaciones altamente conectados? Para responder a esta pregunta, se analizó la anotación funcional de los genes disponibles de Saccharomyces cerevisiae (20, 30). Hemos encontrado que los genes pertenecientes a un mismo módulo o complejo tienen una función biológica consistente, proporcionado por el centro de Munich Información de Secuencias de Proteínas (MIPS) tablas funcionales de anotación (www.mips.biochem.mpg.de) (20). Higo. 2 presenta ejemplos de complejos descubiertos, con las proteínas de color de acuerdo a sus clasificaciones funcionales. Higo. 3 da ejemplos de dos módulos funcionales: la regulación del ciclo celular y la cascada de MAP quinasa. Gene anotación nos permitió asignar funciones a los complejos identificados. La mayoría de los complejos y los módulos identificados pertenecen a las siguientes cuatro clases funcionales: regulación de la transcripción, del ciclo celular / control de la celda de destino, de procesamiento del ARN, y proteínas de transporte.


Fig. 3.
Ejemplos de módulos funcionales descubiertos. (A) Un módulo implicado en la regulación del ciclo celular. Este módulo consta de ciclinas (CLB1-4 y Cln2) y quinasas dependientes de ciclina (Cks1 y Cdc28) y una proteína nuclear de importación (NIP29). Aunque tienen muchas interacciones, estas proteínas no están presentes en la célula al mismo tiempo. vía de transducción de (B) de la señal de la feromona en la red de interacciones proteína-proteína. Este módulo incluye (MAP quinasa quinasa quinasas) varios MAPK (mitogen-activated proteína quinasa) y MAPKK, así como otras proteínas implicadas en la transducción de señales. Estas proteínas no forman un solo complejo; más bien, en que interactúan en un orden específico.

El mayor complejo totalmente conectado tiene 14 proteínas, todos los cuales son componentes del factor de transcripción SAGA / TFIID. La extensión de 17 miembros de este complejo incluye algunos otros factores de transcripción. Otros complejos de transcripción que se encuentran en la red incluyen el complejo de cuatro miembros de HAP de proteínas de unión a CCAAT, el mediador de siete miembros de regulador de la transcripción (MED), y el complejo NO transcripción. El siguiente a la mayor complejo totalmente conectado consta de 11 proteínas: cuatro son las proteínas de control de la división celular Cdc16, Cdc23, Cdc26 y Cdc27, y los otros siete son subunidades del complejo. En conjunto, estas 11 proteínas constituyen el complejo promotor de la anafase, un componente esencial de la regulación del ciclo celular. Otro complejo implicado en la regulación del ciclo celular es un complejo ubiquitinación de seis miembros (Cdc34, Cdc53, CDC4, MET30, SKP1 y GRR1) conocido por servir de andamiaje Cdc53p y responsable de la transición a la fase S. Los complejos descubiertos incluyen varias máquinas de procesamiento de ARN: (i) un complejo de 12 miembros de varios factores de empalme LSM asociados con el, factor de TopoII asociada mRNA-decapping enzima DCP1, y dos pequeñas 40S subunidades ribosomales; (Ii) un complejo de 14 miembros de los factores de CFI / CFII / PFI y poli polimerasa (A); (Iii) un rRNA de procesamiento complejo (exosome); (Iv) un complejo de cuatro miembros de las subunidades de la endonucleasa de ARNt-empalme; y (v) un complejo de tres factores de empalme de pre-ARNm, unidos a una proteína desconocida que es homóloga a un autoantígeno asociado a un tumor de mama humano (véase el texto de apoyo).

Los módulos tienen más diverso, aunque sigue siendo muy consistente, anotación funcional de los genes. Es importante distinguir entre complejos de proteínas y módulos funcionales, porque tienen diferentes significados biológicos. Un complejo de proteínas es una máquina molecular que consta de varias proteínas (ácidos nucleicos y otras moléculas) que se unen entre sí en el mismo lugar y tiempo (por ejemplo, factores de transcripción, histonas, polimerasas, etc.). Por el contrario, un módulo funcional (31) se compone de un par de proteínas (y otras moléculas) que controlan o realizan una función celular particular a través de interacciones entre ellos. Estas proteínas no necesariamente interactúan en el mismo lugar y hora, o forman un complejo macromolecular (por ejemplo, vía de señalización, la regulación del ciclo celular, etc.). En muchos casos, es difícil hacer esta distinción. Debido a las interacciones de proteínas analizadas por parejas no tienen información temporal y espacial, nuestro método descubre con éxito ambos complejos y módulos, pero no distinguir entre los dos.

La Figura 3 presenta dos módulos identificados: un módulo de ocho miembros dependientes de ciclina quinasas, las ciclinas y sus inhibidores que regulan el ciclo celular (32) (Figura 2 A)., Y la cascada de transducción de señales de feromonas que los andamios en la proteína STE5 (33) ( la Fig. 2B). Otros módulos que se encuentran incluyen un módulo de seis miembros de las proteínas implicadas en la aparición del brote y el establecimiento de polaridad (34, 35) (CDC24, CDC42, FAR1, STE20, BEM1, y RSR1); un módulo de seis miembros de CDC, septins, y las proteínas quinasas Ser / Thr implicadas en el control mitótico; etc (una lista completa de los complejos y módulos con la anotación funcional se proporciona en el texto de apoyo).

La comparación de la predicho con los complejos de derivados experimentalmente (20-22) mostró muy buen acuerdo, tanto en términos de la cobertura y la especificidad de nuestras predicciones. Comparamos complejos con los complejos que se encuentran por (i) la purificación por afinidad en tándem (TAP) y espectrometría de masas (21), catalogada en Cellzome (http://yeast.cellzome.com) identificaron; (Ii) complejos que han encontrado los de alto rendimiento de proteínas de identificación por espectrometría de masas complejo (HMS-PCI) (22), catalogada en la base de datos Biomolecular Interaction red (www.bind.ca); y (iii) otros complejos recogidos de la literatura por los expertos humanos, catalogado en la base de datos MIPS (20). En primer lugar, nos encontramos complejos experimentales que son consistentes con la red estudiado de las interacciones proteína-proteína, es decir, que corresponden a densas regiones de la red. Sólo 29 de los complejos experimentales cumplieron con los criterios estrictos de Q> 0,2 y Pevd <1 × 10-4, y 69 complejos experimentales satisfecho los criterios más débiles de Q> 0,3 y Pevd <0,1. Este resultado no fue una sorpresa, ya que las interacciones de proteínas conocidas representan una pequeña fracción de las interacciones presentes en una célula (9, 10).

A continuación, se comparó la experimentación con los complejos computacionalmente derivados. Para cada complejo computacionalmente derivados, encontramos un complejo experimental mejor coincidencia de al minimizar la probabilidad de una superposición aleatoria entre los dos, usando la siguiente ecuación:

donde N es el número total de nodos en la red, n1 y n2 son los tamaños de dos complejos, y k es el número de nodos que tienen en común. La Fig. 4 presenta la superposición k / n1 entre los que se encuentran los complejos y derivados experimentalmente. De hecho, todos los 29 de los complejos experimentales estrictamente consistentes y la mayor parte de los 69 los débilmente coherentes se encontraron con éxito con 100% de solapamiento. Unos pocos que faltaban o sólo se recuperó parcialmente son más pequeños y más escasa (Fig. 4 recuadro). También se encontró que de los 50 grupos computacionalmente> descubiertos,> 80% corresponde al menos un complejo experimental. Sugerimos que el resto constituye complejos o módulos previamente no.


Fig. 4.
La comparación de los complejos y módulos descubiertos con complejos derivados experimentalmente (BIND) y Cellzome y complejos catalogados en MIPS. complejos descubiertos están ordenados por la superposición con el complejo experimental de mejor coincidencia (ver Métodos y texto de apoyo). El solapamiento se define como el número de proteínas comunes, dividido por el número de proteínas en el complejo experimental mejor de coincidencia. Los primeros 31 complejos coincidir exactamente, y otro 11 tienen solapamiento por encima del 65%. El recuadro muestra la superposición como una función del tamaño del complejo descubierto. Tenga en cuenta que los complejos descubiertos de todos los tamaños partido muy bien con los complejos experimentales conocidos. complejos descubiertos que no coinciden con los experimentales constituyen nuestras predicciones (véase la discusión para más detalles).

Nuestro estudio hace cuatro tipos de predicciones: complejos de proteínas previamente no, previamente miembros no caracterizados en complejos conocidos, miembros de las proteínas no en complejos conocidos y módulos funcionales. Predecimos 8 posibles complejos previamente no, 7 módulos funcionales, 4 proteínas no en diferentes complejos, y 13 complejos con la posible adhesión adicional. Por ejemplo, nos encontramos con una de seis miembros, complejo altamente significativa con Q = 0,73, p = 1 × 10-17, y Pevd = 1 × 10-5 que no aparece entre los complejos de proteínas conocidas. Sólo una proteína de los seis en que complejo se ha caracterizado, como una proteína de membrana YIP1 Golgi (36); los otros no tienen ninguna anotación, aunque comparten alguna homología con proteínas de membrana. El mejor ejemplo de los miembros previamente no conocidos en los complejos es un complejo de 13 proteínas, 11 de los cuales forman el complejo de empalme Lsm, junto con dos pequeñas 40S ribosomal subunidades que al parecer son los nuevos miembros. Estas y otras predicciones de los complejos de proteínas previamente no (véase el texto de apoyo) pueden ser verificados por coimmunoprecipitation o técnicas similares.

Discusión

Hemos demostrado la presencia de grupos altamente conectados de proteínas en una red de interacciones de proteínas. Estos resultados apoyan fuertemente la arquitectura modular sugerido de redes biológicas (31). Mediante el análisis de la función biológica de estos grupos, hemos distinguido dos tipos de agrupaciones: los complejos de proteínas y módulos funcionales dinámicos. Ambos complejos y módulos tienen más interacciones entre sus miembros que con el resto de la red. En un complejo, sin embargo, estas interacciones se realizan al mismo tiempo, con lo que las proteínas que participan juntos (tal vez en un orden diferente, y no simultáneamente). En un módulo más genérico, dinámica, interacciones no se realizan al mismo tiempo o el lugar (por ejemplo, las interacciones entre las CDK y ciclinas en el módulo de regulación del ciclo celular). Los módulos dinámicos son difícil de alcanzar para la purificación experimental porque no se ensamblan como un complejo en un solo punto en el tiempo.

Una ventaja importante de análisis computacional es que permite la detección de dichos módulos mediante la integración de las interacciones moleculares por pares que se producen en diferentes momentos y lugares. El uso de técnicas computacionales solo, sin embargo, no podemos discriminar entre complejos y módulos o entre interacciones transitorias y simultáneas, sino que debe apuntar hacia estudios experimentales posibles módulos funcionales. Por ejemplo, la composición predicha de las dos proteínas ribosómicas en el complejo de corte y empalme Lsm puede ser transitoria, condicional, o simultánea con el resto del complejo Lsm. Estas ambigüedades deben resolverse experimentalmente.

Las estrategias de cálculo como el nuestro necesariamente se basan en datos experimentales con sus limitaciones y errores instrumentales. Un aspecto importante (y lamentable) de alto rendimiento de datos experimentales, es una alta tasa de falsos positivos. Para investigar el grado en que los falsos positivos pueden hacer fracasar el proceso de búsqueda y afectar a grupos identificados (18), que reconectados al azar, eliminado o añadido 10-50% de las interacciones en la red. Se realizaron búsquedas de las agrupaciones en las redes perturbadas y grupos identificados en comparación con los originales. Higo. 5 presenta la fracción de grupos originales que han sido recuperados en las redes perturbadas.

 
Fig. 5.
La fracción de grupos recupera en la red perturbada al azar, como una función de la fracción de enlaces alterados. curvas negras corresponden al caso en que los enlaces se reconectado al azar; rojo, extraídos al azar (verdaderos negativos); y verdes, añadidos al azar (falsos positivos). El clúster original se dice que a su devolución cuando la red perturbada tiene un clúster que comparte al menos el 50% de los nodos con el original. Cada perturbación se repitió 10 veces. Véase también la Fig. 9, que se publica como información de apoyo en el sitio web de PNAS.

Es importante destacar que el ruido en la forma de eliminación o adición de enlaces tiene menos efecto de deterioro del cableado al azar. Alrededor del 75% de los grupos todavía se pueden encontrar cuando el 10% de los enlaces están recableado. Más de 80% de los grupos sostener adición o eliminación de 20% de los enlaces. La robustez de las agrupaciones descubiertos a ruido en los datos surge de la utilización de múltiples interacciones para identificar un clúster. robustez similar se ha demostrado por motivos más pequeños (18).

Naturalmente, nuestra técnica no logra identificar complejos y módulos para los que el número de interacciones conocidas dentro de la agrupación es insuficiente. Encontramos varios complejos y módulos que tienen anotación funcional consistente, pero no son lo suficientemente densa como para ser estadísticamente significativos racimos densos. Omitimos estas agrupaciones de mayor análisis. Del mismo modo, muchos grupitos de tres proteínas (total = 1.444) tienen anotación funcional consistente, pero deben ser considerados con cautela, ya que se espera un gráfico al azar para tener ≈500 tales camarillas (que corresponde a la tasa de falsos positivos del 38%).

Otras técnicas para analizar la estructura de las redes biológicas y sociales se han desarrollado recientemente. Milo et al. (18) estudiaron los pequeños (de tres a cuatro miembros) los motivos que son frecuentes en una red dirigida. Shenn-Orr et al. (7) identificado tres tipos de estructuras frecuentes en la red de transcripción de Escherichia coli. En contraste con estos enfoques, que buscábamos (i) grupos más grandes (4-20) y (ii) grupos que tienen muchas más interacciones dentro que con el resto de la red. Además, no estábamos interesados ​​en la frecuencia de estos grupos en la red, sino más bien con la densidad de las interacciones en los racimos. Este enfoque nos ha permitido destapar grandes complejos y únicos en la red de interacción de proteínas (como el complejo promotor de la anafase). Otra técnica, desarrollado por Girvan y Newman (37), los intentos para descomponer la red entera en componentes débilmente conectadas. Si bien es un enfoque muy prometedor, puede no ser capaz de encontrar regiones pequeñas, altamente conectados incrustadas en una red altamente estructurado, la situación evidente en la red de interacciones de proteínas. Los enfoques de Milo et al., Girvan y Newman, y este estudio son altamente complementarias entre sí porque se dirigen a diferentes preguntas y redes de estudio en diferentes resoluciones.

La red analizados (20) incluye interacciones obtenidos por dos tipos de estudios: experimentos proteómicos a gran escala (de dos híbridos) y los estudios tradicionales, basados ​​en hipótesis de interacciones de proteínas (es decir, a pequeña escala de dos híbridos, coprecipitación, etc.) . proteínas por espectrometría de masas de alto rendimiento de identificación compleja (HMS-PCI) y la purificación por afinidad en tándem (TAP) complejos derivados no eran parte de la base de datos en el momento de la descarga. Curiosamente, la mayoría de los complejos y módulos descubiertos vienen de los estudios tradicionales, en lugar de a partir de experimentos a gran escala. Este hallazgo indica sesgo antropomórfico significativa en el conjunto de interacciones conocidas. También sugiere que aunque los estudios de proteómica a gran escala proporcionan una gran cantidad de datos de interacción de proteínas, la escasez de los datos (y su contaminación con falsos positivos) hace que este tipo de estudios menos valiosas para la identificación de los módulos funcionales. Nuestros resultados sugieren que la integración a gran escala de los datos de dos híbridos con otros tipos de interacciones puede ayudar a superar esta limitación. Nuestra estrategia computacional tiene gran promesa como una herramienta para la integración de diversos tipos de datos en la búsqueda de nuevos módulos funcionales, ya que puede manejar diferentes tipos ( "colores") de las interacciones, incluyendo genética (por ejemplo, syn-letalidad), en proteínas de ADN, y localización de datos. Integración de redes de interacciones físicas con gráficos de las relaciones evolutivas (38) nos puede ayudar a comprender el origen de la modularidad celular.

Hemos demostrado que una técnica computacional puede identificar complejos y módulos de todos los tamaños, incluyendo complejos de transitorios y complejos de baja estequiometría, la superación de las limitaciones de purificación experimental de complejos de proteínas (21, 22). A pesar de que nuestra técnica se basa en las interacciones obtenidos experimentalmente, la naturaleza multicuerpo de complejos descubiertos hace que nuestros algoritmos robustos a la alta tasa de falsos positivos en los datos experimentales. Nuestros resultados sugieren varias hipótesis biológicas comprobables y revelan una modularidad de escala intermedia esencial y la estructura de las redes moleculares multicuerpo.

Referencias

1. Ideker, T., Thorsson, V., Ranish, J. A., Christmas, R., Buhler, J., Eng, J. K., Bumgarner, R., Goodlett, D. R., Aebersold, R. & Hood, L. (2001) Science 292, 929 Abstract/FREE Full Text
2. Kanehisa, M., Goto, S., Kawashima, S. & Nakaya, A. (2002) Nucleic Acids Res. 30, 42 Abstract/FREE Full Text 
3. Karp, P. D., Riley, M., Paley, S. M. & Pellegrini-Toole, A. (2002) Nucleic Acids Res. 30, 59 Abstract/FREE Full Text
4. Uetz, P., Giot, L., Cagney, G., Mansfield, T. A., Judson, R. S., Knight, J. R., Lockshon, D., Narayan, V., Srinivasan, M., Pochart, P., et al. (2000) Nature 403, 623 CrossRefMedlineWeb of Science 
5. Ito, T., Chiba, T., Ozawa, R., Yoshida, M., Hattori, M. & Sakaki, Y. (2001) Proc. Natl. Acad. Sci. USA98, 4569  Abstract/FREE Full Text
6. Lee, T. I., Rinaldi, N. J., Robert, F., Odom, D. T., Bar-Joseph, Z., Gerber, G. K., Hannett, N. M., Harbison, C. T., Thompson, C. M., Simon, I., et al. (2002) Science 298, 799  Abstract/FREE Full Text
7. Shen-Orr, S. S., Milo, R., Mangan, S. & Alon, U. (2002) Nat. Genet. 31, 64  CrossRefMedlineWeb of Science 
8. Deng, M., Sun, F. & Chen, T. (2003) Pac. Symp. Biocomput., 140  Medline
9. Gerstein, M., Lan, N. & Jansen, R. (2002) Science 295, 284  Abstract/FREE Full Text
10. von Mering, C., Krause, R., Snel, B., Cornell, M., Oliver, S. G., Fields, S. & Bork, P. (2002) Nature 417, 399 MedlineWeb of Science 
11. Goldberg, D. S. & Roth, F. P. (2003) Proc. Natl. Acad. Sci. USA 100, 4372  Abstract/FREE Full Text 
12. Podani, J., Oltvai, Z. N., Jeong, H., Tombor, B., Barabasi, A. L. & Szathmary, E. (2001) Nat. Genet.29, 54  CrossRefMedlineWeb of Science
13. Ravasz, E., Somera, A. L., Mongru, D. A., Oltvai, Z. N. & Barabasi, A. L. (2002) Science 297, 1551 Abstract/FREE Full Text 
14. Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N. & Barabasi, A. L. (2000) Nature 407, 651  CrossRefMedlineWeb of Science
15. Maslov, S. & Sneppen, K. (2002) Science 296, 910  Abstract/FREE Full Text
16. Wagner, A. & Fell, D. A. (2001) Proc. R. Soc. London B 268, 1803–1810.  Abstract/FREE Full Text 
17. Jeong, H., Mason, S. P., Barabasi, A. L. & Oltvai, Z. N. (2001) Nature 411, 41  CrossRefMedlineWeb of Science
18. Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D. & Alon, U. (2002) Science 298, 824 Abstract/FREE Full Text
19. Rosenfeld, N., Elowitz, M. B. & Alon, U. (2002) J. Mol. Biol. 323, 785  CrossRefMedlineWeb of Science
20. Mewes, H. W., Frishman, D., Guldener, U., Mannhaupt, G., Mayer, K., Mokrejs, M., Morgenstern, B., Munsterkotter, M., Rudd, S. & Weil, B. (2002) Nucleic Acids Res. 30, 31  Abstract/FREE Full Text
21. Gavin, A. C., Bosche, M., Krause, R., Grandi, P., Marzioch, M., Bauer, A., Schultz, J., Rick, J. M., Michon, A. M., Cruciat, C. M., et al. (2002) Nature 415, 141  CrossRefMedlineWeb of Science
22. Ho, Y., Gruhler, A., Heilbut, A., Bader, G. D., Moore, L., Adams, S. L., Millar, A., Taylor, P., Bennett, K., Boutilier, K., et al. (2002) Nature 415, 180  CrossRefMedlineWeb of Science 
23. Blatt, M., Wiseman, S. & Domany, E. (1996) Phys. Rev. Lett. 76, 3251  CrossRefMedlineWeb of Science 
24. Getz, G., Levine, E. & Domany, E. (2000) Proc. Natl. Acad. Sci. USA 97, 12079 Abstract/FREE Full Text 
25. Getz, G., Vendruscolo, M., Sachs, D. & Domany, E. (2002) Proteins 46, 405  CrossRefMedline Web of Science 
26. Ideker, T., Ozier, O., Schwikowski, B. & Siegel, A. F. (2002) Bioinformatics 18, Suppl. 1, S233 Abstract
27. Pilpel, Y., Sudarsanam, P. & Church, G. M. (2001) Nat. Genet. 29, 153  CrossRef Medline Web of Science
28. Håstad, J. (1996) in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science (IEEE Computer Society, Los Alamitos, CA), pp. 627–636.
29. Leadbetter, M. R., Lindgren, G. & Rootzβen, H. (1983) Extremes and Related Properties of Random Sequences and Processes (Springer, New York). Weng, S., Dong, Q., Balakrishnan, R., Christie, K., Costanzo, M., Dolinski, K., Dwight, S. S., Engel, S., Fisk, D. G., Hong, E., et al. (2003) Nucleic Acids Res. 31, 216 Abstract/FREE Full Text 
30. Hartwell, L. H., Hopfield, J. J., Leibler, S. & Murray, A. W. (1999) Nature 402, C47  CrossRef Medline Web of Science
31. Spruck, C. H. & Strohmaier, H. M. (2002) Cell Cycle 1, 250 Medline
32. Elion, E. A. (2001) J. Cell Sci. 114, 3967 Medline Web of Science
33. Krylov, D. M., Nasmyth, K. & Koonin, E. V. (2003) Curr. Biol. 13, 173 CrossRef Medline Web of Science
34. Segal, M. & Bloom, K. (2001) Trends Cell Biol. 11, 160  CrossRef Medline Web of Science
35. Yang, X., Matern, H. T. & Gallwitz, D. (1998) EMBO J. 17, 4954 Abstract
36. Girvan, M. & Newman, M. E. (2002) Proc. Natl. Acad. Sci. USA 99, 7821 Abstract/FREE Full Text
37. Dokholyan, N. V., Shakhnovich, B. & Shakhnovich, E. I. (2002) Proc. Natl. Acad. Sci. USA 99,14132 Abstract/FREE Full Text

Topologías y charlas de amigos

Representación gráfica de las redes sociales

Pertinent Observations

Cuando me voy a encontrar con un grupo aleatorio de personas que me gustaría graficar las redes sociales en términos de quién conocía a quien antes de la reunión. Por ejemplo, me encontraba con unos amigos ayer - B estaba en la ciudad, y quería conocer a gente. Llamó a A y C, que se llevaba bien con D (también conocido a B). Después de esta reunión B debía reunirse con E, pero E apareció de todos modos. Sobre la base de quién conocía quién antes de la reunión es como la topología de la red emergió. Las personas están representados por vértices y si hay un enlace significa entre ellos se conocen entre sí.



Así comenzó la reunión con A y B, con C suponiendo que aparecería en un momento. Ahora, C conoce a A y B a través de dos "grupos de afiliación" diferentes, pero ambos se conocen muy bien. Así cae a la reunión C, pero ahora la pregunta es ¿de qué se habla? La estructura básica del grupo - donde AB, BC y CA se conocen entre sí a través de tres grupos separados afiliación significa que no se puede hablar de personas (¡por suerte!).

De todos modos la conversación continúa, y entonces D arriba. Cuando B le preguntó a C si podían encontrarse, él dijo: "Yo no estoy en contacto con nadie más aquí en Bangalore. Pero si usted piensa que hay alguien más de nuestra pertenencia a un grupo que está aquí y quiere conocer, llévelos consigo". Por lo tanto, C invita a D (con quién no se ha visto en mucho tiempo) y D arriba.

Ahora, por primera vez, el grupo no es un clique - dado que A y D no se conocen entre sí. Todo depende de B y C ahora para controlar la conversación de una manera que A o D no se aburran. La gente habla de trabajo, carreras y todo eso - donde cualquier persona puede dar charla.

Después de un tiempo, E arriba. Ahora, E no conoce a nadie más en el grupo (excepto B). Así que ahora, el B pasa a ser el vértice de corte. B empieza a hablar a E. Con B y E sacado en la red ACD, C es ahora el vértice de corte! ¡Por lo que ahora le toca a C gestionar la conversación con A y D! ¡C no es particularmente bueno en eso!

Pronto A se retira. Ahora, el grupo se divide de manera efectiva, mientras están sentados en la misma mesa. Las conversaciones de B a E (nadie más conoce a E), y C habla con D. Todo está bien.

El problema con el grupo fue que ninguno de los "conectores" (B, C) fueron particularmente buenos en conectar a la gente, y mantener una conversación. Esto, sin embargo, no fue el caso en una sesión de tragos a la que asistí el lunes por la noche. Allí, la red social al inicio de la conversación se veía así (aquí todas las variables significan diferentes personas, yo sólo era común a las dos reuniones):



Las líneas delgadas aquí indican que B-F y E-F se habían conocido antes, pero no se conocen bastante bien. Como se puede ver, A es ahora el vértice de corte aquí. La diferencia, sin embargo, es que A es un maestro en socialización, y tiene el interés confeso de "juntar gente interesante." El grupo de la reunión fue totalmente también comisariada por A - nadie "se aburrió" con otra persona.

Así que A aseguró que la conversación fluyera. Se aseguró de personas conectadas, y había una gran conversación. Al final del día, ¡la red era un clique!

Nunca he sido bueno para hacer estas conexiones. Temo estar en situaciones donde yo soy el vértice de corte- siempre tuve miedo de que alguien pudiera quedarse afuera. Conectar y juntar gente es, sin duda una habilidad que se necesita desarrollar!

PD: En una cafetería en Mumbai hace ocho veranos, yo estaba en un extremo de una red social qué se veía así. ¡No me preguntes cómo llegué a ser invitado!

ARS 101: Método de percolación de cliques

Método de percolación de cliques


Wikipedia

El método de percolación de clique [1] es un método popular para analizar la estructura de comunidades superpuestas de redes. El término comunidad de redes (también llamado módulo, clúster o grupo cohesivo) ha sido ampliamente aceptado como definición única y por lo general se define como un grupo de nodos que están más densamente conectada entre sí que a otros nodos de la red. Existen numerosos métodos alternativos para la detección de las comunidades en las redes, [2], por ejemplo, el algoritmo Girvan-Newman, la agrupación jerárquica y la maximización de modularidad.


Evolución temporal de las comunidades superpuestas. La estructura (parte) y la dinámica esquemáticas de la red de co-autoría de ~ 30.000 autores cond-mat y la red de comunicación de más de 4 millones de suscriptores de telefonía. De Palla et. al., Nature 446, 664 (2007).

Definiciones

Clique Percolation Method (CPM)

El método de percolación de cliques acumula las comunidades de k-cliques, que corresponden a un grafo completo (totalmente conectados) de sub-grafos de k nodos. (Por ejemplo, una k-clique en k = 3 es equivalente a un triángulo). Dos k-cliques se consideran adyacentes si comparten k - 1 nodos. Una comunidad se define como la unión máxima de k-cliques que se puede alcanzar una de la otra a través de una serie de k-cliques adyacentes. Tales comunidades pueden interpretarse mejor con la ayuda de una plantilla k-clique (un objeto isomorfo a un grafo completo de nodos k). Una plantilla de este tipo puede ser colocado en cualquier k-clique en el gráfico, y rodó a un k-clique adyacente mediante la reubicación de uno de sus nodos y mantener su otro k - 1 nodos fijos. Por lo tanto, las comunidades k-clique de una red son todas aquellas sub-gráficos que se pueden explorar plenamente haciendo rodar una plantilla-k clique en ellos, pero no pueden ser dejados por esta plantilla.

Esta definición permite solapamientos entre las comunidades de una manera natural, como se ilustra en la Figura 1, que muestra cuatro comunidades k-clique en k = 4. Las comunidades están codificados por color y la superposición entre ellas se destacan en rojo. La definición anterior también es local: si un determinado sub-gráfico cumple los criterios para ser considerado como una comunidad, entonces seguirá siendo una comunidad independiente de lo que sucede a otra parte de la red lejos. Por el contrario, en la búsqueda de las comunidades mediante la optimización con respecto a una cantidad global, un cambio muy lejos, en la red se puede formar de nuevo las comunidades de las regiones perturbadas también. Además, se ha demostrado que los métodos globales pueden sufrir de un problema de límite de resolución, [3], donde el tamaño de la comunidad más pequeña que se puede extraer es dependiente del tamaño del sistema. Una definición de la comunidad local, como aquí evita este problema de forma automática.

Puesto que incluso las redes pequeñas pueden contener un gran número de k-cliques, la aplicación de este enfoque se basa en la localización de las cliques máxima en lugar de los k-cliques individuales. [1] Por lo tanto, la complejidad de este enfoque en la práctica es equivalente a la del hallazgo NP-completo máxima de clique, (a pesar de que la búsqueda de k-cliques es polinómica). Esto significa que aunque las redes con pocos millones de nodos ya se han analizado con éxito con este enfoque, [4] ninguna estimación previa se puede dar para el tiempo de ejecución del algoritmo basado simplemente en el tamaño del sistema.


Fig.1. Ilustración de las comunidades k-clique en k = 4.

Método de percolación de cliques dirigidos (CPMD)

En una red con enlaces dirigidos a k-clique dirigida es un subgrafo completo con nodos k cumplir la siguiente condición. Los nodos k pueden ser ordenados de tal manera que entre un par arbitrario de ellos existe un enlace apuntando dirigida desde el nodo con el rango más alto hacia el nodo con el rango inferior. The Clique Método percolación dirigida define dirigida comunidades en red como los clusters de percolación de k-cliques dirigidos.

Método de percolación de cliques ponderado (CPMw)

En una red con enlaces ponderados una k-clique ponderada es un subgrafo completo con k nodos tales que la media geométrica de la k (k - 1) / 2 de enlace de pesos dentro de la k-clique es mayor que un valor umbral seleccionado, I. The Clique ponderado Método percolación define comunidades red ponderados como los clusters de percolación de k-cliques ponderados. Tenga en cuenta que la media geométrica de los pesos de enlace dentro de un subgrafo se llama la intensidad de ese subgrafo. [5]

Generalizaciones de grafos de clique

Los métodos de percolación de clique pueden generalizarse mediante el registro de diferentes cantidades de solapamiento entre las distintas k-cliques. Esto define entonces un nuevo tipo de gráfico, un grafo clique, [6], donde cada k-clique en el gráfico original se representa por un vértice en el nuevo grafo clique. Los enlaces en el grafo de clique se utilizan para registrar la fuerza de la superposición de cliques en el gráfico original. Entonces, uno puede aplicar cualquier método de detección de la comunidad a este grafo clique para identificar los grupos en la gráfica original a través de la estructura de k-clique.

Por ejemplo, en un gráfico simple, podemos definir la superposición entre dos k-cliques ser el número de vértices comunes a los dos k-cliques. El método de percolación de cliques es entonces equivalente a thresholding este grafo clique, cayendo todos los enlaces de peso menor que (k-1), con los componentes conectados restantes que forman las comunidades de cliques que se encuentran en la RPC. Para k = 2 las cliques son los enlaces del grafo original y la grafo de clique en este caso es el grafo de líneas de la red original.

En la práctica, utilizando el número de vértices comunes como una medida de la fuerza de solapamiento clique puede dar resultados pobres como grandes clique en el gráfico original, los que tienen muchos más de k vértices, dominarán el grafo de clique. El problema surge porque si un vértice está en n diferentes k-cliques que contribuirá a n (n-1) / 2 enlaces en un gráfico como clique. Una solución sencilla es dejar que cada vértice común a dos kcliques superpuestas para contribuir un peso igual a 1 / n en la medición de la fuerza de la superposición de los dos k-cliques.

En general, el punto de vista del grafo clique es una manera útil de encontrar generalizaciones de métodos de percolación de cliques estándar para obtener algún problema redondas encontradas. Incluso muestra cómo describir las extensiones de estos métodos basados en otros motivos, subgrafos distinta k-cliques. En este caso un gráfico clique es mejor pensamiento de un ejemplo particular de un hipergrafo.

Transición de percolación en el CPM

El modelo Erdös-Rényi muestra una serie de transiciones interesantes cuando se aumenta la probabilidad p de dos nodos están conectados. Para cada k uno puede encontrar un cierto pc probabilidad umbral por encima del cual los k-cliques se organizan en una comunidad gigante. [7] [8] (El tamaño de la comunidad gigante es comparable con el tamaño del sistema, en palabras oder la comunidad gigante ocupa una parte finita del sistema incluso en el límite termodinámico.) Esta transición es análoga a la transición de percolación en la física estadística. Un fenómeno similar se observa en muchas redes reales, así: si k es grande, sólo las partes más densamente vinculados son aceptadas como las comunidades, por lo tanto, por lo general permanecen pequeñas y dispersas. Cuando se baja k, tanto el número como el tamaño de las comunidades comienzan a crecer. Sin embargo, en la mayoría de los casos un valor crítico k puede ser alcanzado, por debajo del cual una comunidad gigante emerge, manchando los detalles de la estructura de la comunidad mediante la fusión (y haciendo invisibles) muchas comunidades más pequeñas.

Aplicaciones

El método de percolación clique había sido utilizada para detectar las comunidades de los estudios de la metástasis del cáncer [9] [10] a través de diversas redes sociales [4] [11] [12] [13] [14] para documentar la agrupación [15] y las redes económicas . [16]

Algoritmos y Software

Hay un número de implementaciones de percolación clique. El método de percolación de clique se implementó y popularizado por CFinder [1] (freeware para uso no comercial) de software para detectar y visualizar comunidades superpuestas en las redes de primera. El programa permite la visualización personalizable y permite un fácil paseo a través de las comunidades que se encuentran. El paquete contiene una versión de línea de comandos del programa, así, que es adecuado para scripting.

Una implementación más rápida (disponible bajo la licencia GPL) ha sido implementado por otro grupo. [17] Otro ejemplo, que también es muy rápido en ciertos contextos, es el algoritmo SCP. [18]

Algoritmos Paralelos

Una versión paralela del método de percolación cliques fue diseñado y desarrollado por S. Mainardi et al .. [19] Mediante la explotación de multi-core / multi-procesador arquitecturas de computación de hoy en día, el método permite la extracción de las comunidades k-cliques de redes muy grandes tales como Internet. [20] los autores lanzaron el código fuente del método bajo la GPL y lo hizo libremente disponible para la comunidad.

Referencias

• Uncovering the overlapping community structure of complex networks in nature and society G. Palla, I. Derényi, I. Farkas, and T. Vicsek: Nature 435, 814–818 (2005)
• Community detection in graphs by S. Fortunato, Physics Reports 486, 75-174 (2010)
• Resolution limit in community detection S. Fortunato and M. Barthelemy: Proc. Natl. Acad. Sci. USA 104 (1), 36–41 (2007)
• Quantifying social group evolution G. Palla, A.-L. Barabási and T. Vicsek: Nature 446, 664–667(2007)
• Intensity and coherence of motifs in weighted complex networks J.-P. Onnela, J. Saramäki, J. Kertész, and K. Kaski: Phys. Rev. E 71, 065103 (2005)
• Clique Graphs and Overlapping Communities T.S. Evans: J. Stat. Mech. P12037 (2010) doi:10.1088/1742-5468/2010/12/P12037
• Clique percolation in random networks I. Derényi, G. Palla, and T. Vicsek: Phys. Rev. Lett. 94, 160202 (2005)
• The critical point of k-clique percolation in the Erdos–Renyi graph G. Palla, I. Derényi, and T. Vicsek: J. Stat. Phys. 128, 219–227 (2007)
• Global topological features of cancer proteins in the human interactome P.F. Jonsson and P.A. Bates: Bioinformatics 22(18):2291–2297 (2006)
• Cluster analysis of networks generated through homology: automatic identification of important protein communities involved in cancer metastasis P.F. Jonsson, T. Cavanna, D. Zicha and P. A. Bates: BMC Bioinformatics 7, 2 (2006)
• A system of mobile agents to model social networks M.C. Gonzalez, P.G. Lind and H.J. Herrmann: Phys. Rev. Lett. 96, 088702 (2006)
• Emergence of communities in weighted networks J.M. Kumpula, J.-P. Onnela, J. Saramaki, K. Kaski and J. Kertész: Phys. Rev. Lett. 99, 228701 (2007)
• A Model for Social Networks R. Toivonen, J.-P. Onnela, J. Saramäki, J. Hyvönen and K. Kaski: Physica A-Statistical Mechanics and its Applications 370, 851–860 (2006)
• Community structure and ethnic preferences in school friendship networks M. C. Gonzalez, H. J. Herrmann, J. Kertesz and T. Vicsek: Physica A-Statistical Mechenics and its Applications 379, 307–316 (2007)
• Natural Document Clustering by Clique Percolation in Random Graphs W. Gao and K.-F. Wong: Lect. Notes in Comp. Sci. 4182, 119–131, (2006)
• Spectral and network methods in the analysis of correlation matrices of stock returns T. Heimo, J. Saramaki, J.-P. Onnela and K. Kaski: Physica A-Statistical Mechenics and its Applications 383, 147–151 (2007)
• Percolation Computation in Complex Networks Fergal Reid, Aaron McDaid, Neil Hurley: ASONAM 2012, (2012)
• Sequential algorithm for fast clique percolation Jussi M. Kumpula, Mikko Kivelä, Kimmo Kaski, and Jari Saramäki: Phys. Rev. E 78, 026109 (2008) (2008)
• Parallel k-Clique Community Detection on Large-Scale Networks Enrico Gregori, Luciano Lenzini and Simone Mainardi: IEEE Transactions on Parallel and Distributed Systems, 31 Aug. 2012.
• k-clique Communities in the Internet AS-level Topology Graph Enrico Gregori, Luciano Lenzini and Chiara Orsini: International Conference on Distributed Computing Systems Workshops (ICDCSW), 2011.

La fragmentación y el desafío para el ARS

Fragmentación, minimización y alianzas de redes cruzadas

A menudo escuchamos que el universo se está expandiendo, pero nuestra propia experiencia es que la fragmentación es creciente. Los objetos son más pequeños, los textos más cortos, los equipos más delgados. Es claramente una tendencia importante que también produce los nuevos desafíos. ¿Cómo dar sentido a esos pedazos de información? ¿Cómo pueden colaborar los equipos más pequeños para servir a los propósitos comunes?

A medida que las transmisiones simultáneas sin fin de tweets y actualizaciones de estado proliferan a través de las redes digitales, las revistas de negocios están llenos de consejos sobre fragmentar las estructuras organizativas.

Lo que estamos presenciando es la continua transformación de las estructuras sociales en respuesta a los flujos de datos cada vez más fragmentadas y sensibles al tiempo.

Pequeños equipos temporales basados ​​en proyectos inspirados en DARPA (la agencia que inventó el Internet) se implementan en los departamentos de Motorola Mobile por ex ejecutivos de DARPA.

"Unidades de práctica" en los hospitales que se forman con rapidez para resolver ciertas tareas y disolverse después de reintegrarse posteriormente a una nueva constelación han demostrado su eficacia en la atención de la salud.

Lo que estamos presenciando es la continua transformación de las estructuras sociales en respuesta a los flujos de datos cada vez más fragmentadas y sensibles al tiempo. De ahí la creciente importancia de las alianzas entre redes: las colaboraciones e interacciones entre los nodos que pertenecen a diferentes camarillas o cliques.

Además, incluso los datos en sí tiene que migrar a las nuevas infraestructuras que apoyen su creciente fragmentación y conectividad.

El origen de este reto muy positivo proviene de las redes comunicacionales. Paquete de tamaño modelo de conmutación de datos se utiliza para transmitir información de toda la web. Cuando estás hablando por Skype y decir " Hola ", la palabra se desmonta en pequeñas partículas, que más tarde conseguir volver a montar de nuevo cuando llegan a su destino con la meta-información suministrada. En el mundo de los datos de cada nodo en la red comunicacional actúa como un transmisor, relativa a sí mismo menos con el mensaje, más con los procedimientos de reencaminamiento.

El mismo comportamiento se adaptó cada vez más en las estructuras sociales. La frecuencia de la comunicación es cada vez mayor, los paquetes de datos se están convirtiendo (actualizaciones de Facebook a los tweets de Snapchat) más y más pequeño. La gente hace "Repost", "Gustan", "Reiteran " o "Liberan" de una manera que tiene más que ver con el reflejo que con la respuesta. Las estructuras sociales son cada vez más como un animal: pequeñas camarillas temporales, tácticas altamente expresados ​​enjambre (aunque sólo sea en ámbito digital), conjuntos orientados a tareas, reflexiva sobre sensible.

Hay muchas ventajas en este diseño de red de reciente aparición. Equipos más pequeños han demostrado ser mejores en su adaptación al entorno en constante cambio. Fragmentos informativos cortos están mucho más estrechamente relacionados con el momento de tiempo pertinente. La unidad común de crear nueva tecnología inteligente hace que sea necesario traducir lo que ya sabemos en una forma que pueda ser entendida por las máquinas: hechos, ideas y las relaciones entre ellos.

Lo que es importante es la creación de infraestructuras que apoyen el diseño de la red emergente se define por la fragmentación. Las herramientas y las prácticas que ayudan a los grupos de comunicación, miembros de la bolsa, fusionar temporalmente y trabajar en pro de un objetivo común se convertirán cada vez más en la demanda.

Nodus Labs

ARS 101: Clique

Clique

El grafo completo K5. En un subgrafo como éste,
los vértices forman un clique de tamaño 5.

En teoría de grafos, un clique en un grafo no dirigido G es un conjunto de vértices V tal que para todo par de vértices de V, existe una arista que las conecta. En otras palabras, un clique es un subgrafo en que cada vértice está conectado a cada otro vértice del grafo. Esto equivale a decir que el subgrafo inducido por V es un grafo completo. El tamaño de un clique es el número de vértices que contiene.

El Problema del clique, que consiste en dado un grafo, decidir si existe en él un clique con un tamaño particular, es NP-completo.

Lo opuesto de un clique es un conjunto independiente, en el sentido que cada clique corresponde a un conjunto independiente del grafo complemento.

Los nodos 1,2 y 5 forman un clique

Origen del nombre

El término proviene de la palabra inglesa clique, que define a un grupo de personas que comparten intereses en común. En esta analogía, las personas serían los vértices; las relaciones de interés, las aristas; y el hecho de que todas compartan un mismo interés, el grafo completo, es decir, el clique en si.

Referencias

El término "clique" en Wolfram MathWorld

Wikipedia