Hispanopedia Wiki
Articulo de referencia

Análisis de gráficos de potencia

En biología computacional , el análisis de grafos de potencia es un método para el análisis y la representación de redes complejas . El análisis de grafos de potencia consiste e...

Hispanopedia WikiContenido en espanolLectura gratuita

En biología computacional , el análisis de grafos de potencia es un método para el análisis y la representación de redes complejas . El análisis de grafos de potencia consiste en el cálculo, el análisis y la representación visual de un grafo de potencia a partir de un grafo ( redes ).

El análisis de gráficos de potencia puede considerarse un algoritmo de compresión sin pérdidas para gráficos. [ 1 ] Extiende la sintaxis de gráficos con representaciones de cliques , bicliques y estrellas . Se han obtenido niveles de compresión de hasta el 95 % para redes biológicas complejas .

Los hipergrafos son una generalización de los grafos en la que las aristas no son solo pares de nodos , sino n-tuplas arbitrarias . Los grafos de potencia no son otra generalización de los grafos, sino una representación novedosa que propone un cambio del lenguaje de "nodos y aristas" a uno que utiliza cliques, bicliques y estrellas como primitivas.

Gráficos de potencia

Los motivos primitivos utilizados para el análisis de gráficos de potencia y su correspondiente representación diagramática: biclique, clique y estrella.

Representación gráfica

Los gráficos se dibujan con círculos o puntos que representan nodos y líneas que conectan pares de nodos y que representan aristas . Los gráficos de potencia extienden la sintaxis de los gráficos con nodos de potencia , que se dibujan como un círculo que encierra nodos u otros nodos de potencia , y aristas de potencia , que son líneas entre nodos de potencia.

Las bicliques son dos conjuntos de nodos con una arista entre cada miembro de un conjunto y cada miembro del otro. En un grafo de potencia, una biclique se representa como una arista entre dos nodos de potencia.

Las camarillas son un conjunto de nodos con una arista entre cada par de nodos. En un grafo de potencia, una camarilla está representada por un nodo de potencia con un bucle .

Las estrellas son conjuntos de nodos con una arista entre cada miembro de ese conjunto y un único nodo fuera del conjunto. En un grafo de potencia, una estrella se representa mediante una arista de potencia entre un nodo regular y un nodo de potencia.

Definición formal

