Codificación por colores

En informática y teoría de grafos , el término codificación por colores se refiere a una técnica algorítmica útil para descubrir patrones en redes . Por ejemplo, se puede usar para detectar un camino simple de longitud k en un grafo dado . El algoritmo tradicional de codificación por colores es probabilístico , pero se puede desaleatorizar sin aumentar significativamente 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 del isomorfismo de subgrafos (un problema NP-completo ), donde produce algoritmos de tiempo polinomial cuando el patrón de subgrafo que intenta detectar tiene un ancho de árbol acotado .

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

Mediante el método de codificación por colores se pueden obtener los siguientes resultados:

• Para cada constante fija k , si un gráfico G = ( V , E ) contiene un ciclo simple de tamaño k , entonces dicho ciclo se puede encontrar en:
  • ${\displaystyle O(|V|^{\omega })}$tiempo previsto o
  • ${\displaystyle O(|V|^{\omega }\log |V|)}$tiempo en el peor de los casos, donde ω es el exponente de la multiplicación de matrices . ^{[ 3 ]}
• Para cada constante fija k y cada grafo G = ( V , E ) que pertenece a cualquier familia de grafos cerrados menores 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${\displaystyle H=(V_{H},E_{H})}$en un grafo dado G = ( V , E ) , donde H puede ser un camino, un ciclo o cualquier grafo de ancho de árbol acotado donde${\displaystyle |V_{H}|=O(\log |V|)}$, el método de codificación por colores comienza coloreando aleatoriamente cada vértice de G con${\displaystyle k=|V_{H}|}$Se asignan colores a H y luego se intenta encontrar una copia colorida de H en G coloreado . Un grafo es colorido si cada uno de sus vértices tiene un color distinto. Este método funciona repitiendo (1) la coloración aleatoria de un grafo y (2) la búsqueda de una copia colorida del subgrafo objetivo. Si el proceso se repite suficientes veces, se puede encontrar el subgrafo objetivo.

Supongamos que una copia de H en G se vuelve colorida con alguna probabilidad no nula p . Inmediatamente se deduce que si la coloración aleatoria se repite 1 / p veces , entonces se espera que esta copia se vuelva colorida una vez. Nótese que aunque p es pequeño, se demuestra que si${\displaystyle |V_{H}|=O(\log |V|)}$, p es solo polinómicamente pequeño. Supongamos de nuevo que existe un algoritmo tal que, dado un grafo G y una coloración que asigna a cada vértice de G uno de los k colores, encuentra una copia de H coloreada , si existe, en algún tiempo de ejecución O ( r ) . Entonces, el tiempo esperado para encontrar una copia de H en G , si existe, es${\displaystyle O({\tfrac {r}{p}})}$.

En ocasiones, también es conveniente utilizar una versión más restringida del concepto de coloración. 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.

La desaleatorización de la codificación por colores implica enumerar las posibles coloraciones 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 colorido. Para lograr esto, enumerar una familia k -perfecta F de funciones hash de {1, ..., | V |} a {1, ..., k } es suficiente. Por definición, F es k -perfecta si para cada subconjunto S de {1, ..., | V |} donde${\displaystyle |S|=k}$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 conjunto de k vértices con k colores distintos.

Existen varios enfoques para construir una familia de funciones hash k -perfecta de este tipo:

1. La mejor construcción explícita es la de Moni Naor , Leonard J. Schulman y Aravind Srinivasan , ^{[ 5 ]} donde una familia de tamaño${\displaystyle e^{k}k^{O(\log k)}\log |V|}$se puede obtener. Esta construcción no requiere que el subgrafo objetivo exista en el problema original de búsqueda de subgrafos.
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 de la construcción de otra familia k -perfecta que mapea {1, ..., k ² } a {1, ..., k }. En el primer paso, es posible construir dicha familia 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${\displaystyle k^{O(1)}\log |V|}$^{. En el segundo paso, Jeanette P. Schmidt y Alan Siegel [ 6 ]} demostraron que el tamaño de dicha familia k -perfecta puede ser${\displaystyle 2^{O(k)}}$. En consecuencia, al componer las familias k -perfectas de ambos pasos, se obtiene una familia k -perfecta de tamaño${\displaystyle 2^{O(k)}\log |V|}$que mapea de {1, ..., | V |} a {1, ..., k } se puede obtener.

En el caso de la coloración de pozos de desaleatorización, donde cada vértice del subgrafo se colorea consecutivamente, se necesita una familia k -perfecta de funciones hash de {1, ..., | V |} a {1, ..., k !} . Una familia k -perfecta suficiente que mapee de {1, ..., | V |} a {1, ..., k ^k } se puede construir de una manera similar al enfoque 3 anterior (el primer paso). En particular, se hace usando 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|}$.

La eliminación de la aleatorización en el método de codificación por colores se puede paralelizar fácilmente, lo que da como resultado algoritmos NC eficientes.

Recientemente, la codificación por colores ha captado gran 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 de motivos en dichas redes. 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 entre numerosas funciones, procesos y estructuras biológicas en los organismos.

Debido a la enorme cantidad de datos genéticos que se pueden recopilar, la búsqueda de vías o motivos puede ser muy laboriosa. Sin embargo, al explotar el método de codificación por colores, los motivos o vías de señalización con${\displaystyle k=O(\log n)}$Los vértices de una red G con n vértices se pueden encontrar de forma muy eficiente en tiempo polinomial. Esto nos permite explorar estructuras más complejas o de mayor tamaño en redes de interacción proteína-proteína.

• Alon, N.; Dao, P.; Hajirasouliha, I.; Hormozdiari, F.; Sahinalp, SC (2008). "Recuento y descubrimiento de motivos de redes biomoleculares mediante codificación por colores" . Bioinformatics . 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 por colores con aplicaciones a 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 .