Codificación de colores

En informática y teoría de grafos , el término codificación por colores se refiere a una técnica algorítmica que resulta útil para descubrir motivos de redes . Por ejemplo, se puede utilizar para detectar una ruta simple de longitud k en un grafo determinado . El algoritmo de codificación por colores tradicional es probabilístico , pero se puede desaleatorizar sin demasiada sobrecarga en el tiempo de ejecución.

La codificación por colores también se aplica a la detección de ciclos de una longitud dada y, de manera más general, se aplica al problema de isomorfismo de subgrafos (un problema NP-completo ), donde produce algoritmos de tiempo polinomial cuando el patrón de subgrafo que está tratando de detectar tiene un ancho de árbol acotado .

El método de codificación de colores fue propuesto y analizado en 1994 por Noga Alon , Raphael Yuster y Uri Zwick . ^{[1] [2]}

Los siguientes resultados se pueden obtener mediante el método de codificación de colores:

• Para cada constante fija k , si un grafo G = ( V , E ) contiene un ciclo simple de tamaño k , entonces dicho ciclo se puede encontrar en:
  • ${\displaystyle O(|V|^{\omega })}$tiempo esperado, o
  • ${\displaystyle O(|V|^{\omega }\log |V|)}$tiempo del peor caso, donde ω es el exponente de la multiplicación de matrices . ^[3]
• Para cada constante fija k , y cada grafo G = ( V , E ) que esté en cualquier familia de grafos menores cerrados no triviales (por ejemplo, un grafo planar ), si G contiene un ciclo simple de tamaño k , entonces dicho ciclo se puede encontrar en:
  • O ( V ) tiempo esperado, o
  • O ( V log V ) tiempo en el peor de los casos.
• Si un grafo G = ( V , E ) contiene un subgrafo isomorfo a un grafo de ancho de árbol acotado que tiene O (log V ) vértices, entonces dicho subgrafo se puede encontrar en tiempo polinomial .

Para resolver el problema de encontrar un subgrafo en un grafo dado G = ( V , E ) , donde H puede ser un camino, un ciclo o cualquier grafo de ancho de árbol acotado donde , el método de codificación de colores comienza coloreando aleatoriamente cada vértice de G con colores, y luego intenta encontrar una copia colorida de H en G coloreado . Aquí, un grafo es colorido si cada vértice en él está coloreado con un color distinto. Este método funciona repitiendo (1) colorear aleatoriamente un grafo y (2) encontrar una copia colorida del subgrafo objetivo, y eventualmente el subgrafo objetivo se puede encontrar si el proceso se repite una cantidad suficiente de veces.${\displaystyle H=(V_{H},E_{H})}$${\displaystyle |V_{H}|=O(\log |V|)}$${\displaystyle k=|V_{H}|}$

Supongamos que una copia de H en G se vuelve colorida con una probabilidad p distinta de cero . De ello se deduce inmediatamente que si se repite la coloración aleatoria1/pag⁠ veces, entonces se espera que esta copia se vuelva colorida una vez. Nótese que aunque p es pequeño, se muestra que si, p es solo polinomialmente pequeño. Supóngase nuevamente que existe un algoritmo tal que, dado un grafo G y una coloración que asigna cada vértice de G a uno de los k colores, encuentra una copia de la colorida H , si existe, dentro de un tiempo de ejecución O ( r ) . Entonces el tiempo esperado para encontrar una copia de H en G , si existe, es.${\displaystyle |V_{H}|=O(\log |V|)}$${\displaystyle O({\tfrac {r}{p}})}$

A veces también es conveniente utilizar una versión más restringida del colorido. Por ejemplo, en el contexto de la búsqueda de ciclos en grafos planares , es posible desarrollar un algoritmo que encuentre ciclos bien coloreados. En este caso, un ciclo está bien coloreado si sus vértices están coloreados con colores consecutivos.

Un ejemplo sería encontrar un ciclo simple de longitud k en el gráfico G = ( V , E ) .

Al aplicar el método de coloración aleatoria, cada ciclo simple tiene una probabilidad de volverse colorido, ya que existen formas de colorear los k vértices del ciclo, entre los cuales hay ocurrencias coloridas. Luego, se puede usar un algoritmo (descrito a continuación) para encontrar ciclos coloridos en el grafo G coloreado aleatoriamente en el tiempo , donde es la constante de multiplicación de matrices. Por lo tanto, se necesita tiempo total para encontrar un ciclo simple de longitud k en G .${\displaystyle k!/k^{k}>e^{-k}}$${\displaystyle k^{k}}$${\estilo de visualización k!}$${\displaystyle O(V^{\omega })}$${\estilo de visualización \omega}$${\displaystyle e^{k}\cdot O(V^{\omega })}$