Dado un gráficoGRAMO=(V,mi){\displaystyle G={\bigl (}{V,E}{\bigr )}}dóndeV={v0,…,vnorte}{\displaystyle V={\bigl \{}v_{0},\dots,v_{n}{\bigr \}}}es el conjunto de nodos ymi⊆V×V{\displaystyle E\subseteq V\times V}es el conjunto de aristas, un grafo de potenciaGRAMO′=(V′,mi′){\displaystyle G'={\bigl (}{V',E'}{\bigr )}}es un gráfico definido en el conjunto potenciaV′⊆PAG(V){\displaystyle V'\subseteq {\mathcal {P}}{\bigl (}V{\bigr )}}de nodos de energía conectados entre sí por aristas de energía :mi′⊆V′×V′{\displaystyle E'\subseteq V'\times V'}Por lo tanto, los grafos de potencia se definen tanto en el conjunto de potencia de los nodos como en el conjunto de potencia de las aristas del grafo.GRAMO{\displaystyle G}.

La semántica de los grafos de potencia es la siguiente: si dos nodos de potencia están conectados por una arista de potencia, esto significa que todos los nodos del primer nodo de potencia están conectados a todos los nodos del segundo nodo de potencia. De manera similar, si un nodo de potencia está conectado a sí mismo por una arista de potencia, esto significa que todos los nodos dentro del nodo de potencia están conectados entre sí por aristas.

Se requieren las dos condiciones siguientes:

  • Condición de jerarquía de nodos de poder: Cualquier par de nodos de poder son disjuntos, o uno está incluido en el otro.
  • Condición de disyunción de aristas de potencia: Existe una aplicación sobreyectiva de las aristas del grafo original a las aristas de potencia.

Analogía con el análisis de Fourier

El análisis de Fourier de una función puede verse como una reescritura de la función en términos de funciones armónicas en lugar de t↦incógnita{\displaystyle t\mapsto x}pares. Esta transformación cambia el punto de vista del dominio del tiempo al dominio de la frecuencia y permite muchas aplicaciones interesantes en el análisis de señales , la compresión de datos y el filtrado. De manera similar, el análisis de grafos de potencia es una reescritura o descomposición de una red usando bicliques, cliques y estrellas como elementos primitivos (al igual que las funciones armónicas para el análisis de Fourier). Se puede usar para analizar, comprimir y filtrar redes. Sin embargo, hay varias diferencias clave. Primero, en el análisis de Fourier los dos espacios (dominios del tiempo y de la frecuencia) son el mismo espacio de funciones , pero en sentido estricto, los grafos de potencia no son grafos. Segundo, no hay un único grafo de potencia que represente un grafo dado. Sin embargo, una clase muy interesante de grafos de potencia son los grafos de potencia mínimos que tienen la menor cantidad de aristas y nodos de potencia necesarios para representar un grafo dado.

Gráficos de potencia mínima

Dos gráficas de potencia diferentes que representan la misma gráfica.

En general, no existe un grafo de potencia mínima único para un grafo dado. En este ejemplo (derecha), un grafo de cuatro nodos y cinco aristas admite dos grafos de potencia mínima, cada uno con dos aristas de potencia. La principal diferencia entre estos dos grafos de potencia mínima radica en el mayor nivel de anidamiento del segundo grafo de potencia, así como en la pérdida de simetría con respecto al grafo subyacente. La pérdida de simetría solo representa un problema en ejemplos sencillos, ya que las redes complejas rara vez presentan tales simetrías. Además, se puede minimizar el nivel de anidamiento, pero incluso en ese caso, en general no existe un grafo de potencia mínima único con un nivel de anidamiento mínimo.

Algoritmo voraz de gráfico de potencia

El algoritmo voraz de grafos de potencia se basa en dos pasos sencillos para realizar la descomposición:

El primer paso consiste en identificar posibles nodos de potencia mediante una agrupación jerárquica de los nodos de la red, basada en la similitud de sus nodos vecinos. La similitud entre dos conjuntos de vecinos se considera el índice de Jaccard de dichos conjuntos.

El segundo paso realiza una búsqueda voraz de posibles aristas de poder entre nodos candidatos. Las aristas de poder que abstraen la mayor cantidad de aristas en la red original se agregan primero al grafo de poder. De esta manera, las bicliques, cliques y estrellas se reemplazan incrementalmente con aristas de poder, hasta que todas las aristas simples restantes también se agregan. Los nodos candidatos de poder que no son el punto final de ninguna arista de poder se ignoran.

descomposición modular

La descomposición modular permite calcular un grafo de potencia mediante los módulos fuertes de dicha descomposición. Los módulos en la descomposición modular son grupos de nodos en un grafo que tienen vecinos idénticos. Un módulo fuerte es aquel que no se superpone con otro. Sin embargo, en redes complejas, los módulos fuertes son más la excepción que la regla. Por lo tanto, los grafos de potencia obtenidos mediante la descomposición modular distan mucho de ser mínimos. La principal diferencia entre la descomposición modular y el análisis de grafos de potencia radica en que este último se centra en descomponer grafos no solo mediante módulos de nodos, sino también mediante módulos de aristas (cliques, bicliques). De hecho, el análisis de grafos de potencia puede considerarse como una agrupación simultánea y sin pérdida de información tanto de nodos como de aristas.

Aplicaciones

Redes biológicas

Se ha demostrado que el análisis de gráficos de potencia es útil para el análisis de varios tipos de redes biológicas, como redes de interacción proteína-proteína , [ 2 ] motivos de unión dominio-péptido, redes de regulación génica [ 3 ] y redes de homología/paralogía. Además, recientemente se ha visualizado y analizado una red de pares significativos de enfermedad-rasgo [ 4 ] mediante gráficos de potencia.

La compresión de red, una nueva medida derivada de los gráficos de potencia, se ha propuesto como una medida de calidad para las redes de interacción de proteínas. [ 5 ]

Reposicionamiento de fármacos

Los gráficos de potencia también se han aplicado al análisis de redes fármaco-diana-enfermedad [ 6 ] para el reposicionamiento de fármacos .

Redes sociales

Los gráficos de poder se han aplicado a datos a gran escala en redes sociales, para minería de comunidades [ 7 ] o para modelar tipos de autores. [ 8 ]

Véase también

Referencias

  1. ↑ Matthias Reimann; Loïc Royer; Simone Daminelli; Michael Schroeder (2015). Matthias Dehmer; Frank Emmert-Streib; Stefan Pickl (eds.). Teoría de redes computacionales: fundamentos teóricos y aplicaciones . Serie de biología cuantitativa y de redes. Vol. 5. Wiley-Blackwell. ISBN  978-3-527-33724-8.
  2. ↑ Royer, Loïc; Reimann, Matthias; Andreopoulos, Bill; Schroeder, Michael (11 de julio de 2008). Berg, Johannes (ed.). " Desentrañando redes de proteínas con análisis de grafos de potencia" . PLOS Computational Biology . 4 (7) e1000108. Bibcode : 2008PLSCB...4E0108R . doi : 10.1371/journal.pcbi.1000108 . PMC 2424176. PMID 18617988 .  
  3. ↑ Martina Maisel; Hans-Jörg Habisch; Loïc Royer; Alexander Herr; Javorina Milosevic; Andreas Hermann; Stefan Liebau; Rolf Brenner; Johannes Schwarz; Michael Schroeder; Alexander Storch (15 de octubre de 2010). "El perfil de expresión genómica y el análisis de redes funcionales tras la conversión neuroectodérmica de células madre mesenquimales humanas sugieren que HIF-1 y miR-124a son reguladores importantes". Experimental Cell Research . 316 (17): 2760–78 . doi : 10.1016/j.yexcr.2010.06.012 . PMID 20599952 . 
  4. ↑ Li, Li; Ruau, David J.; Patel, Chirag J.; Weber, Susan C.; Chen, Rong; Tatonetti, Nicholas P.; Dudley, Joel T.; Butte, Atul J. (30 de abril de 2014). "Factores de riesgo de enfermedad identificados a través de la arquitectura genética compartida y los registros médicos electrónicos" . Sci . Transl. Med . 6 (234): 234ra57. doi : 10.1126/scitranslmed.3007191 . PMC 4323098. PMID 24786325 .  
  5. ↑ Royer, Loïc; Reimann, Matthias; Stewart, Francis A.; Schroeder, Michael (18 de junio de 2012). " Compresión de redes como medida de calidad para redes de interacción de proteínas" . PLOS ONE . 7 (6) e35729. Bibcode : 2012PLoSO...735729R . doi : 10.1371/journal.pone.0035729 . PMC 3377704. PMID 22719828 .  
  6. ↑ Daminelli, Simone; Haupt, Joachim V.; Reimann, Matthias; Schroeder, Michael (26 de abril de 2012). "Reposicionamiento de fármacos a través de bicliques incompletos en una red integrada fármaco-diana-enfermedad" . Integrative Biology . 4 (7): 778–88 . doi : 10.1039/C2IB00154C . PMID 22538435 . 
  7. ↑ George Tsatsaronis; Matthias Reimann; Iraklis Varlamis; Orestis Gkorgkas; Kjetil Nørvåg (2011). "Detección eficiente de comunidades mediante análisis de grafos de potencia". Actas del 9.º taller sobre recuperación de información a gran escala y distribuida . Lsds-Ir '11. págs. 21–26 . doi : 10.1145/2064730.2064738 . ISBN  978-1-4503-0959-2. S2CID 10224386 . 
  8. ↑ George Tsatsaronis; Iraklis Varlamis; Sunna Torge; Matthias Reimann; Kjetil Nørvåg; Michael Schroeder; Matthias Zschunke (2011). "¿Cómo convertirse en líder de grupo? o Modelado de tipos de autores basado en minería de grafos". Investigación y tecnología avanzada para bibliotecas digitales: Conferencia internacional sobre teoría y práctica de bibliotecas digitales, TPDL . Lecture Notes in Computer Science. Vol. 6966. SpringerLink. pp. 15–26 . CiteSeerX 10.1.1.299.714 . doi : 10.1007/978-3-642-24469-8_4 . ISBN    978-3-642-24468-1.
  • Herramientas de análisis de gráficos de potencia (CyOog v2.8.2) y ejemplos de aplicaciones
  • Análisis de gráficos de potencia con CyOog v2.6