lunes, 29 de agosto de 2016

ARS 101: Clausura triádica

Grafos para bases de datos para principiantes: Teoría de grafos y modelado predictivo

Conexión de nodos en una base de datos gráfica es fundamentalmente diferente de llenar una tabla con datos. Si usted es nuevo para representar gráficamente las bases de datos: Lee esto.

  por Joy Chao ·- DZone

Los grafos están en todas partes, desde que ilustra las conexiones entre los caracteres de Juego de Tronos hasta el seguimiento de las interacciones intermediarios cientos de miles de servidores en una red pública.

A lo largo de esta serie blog, hemos hablado mucho sobre los detalles prácticos de trabajo con las bases de datos del gráfico. Ahora es el momento para hablar de la teoría de grafos, con su una aplicación mucho más práctico para la vida cotidiana.

Como un campo más desarrollado, la teoría de grafos nos ayuda a ganar la penetración en nuevos dominios. En combinación con las ciencias sociales, hay muchos conceptos que se pueden utilizar sin rodeos para obtener información de los datos del gráfico.

En este serie del blog “Graph Databases for Beginners”, hemos discutidos sobre why graphs are the future, why data relationships matter, the basics of data modeling, data modeling pitfalls to avoid,why a database query language matters, why we need NoSQL databases, ACID vs. BASE, a tour of aggregate stores, other graph data technologies, native versus non-native graph processing and storage, y algoritmos de búsqueda en grafos.
En el post de la semana pasada, hemos explicado los mecanismos transversales de menor nivel de algoritmos de grafos. Si usted no ha leído todavía, yo recomendaría hacerlo con el fin de entender mejor el orden superior de los análisis que vamos a discutir. Ahora vamos a echar un vistazo a algunos de los conceptos clave de la teoría de grafos social.

Las clausuras triádicas

Una de las propiedades más comunes de gráficos sociales es el de cierres triádicas. Esta es la observación de que si dos nodos están conectados a través de un camino con un tercer nodo mutuo, hay una mayor probabilidad de que los dos nodos se conviertan conectado directamente en el futuro.

En un entorno social, un cierre triádica sería una situación en la que dos personas con un amigo en común tienen una mayor probabilidad de encontrarse entre sí y convertirse en conocerse.

La propiedad de encierro triádica es más probable que se confirmó cuando un gráfico que tiene un nodo A con una fuerte relación con otros dos nodos, B y C. Esto da a continuación, B y C Una probabilidad de una relación, ya sea débil o fuerte. Aunque esto no es una garantía de una relación potencial, que sirve como un indicador predictivo creíble.

Vamos a echar un vistazo a este ejemplo.





Por encima de una jerarquía organizativa en Alice maneja tanto Bob y Charlie. Esto es bastante extraño, ya que sería poco probable que Bob y Charlie sean no conocerse mientras que comparte el mismo administrador.

Tal como es, hay una gran posibilidad de que terminarán trabajando juntos debido a la propiedad de clausura triádica. Esto creará una relación cualquiera WORKS_WITH [Trabaja_con] (fuerte) o (débil) PEER_OF [Es_par_de] entre ellos dos, cerrando el triángulo - por lo tanto el término clausura triádica.





Balance estructural

Sin embargo, otro aspecto a considerar en la formación de clausuras triádicas estables es la calidad de las interacciones existentes en el gráfico. Para ilustrar el concepto siguiente, asumen que la relación MANAGES [DIRIGE A] es algo negativo, mientras que las relaciones PEER_OF y WORKS_WITH son más positivas.

Basado fuera de la propiedad de encierro triádica, podemos suponer que podemos llenar la tercera relación con cualquier etiqueta, como todo el mundo que tiene gestionar entre sí como en la primera imagen de abajo o la situación extraña en la segunda imagen a continuación.





Sin embargo, se puede ver cómo esas situaciones incómodas de trabajo estarían en realidad. En la segunda imagen, Charlie encuentra a sí mismo tanto el par de un jefe y un compañero de trabajo. Sería difícil para Bob a encontrar la manera de tratar a Charlie - como un compañero o compañera de trabajo como el de pares de su jefe?

Tenemos una preferencia innata por la simetría estructural y estratificación racional. En la teoría de grafos, esto se conoce como equilibrio estructural.

Una clausura triádica estructuralmente equilibrado está hecha de relaciones de todos los sentimientos fuertes y positivos (tales como el primer ejemplo de abajo) o dos relaciones con los sentimientos negativos y una única relación positiva (segundo ejemplo).