El algoritmo de búsqueda de ciclos coloridos funciona encontrando primero todos los pares de vértices en V que están conectados por un camino simple de longitud k − 1 , y luego verificando si los dos vértices en cada par están conectados. Dada una función de coloración c  : V → {1, ..., k } para colorear el grafo G , enumera todas las particiones del conjunto de colores {1, ..., k } en dos subconjuntos C ₁ , C ₂ de tamaño cada uno. Nótese que V puede dividirse en V ₁ y V ₂ en consecuencia, y sea G ₁ y G ₂ los subgrafos inducidos por V ₁ y V ₂ respectivamente. Luego, encuentre recursivamente caminos coloridos de longitud en cada uno de G ₁ y G ₂ . Supongamos que la matriz booleana A ₁ y A ₂ representan la conectividad de cada par de vértices en G ₁ y G ₂ por un camino colorido, respectivamente, y sea B la matriz que describe las relaciones de adyacencia entre los vértices de V ₁ y los de V ₂ , el producto booleano da todos los pares de vértices en V que están conectados por un camino colorido de longitud k − 1 . Por lo tanto, la relación recursiva de las multiplicaciones de matrices es , lo que produce un tiempo de ejecución de . Aunque este algoritmo encuentra solo los puntos finales del camino colorido, se puede incorporar otro algoritmo de Alon y Naor ^{[4] que encuentra los propios caminos coloridos.}${\estilo de visualización k/2}$${\estilo de visualización k/2-1}$$Estilo de visualización A_{1}BA_{2}$${\displaystyle t(k)\leq 2^{k}\cdot t(k/2)}$${\displaystyle 2^{O(k)}\cdot V^{\omega }}$

La desaleatorización de la codificación de colores implica enumerar los posibles colores de un grafo G , de modo que la aleatoriedad de la coloración de G ya no sea necesaria. Para que el subgrafo objetivo H en G sea detectable, la enumeración debe incluir al menos una instancia donde H sea colorida. Para lograr esto, es suficiente enumerar una familia k -perfecta F de funciones hash desde {1, ..., | V |} hasta {1, ..., k } . Por definición, F es k -perfecta si para cada subconjunto S de {1, ..., | V |} donde , existe una función hash h en F tal que h  : S → {1, ..., k } es perfecta . En otras palabras, debe existir una función hash en F que coloree cualquier k vértice dado con k colores distintos.${\displaystyle |S|=k}$

Existen varios enfoques para construir dicha familia hash k -perfecta:

1. La mejor construcción explícita es la de Moni Naor , Leonard J. Schulman y Aravind Srinivasan, ^[5] donde se puede obtener una familia de tamaño . Esta construcción no requiere que el subgrafo de destino exista en el problema de búsqueda del subgrafo original.${\displaystyle e^{k}k^{O(\log k)}\log |V|}$
2. Otra construcción explícita de Jeanette P. Schmidt y Alan Siegel ^[6] produce una familia de tamaño .${\displaystyle 2^{O(k)}\log ^{2}|V|}$
3. Otra construcción que aparece en el artículo original de Noga Alon et al. ^[2] se puede obtener construyendo primero una familia k -perfecta que mapea {1, ..., | V |} a {1, ..., k ² }, seguida por la construcción de otra familia k -perfecta que mapea {1, ..., k ² } a {1, ..., k }. En el primer paso, es posible construir una familia de este tipo con 2 n log k bits aleatorios que son casi 2log k -independientes, ^{[7] [8]} y el espacio muestral necesario para generar esos bits aleatorios puede ser tan pequeño como . En el segundo paso, Jeanette P. Schmidt y Alan Siegel ^[6] han demostrado que el tamaño de dicha familia k -perfecta puede ser . En consecuencia, al componer las familias k -perfectas de ambos pasos, se puede obtener una familia k -perfecta de tamaño que mapea de {1, ..., | V |} a {1, ..., k } .${\displaystyle k^{O(1)}\log |V|}$${\displaystyle 2^{O(k)}}$${\displaystyle 2^{O(k)}\log |V|}$

En el caso de la desaleatoriedad de la coloración adecuada, donde cada vértice del subgrafo se colorea consecutivamente, se necesita una familia k -perfecta de funciones hash desde {1, ..., | V |} hasta {1, ..., k !} . Se puede construir una familia k -perfecta suficiente que mapee desde {1, ..., | V |} hasta {1, ..., k ^k } de una manera similar al enfoque 3 anterior (el primer paso). En particular, se hace utilizando nk log k bits aleatorios que son casi k log k independientes, y el tamaño de la familia k -perfecta resultante será .${\displaystyle k^{O(k)}\log |V|}$

El método de desaleatorización del código de colores se puede paralelizar fácilmente, lo que produce algoritmos NC eficientes .

Recientemente, la codificación por colores ha atraído mucha atención en el campo de la bioinformática. Un ejemplo es la detección de vías de señalización en redes de interacción proteína-proteína (PPI). Otro ejemplo es el descubrimiento y recuento del número de motivos en redes PPI. El estudio tanto de las vías de señalización como de los motivos permite una comprensión más profunda de las similitudes y diferencias de muchas funciones, procesos y estructuras biológicas entre los organismos.

Debido a la enorme cantidad de datos genéticos que se pueden recopilar, la búsqueda de vías o motivos puede llevar mucho tiempo. Sin embargo, al explotar el método de codificación por colores, los motivos o vías de señalización con vértices en una red G con n vértices se pueden encontrar de manera muy eficiente en tiempo polinomial. Por lo tanto, esto nos permite explorar estructuras más complejas o más grandes en redes PPI.${\displaystyle k=O(\log n)}$

• Alon, N.; Dao, P.; Hajirasouliha, I.; Hormozdiari, F.; Sahinalp, SC (2008). "Recuento y descubrimiento de motivos de redes biomoleculares mediante codificación de colores". Bioinformática . 24 (13): i241–i249. doi :10.1093/bioinformatics/btn163. PMC  2718641 . PMID  18586721.
• Hüffner, F.; Wernicke, S.; Zichner, T. (2008). "Ingeniería de algoritmos para codificación de colores con aplicaciones para la detección de vías de señalización". Algorithmica . 52 (2): 114–132. CiteSeerX  10.1.1.68.9469 . doi :10.1007/s00453-007-9008-7. S2CID  81069.