Aprender a utilizar los conceptos de la teoría de grafos sociales y modelos de predicción para entender los datos conectados

cierres equilibrados ayudan con el modelado predictivo en los grafos. La simple acción de búsqueda de posibilidades para crear cierres equilibradas permite la modificación de la estructura gráfica para el análisis de predicción precisa.

Los puentes locales

Podemos ir más allá y obtener una perspectiva más valioso en el flujo de las comunicaciones de nuestras organizaciones examinado puentes locales. Estos se refieren a un empate entre dos nodos en los extremos del puente local no están conectados de otro modo, ni comparten los vecinos comunes. Se puede pensar en puentes locales como las conexiones entre dos grupos distintos de los grafos. En este caso, uno de los lazos tiene que ser débil.

Por ejemplo, el concepto de vínculos débiles es relevante en algoritmos para la búsqueda de empleo. Los estudios han demostrado que las mejores fuentes de empleo provienen de conocidos más flexibles, más que amigos cercanos. Esto se debe a los amigos más estrechos tienden a compartir una visión del mundo similar (están en la misma componente gráfico) pero los amigos más flexibles a través de un puente local son en una red social diferente (y están en un grafo de un componente diferente).





En la imagen de arriba, Davina y Alice están conectadas por un puente local, sino que pertenecen a diferentes componentes del grafo. Si Davina fueron a buscar un nuevo trabajo, que sería más probable encontrar una recomendación éxito de Alicia que de Frances.

Esta propiedad de los puentes locales son débiles es algo que se encuentra a través de grafos sociales. Como resultado, podemos hacer los análisis predictivos basados ​​en puente locales derivada empíricamente y fuertes nociones de cierre triádicas.

Conclusión final

Si bien los grafos y nuestra comprensión de ellos tienen su origen en cientos de años de estudio, seguimos encontrando nuevas maneras de aplicar a nuestra vida personal, social y de negocios. La tecnología actual ofrece otro método para la comprensión de estos principios en la forma de grafos de base de datos moderna.

Como hemos visto a lo largo de la serie "Grafos de bases de datos para principiantes" del blog, simplemente hay que entender cómo aplicar algoritmos de teoría de grafos y técnicas de análisis con el fin de lograr nuestros objetivos. Tome una mirada retrospectiva a los demás puestos de esta serie y obtendrá las habilidades que necesita para aprovechar el poder de los gráficos.

sábado, 27 de agosto de 2016

ARS 101: Asortatividad (2)

Asortatividad


La asortatividad es la preferencia de los nodos de una red por unirse a otros que le son similares en alguna característica. A pesar de que la medida específica de similitud puede variar, los teóricos de redes frecuentemente estudian la asortatividad en función del grado de los nodos.1 Esta característica sirve para aproximar los modelos de redes complejas al comportamiento de muchas redes reales.

Frecuentemente se encuentran correlaciones entre los nodos de redes que tienen grado similar. Además, en las redes sociales, los nodos con alta conectividad tienden a conectarse a otros que tiene un grado alto. Esta tendencia se denomina asortatividad. Por otro lado, las redes tecnológicas y biológicas tiende a mostrar comportamiento disortativo ya que los nodos con alto grado tienden a conectarse con los nodos de bajo grado.2



Redes libres de escala para los diferentes grados de asortatividad: (a) A = 0 (la red no correlacionada), (b) A = 0,26, (c) A = 0,43, donde A indica r (coeficiente asortatividad, tal como se define en este sub- seccion 3]

Midiendo la asortatividad

La asortatividad se presenta como la correlación entre dos nodos. Sin embargo, existen diferentes formas de medir dicha correlación. Las medidas más utilizadas son el coeficiente de asortatividad y la conectividad. Estas medidas se detallan más ampliamente a continuación

Coeficiente de asortatividad

El coeficiente de asortatividad se trata del coeficiente de correlación de Pearson de los grados entre dos pares de nodos conectados.2 Valores positivos de r indican que existe una correlación entre nodos con grado similar, mientras que un valor negativo indica correlaciones entre nodos de diferente grado. En general, r toma un valor comprendido entre -1 y 1. Cuando r = 1, se dice que la red es totalmente asortativa, cuando r = 0 la red es no asortativa y cuando r = -1 la red es disortativa.

El coeficiente de asortatividad viene dado por
{\displaystyle r={\frac {\sum _{jk}{jk(e_{jk}-q_{j}q_{k})}}{\sigma _{q}^{2}}}}


Aplicación

Las propiedades de asortatividad son útiles en el campo de la epidemiología porque pueden ayudar a comprender la propagación de enfermedades. Por ejemplo, eliminar una porción de los nodos de una red puede corresponder a curar, vacunar o poner en cuarentena células. Desde que se demostró que las redes sociales son asortativas, se sabe que enfermedades dirigidas a individuos con alto grado tienden a propagarse a otros individuos altamente conectados, por ejemplo las enfermedades de transmisión sexual en una red de contactos sexuales. Alternativamente, dentro de las redes celulares, como las redes biológicas son altamente disortativas, las estrategias de vacunación dirigidas a los nodos con alto grado pueden detruir rápidamente la epidemia.

Patrones de mezcla selectivo de las redes reales 



Fig. 3:. Tamaño N y el coeficiente r de asortatividad por varias redes [2]

Los patrones selectivo de una variedad de redes del mundo real se han examinado. Por ejemplo, la Fig. 3 enumera los valores de r para una variedad de redes. Tenga en cuenta que las redes sociales (las primeras cinco entradas) tienen mezcla selectivo aparente. Por otro lado, las redes tecnológicas y biológicas (las medias de seis entradas) todos parecen ser disasortativas. Se ha sugerido que esto es porque la mayoría de las redes tienen una tendencia a evolucionar, a menos que se limite de otra, hacia su estado de máxima entropía, que es por lo general disasortativa. [9]

La tabla también tiene el valor de r calculado analíticamente por dos modelos de redes:

  • el gráfico aleatoria de Erdös y Rényi
  • Modelo BA (modelo Barabási y Albert)

En el modelo de sala de emergencia, ya que los bordes se colocan al azar sin tener en cuenta el grado de vértice, se sigue que r = 0 en el límite de tamaño grande gráfico. Curiosamente, el modelo BA libre de escala también posee esta propiedad. Para el modelo de BA en el caso especial de m = 1 (donde cada nodo de entrada se une a sólo uno de los nodos existentes con una probabilidad grado proporcional), tenemos r\to 0  a medida que (\log^2 N)/N en el límite de un N grande. [2]


Wikipedia
Wikipedia

jueves, 25 de agosto de 2016

Redes de 2 modos en Pajek (1/2)

El análisis de la red de 2 modos usando Pajek - Parte 1
 Intan Dzikria - Blog My Life, My Dreams




Este semestre tengo que aprender algo interesante llamado análisis de redes sociales. Al principio pensé que se siente red social un poco las cosas, por ejemplo, Facebook, Twitter, etc. Pero, en realidad son página web de redes sociales y un caso de análisis.

Déjeme decirle algo simple de pensar. Usted tiene amigos en Facebook ¿verdad? Y su amigo tienen amigos en común con usted, y sus otros amigos también. Estos pueden construir una red, llamada red social. Esta red puede tener muchos beneficios del tipo, por ejemplo, que son sus amigos que tienen mayor influencia en la red, así que si hay cualquier caso se puede pedir que le digan a sus amigos.

Hay dos tipos de red, 1-modo y la red de 2-modos. La red de 1-modo sólo tiene 1 caso / actor. Por ejemplo, tus amigos de la red sólo tienen el nombre de sus amigos allí. Sin embargo, la red de 2 modos tiene 2 variables, por ejemplo, el nombre de sus amigos y sus aficiones.

En este artículo, te voy a mostrar cómo analizar la red de 2 modos. En este artículo se compone de varias partes que son la forma simplificar una red, encontrar centralidad, y hacer un agrupamiento.

Hay muchos programas de análisis de redes sociales, sino porque acabo de aprender acerca de este software, Pajek, voy a utilizar este software en su lugar. Pajek es un software gratuito que se puede descargar aquí.

En primer lugar, Abra su Pajek y haga clic en File - Pajek Project File - Read para leer su archivo .paj
Si usted no tiene .paj presentar también se puede abrir el fichero con .net clic en File - Network - Read



Después de abrir el archivo, se abrirá una ventana Informe que muestra todo lo que has hecho usando Pajek. Una especie como una ventana de registro.




En segundo lugar, Dibuje su red con hacer clic en Draw - Network



Su red se mostrará en la ventana de dibujo. Se puede cambiar el dibujo con varias algoritmo proporcionado en el Pajek. Sólo cliqueé en la Layout - Energy - Kamada Kawai - Free o Layout Enegery - Fruchterman Reingold - 2D



Otro dibujo será así. Cada vez que hizo el algoritmo de dibujo, se muestran distintos resultados.



Por lo tanto, debido a que es una red de 2 modos, hay que hacerlo en el segmento 1-mode primero antes de continuar su posterior análisis. Porque va a mostrar resultado más amplio de 2 variables (actor y eventos).

Tercero, cambio el 2-mode al 1-mode network con 
Network - 2 Mode Network - 2 Mode to 1 Mode - Rows (establece la proyección de los eventos)
Network - 2 Mode Network - 2 Mode to 1 Mode - Column (establece la proyección de los actores)

La diferencia entre filas y la columna se encuentra en la proyección. Así, por ejemplo, aquí tengo una red que los actores son el nombre de los estudiantes en la clase y los eventos son los sueños. Viceversa.



Después de que el cambio en el segmento 1-modo, si elijo la proyección caso, el dibujo sólo se muestra la proyección de los estudiantes.



Pero, si elijo la proyección actor, el resultado es sólo los sueños de los estudiantes.



En cuarto lugar, simplificar la red

Vamos a ver la proyección de eventos en lugar porque es más complicada que la proyección actor. Debido a que es demasiado complicado lo que queremos es hacer que sea más sencillo, pero ¿cómo?

Tenemos que saber primero el valor de cada línea. El significado de esto es que una persona puede tener más de 2 sueños, ¿verdad? pero maestra pidió a los estudiantes a elegir sus sueños no más de 4. Así, disponemos de red que muestra la elección de los estudiantes entre 2 hasta 4 opciones. Y si queremos hacer la red más simple, le toca a nosotros el grado mínimo de la red.

Está bien, por ejemplo, que quieren eliminar las líneas que menor que 3. Es decir, la red sólo se muestra a los estudiantes que tienen 3 y 4 opciones de sueños.

Para ello, lleve a cabo esta acción en el Pajek. Haga clic en Network - Create New Network - Transform - Remove - Lines with Value - Lower Than



Una pequeña ventana pop-up e insertar el valor de umbral. El mío es 3. Por lo tanto, me escriba 3 en el cuadro. A continuación, haga clic en OK. Habrá otra ventana aparecerá, pero basta con hacer clic en Ok.



Cuando dibujo la red, que será como esta. Usted puede ver que hay varios vértices o mis amigos en la clase que no tienen línea o enlazar con otros vértices, ¿verdad? Queremos hacer de la red simple, ¿por qué no lo reducimos?



Para reducir los vértices que no tienen vínculos, usted tiene que realizar esta Network - Create New Network - Transform - Reduction - Degree - All

Grado en que aquí es el número de enlaces a los vértices. Por ejemplo, en este caso, el grado mínimo que quiero en mi red es 1. Debido a Sherry y Pietsia tienen 0 grados, serán retirados de la red.



Introducir el grado mínimo que desee, por mí Quiero 1. Habrá otra ventana que se pop-up y haga clic Yes.



Cuando dibujo la red, los vértices que tienen de 0 grados es ya no existen en la red.



Para ver el número de línea, puede hacer clic en Options - Lines - Mark Lines - With Values en la ventana de dibujo.




En quinto lugar, guarde su Red

Por último, no se olvide de guardar su red simplificada para su posterior análisis como para la agrupación, ya que no desea llevar a cabo las mismas acciones de vez en cuando, ¿verdad?

Para guardar su red, se puede hacer clic en el botón Guardar en las Redes section.or haga clic en File - Network - Save..

Voy a ir a la siguiente parte del tutorial Pajek. Si usted tiene alguna pregunta sobre esta parte, por favor, comentario a continuación. :)

Espero que este post ayuda. ^^

Se puede ver la siguiente parte de este enlace

domingo, 21 de agosto de 2016

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

viernes, 19 de agosto de 2016

Modularidad local en clusters

La medida de modularidad local para los agrupamientos de red

Phys Rev E Stat Nonlin Soft Matter Phys. 2005 Nov; 72 (5 Pt 2): 056107
Autores: Muff S, F. Rao, Caflish A.
Fuente



Muchas redes complejas tienen una estructura modular subyacente, es decir, subunidades estructurales (comunidades o grupos) caracterizada por nodos altamente interconectados. La modularidad se ha introducido como una medida para evaluar la calidad de clusterizations. tiene una visión global, mientras que en muchas redes del mundo real racimos están vinculadas principalmente a nivel local entre sí (conectividad clúster local). Aquí introducimos una medida de la modularidad localizada, lo que refleja la estructura de las agrupaciones locales. Y optimización de la clusterización de dos redes biológicas que muestra la modularidad identifica localizada racimos más cohesionadas, dando una visión complementaria de una mayor granularidad.

PMID: 16383688 [PubMed]





miércoles, 17 de agosto de 2016

Marc Smith: "Hacia la estructura social de los medios sociales"

'La estructura es la próxima gran cosa en la analítica de los medios sociales'
Entrevista con Marc Smith, director de la Fundación de Investigación de Medios de Comunicación Social
Innovation Enterprise



Marc Smith es un sociólogo especializado en la organización social de las comunidades en línea y la interacción mediada por ordenador. Smith lidera el grupo de consultoría acción relacionada y vive y trabaja en Silicon Valley, California. Smith co-fundó la Social Media Research Foundation, una organización no lucrativa dedicada a abrir herramientas, datos, y la beca de investigación relacionadas con los medios de comunicación social. Mientras que en Microsoft Research, fundó el Community Technologies Group y llevó al desarrollo del motor de aplicaciones web y minería de datos "Netscan" que permitió a los investigadores que estudiar los grupos de noticias de Usenet y los registros relacionados de conversaciones roscadas para obtener informes sobre las tasas de publicación de anuncios, carteles, crossposting , longitud de la rosca y la distribución de frecuencias de la actividad.

Nos sentamos con él antes de su presentación en el Social Media and Web Analytics Innovation Summit, que tendrá lugar en Chicago en noviembre 29-30.
¿Qué ves como las tendencias clave que afectan al mundo de las mediciones de medios sociales y analítica web en el 2016?

Hay un número cada vez mayor de requisitos de negocio que se basa en los datos, y el acceso a los datos y presentación de informes será esencial. La extracción de los mejores y más rápidas penetraciones será un factor determinante, y los métodos para el análisis será fundamental para hacer esto. Más central de este cambio es la teoría analítica de la red.

¿Hay alguna desarrollos particulares que harán que sea más difícil para los vendedores y analistas para derivar información de los datos sociales / web?

El acceso a la API está siendo limitado por las plataformas para impulsar los vendedores y analistas con respecto a sus propias soluciones de análisis.

La sofisticación requisitos analíticos están aumentando. Una sólida formación en ciencias de datos se está convirtiendo en un requisito para la comercialización!

¿Cuáles son los desarrollos que harán que sea más fácil para derivar la penetración y mejorar el valor de negocio?

Los recursos informáticos son más baratos que nunca y siguen bajando de precio. Una clase de centros de datos del mundo con recursos de supercomputación también se pueden alquilar por un día a precios muy atractivos.

Mejores herramientas están llegando que simplifican el análisis, proceso de penetración de recogida de datos. De la misma manera que la autoedición transformó el papel de la 'impresora', herramientas analíticas que guían a los usuarios a través de procesos complejos aumentará los personas que carecen de los conocimientos técnicos profundos necesarios para hacerlo a mano.

¿Hay alguna ganadores o perdedores obvios como los medios sociales y analítica web y optimización de los mercados continúan madurando y evolucionando?

Las herramientas que van más allá del modelo de conteo y de búsqueda que domina ahora obtendrán grandes ventajas. La mayoría de las herramientas actualmente miran volúmenes de mensajes, carteles y palabras clave. Sin embargo, este enfoque ignora por completo la "estructura" de las conexiones que se forman como enlace de las personas y al igual que los otros.

La estructura es la próxima gran cosa en análisis de medios sociales: el mismo número de personas que pueden formar diferentes patrones de conexión entre sí.

Las colecciones de colecciones tienen patrones. Ser capaz de reconocer el tipo de red que se encuentre y de entender el tipo de red que se prefiere es el núcleo de un enfoque de próxima generación para análisis de medios sociales.

¿De qué va a hablar en su presentación?

Voy a hablar sobre el análisis de redes maneras puede abrir nuestra comprensión de las redes sociales. La charla es acerca de cómo 'Think Link'. Es un cambio en la manera en que vemos el mundo que se basa en cientos de años de estudio de las redes. Con los conceptos y métodos de las ciencias de red, podemos revelar las estructuras ocultas de los medios de comunicación sociales, organizaciones, mercados y culturas.

La charla se centra en la tarea práctica de la recolección, análisis, visualización y comunicación de información procesable en una colección de conexiones.

Vamos a identificar los factores de influencia, mapear las divisiones entre los sub-grupos y barrios de la corriente de la conversación, y poner de relieve los principales temas, direcciones URL, y hashtags utilizados en general y en cada sub-región de la red.

Se puede saber de Marc, junto con otros expertos en el análisis de datos, en el Social Media y Web Innovation Summit. Ver el programa completo aquí.