El problema de enumeración máxima de camarillas: algoritmos, aplicaciones e implementaciones

Utilizando el algoritmo de enumeración máxima seminal de camarillas debido a Bron y Kerbosch como punto de referencia, diseñamos, implementamos y probamos exhaustivamente tres mejoras algorítmicas, la última basada en observaciones sobre la naturaleza de los gráficos producidos por datos transcriptómicos. Además de describir estas mejoras, describiremos nuestra herramienta existente para encontrar una camarilla máxima única, basada en la teoría de la manejabilidad de parámetros fijos (FPT) . Esta herramienta es esencial para las tres mejoras, ya que las dos primeras se basan en el conocimiento del tamaño máximo de la camarilla, y la última utiliza la herramienta de búsqueda de camarillas máximas como subrutina. Todos los códigos están escritos en C / C++ y compilados en Linux. Para las pruebas, utilizamos 100 gráficos derivados de 25 conjuntos de datos diferentes que están disponibles públicamente en GEO. Nos concentramos en los datos transcriptómicos, dada su abundancia, y evitamos los datos sintéticos, habiendo aprendido hace mucho tiempo que los algoritmos efectivos para uno tienen poca relación con el otro. (Las coincidencias patológicas observadas en la cobertura de vértices se pueden extender a la camarilla, pero del mismo modo, también son, por supuesto, enormemente irrelevantes para los datos reales.) En un esfuerzo por mejorar el rendimiento, analizamos la estructura de los gráficos transcriptómicos y exploramos la noción de cubiertas máximas de camarillas y conjuntos de vértices esenciales. De hecho, encontramos que con el preprocesamiento correcto somos capaces de adaptar algoritmos a los tipos de datos que encontramos habitualmente, y que ahora podemos resolver instancias que anteriormente se consideraban inexpugnables.

Algoritmos

En las siguientes secciones, describimos cada uno de los algoritmos de MCE que implementamos y probamos. El primero es el algoritmo de Bron y Kerbosch, que llamamos Backtracking básico y usamos como punto de referencia. Dado que todas nuestras mejoras posteriores hacen uso de un algoritmo que encuentra una única camarilla máxima, a continuación describimos nuestra herramienta existente, llamada Buscador de camarillas máximas (MCF), que hace precisamente eso. A continuación, modificamos el algoritmo de Retroceso básico para aprovechar el hecho de que solo queremos encontrar las camarillas máximas y podemos calcular rápidamente el tamaño máximo de camarilla. Llamamos a este enfoque Retroceso inteligente, ya que retorna activamente temprano desde ramas que no conducirán a una camarilla máxima. A continuación, modificamos MCF para enumerar todas las camarillas máximas, un enfoque que llamamos Camarilla Máxima Parametrizada, o MC parametrizado. En cierto sentido, este es otro enfoque de retroceso que va aún más allá para explotar el hecho de que solo queremos encontrar camarillas máximas. Finalmente, a partir de observaciones sobre las propiedades de los gráficos biológicos, presentamos los conceptos de cubiertas de camarilla máxima y conjuntos de vértices esenciales, y los aplicamos para mejorar significativamente el tiempo de ejecución de los algoritmos de retroceso.

Backtracking básico

La publicación seminal maximal clique describe dos algoritmos. Se proporciona una presentación detallada de la segunda, que es una versión mejorada de la primera. Es este segundo método, más eficiente, el que implementamos y probamos. Lo llamaremos aquí Retroceso básico. Todas las camarillas máximas se enumeran con un recorrido de árbol de búsqueda en profundidad. Las estructuras de datos primarias empleadas son tres conjuntos globales de vértices: COMPSUB, CANDIDATOS y NO. COMPSUB contiene los vértices de la camarilla actual, y está inicialmente vacío. CANDIDATES contiene vértices inexplorados que pueden extender la camarilla actual, e inicialmente contiene todos los vértices del gráfico. NO contiene vértices explorados que no pueden extender la camarilla actual, y está inicialmente vacío. Cada llamada recursiva realiza tres pasos:

• Seleccione un vértice v en CANDIDATOS y muévalo a COMPSUB.

• Elimine todos los vértices no adyacentes a v de ambos CANDIDATOS y NO. En este punto, si ambos CANDIDATOS y NO están vacíos, entonces COMPSUB es una camarilla máxima. Si es así, envíe COMPSUB como un cique máximo y continúe con el siguiente paso. Si no, llame recursivamente al paso anterior.

• Mueva v de COMPSUB a NO.

Tenga en cuenta que NO se usa para evitar generar camarillas máximas duplicadas. El árbol de búsqueda se puede podar terminando una rama temprano si algún vértice de NOT está conectado a todos los vértices de CANDIDATOS.

Los vértices se seleccionan de manera que se produzca esta poda lo antes posible. Omitimos los detalles ya que no son pertinentes para nuestras modificaciones del algoritmo.

Los requisitos de almacenamiento de Backtracking básico son relativamente modestos. No es necesario conservar información sobre camarillas máximas anteriores. En las mejoras que probaremos, nos centramos en la velocidad, pero también mejoramos el uso de la memoria. Por lo tanto, tales limitaciones no son en ningún caso prohibitivas para ninguno de nuestros métodos probados. Sin embargo, en algunos entornos, la utilización de la memoria puede ser extrema. Remitimos al lector interesado .

Nuestra implementación de Backtracking básico sirve como un punto de referencia inicial sobre el que ahora podemos intentar mejorar.

Encontrar un solo grupo grupal máximo

Utilizamos el término Buscador de grupos grupales máximos (MCF) para denotar el software que hemos implementado y refinado para encontrar un grupo grupal individual de mayor tamaño . MCF emplea un conjunto de reglas de preprocesamiento junto con una estrategia de ramificación que refleja el conocido enfoque FPT para la cobertura de vértices . Primero invoca a una heurística codiciosa simple para encontrar rápidamente una camarilla razonablemente grande. Esta camarilla se utiliza para el preprocesamiento, ya que pone un límite inferior en el tamaño máximo de camarilla. La heurística funciona eligiendo el vértice de grado más alto, v, y luego eligiendo el vecino de grado más alto de v. Estos dos vértices forman una camarilla inicial C, que luego se extiende iterativamente eligiendo el vértice de grado más alto adyacente a todo C. En cada iteración, se elimina cualquier vértice que no sea adyacente a todo C. El proceso continúa hasta que no existan más vértices fuera de C. Dado que |C| es un límite inferior en el tamaño máximo de camarilla, todos los vértices con grado menor que |C – 1 / pueden eliminarse permanentemente del gráfico original. A continuación, todos los vértices con grado n – 1 se eliminan temporalmente del gráfico, pero se mantienen en una lista ya que deben formar parte de cualquier camarilla máxima. MCF explota una nueva forma de preprocesamiento de color, utilizada anteriormente para guiar la ramificación. Esta forma de preprocesamiento intenta reducir el gráfico de la siguiente manera. Dado un límite inferior conocido k del tamaño de la camarilla máxima, para cada vértice v aplicamos una coloración rápida y codiciosa a v y sus vecinos. Si estos vértices se pueden colorear con menos de k colores, entonces v no puede ser parte de una camarilla máxima y se elimina del gráfico. Una vez que el grafo se reduce, MCF usa la ramificación recursiva estándar en vértices, donde cada rama asume que el vértice está o no en la camarilla máxima.

Retroceso inteligente

Dada la efectividad relativa con la que podemos encontrar una sola camarilla máxima, parece lógico considerar si el conocimiento del tamaño de esa camarilla puede ser útil para enumerar todas las camarillas máximas. Como resultado, el conocimiento del tamaño máximo de camarilla k conduce a un cambio pequeño y directo en el algoritmo de Retroceso Básico. Específicamente, en cada nodo del árbol de búsqueda comprobamos si hay menos de k vértices en la unión de COMPSUB y CANDIDATOS. Si es así, esa rama no puede llevar a una camarilla de tamaño k, y así regresamos. Véase la Figura 2. Si bien la modificación puede parecer menor, la poda resultante del árbol de búsqueda puede conducir a una reducción sustancial en el espacio de búsqueda. Además de este pequeño cambio en la ramificación, aplicamos el preprocesamiento de color como se describió anteriormente para reducir el gráfico antes de enviarlo al algoritmo de retroceso mejorado. Preprocesamiento de color combinado con el cambio de ramificación menor que llamamos Retroceso inteligente.

Enumeración paramaterizada

Dado que MCF emplea una estrategia de ramificación de vértices, investigamos si se podría modificar para enumerar no solo una, sino todas las camarillas máximas. Resulta que MCF, también, se presta a una modificación directa que resulta en la enumeración de todas las camarillas máximas. La modificación es simplemente mantener una lista global de todas las camarillas de mayor tamaño encontradas hasta el momento. Cada vez que se encuentra una camarilla máxima más grande, la lista se vacía y se actualiza para contener solo la nueva camarilla máxima. Cuando se ha agotado el espacio de búsqueda, se genera la lista de camarillas máximas.

Sin embargo, debemos tener especial cuidado de tener en cuenta que ciertas reglas de preprocesamiento utilizadas durante el entrelazado ya no son válidas. Considere, por ejemplo, la eliminación de un vértice de hoja. El análogo de la camarilla es encontrar un vértice con grado n-2 y eliminar a su no vecino solitario. Esta regla asume claramente que solo se desea una camarilla máxima, porque ignora cualquier camarilla que dependa del vértice descartado. Por lo tanto, esta regla de preprocesamiento en particular debe omitirse una vez que haya comenzado la ramificación.

Cubiertas de camarilla máxima

Si vemos MCF como una subrutina de caja negra que se puede llamar repetidamente, se puede usar en un algoritmo codicioso simple para calcular un conjunto máximo de camarillas máximas disjuntas. Simplemente calculamos una camarilla máxima, la eliminamos del gráfico e iteramos hasta que el tamaño de una camarilla máxima disminuya. Para explorar las ventajas de calcular tal conjunto, introducimos la siguiente noción:

Definición 1 Una cubierta de camarilla máxima de G = (V, E) es un conjunto V’ V V con la propiedad de que cada camarilla máxima de G contiene algún vértice en la cubierta.

La unión de todos los vértices contenidos en un conjunto máximo de camarillas máximas disjuntas es, por supuesto, una cubierta de camarilla máxima (en adelante MCC), porque todas las camarillas máximas deben superponerse con dicho conjunto. Esto conduce a un algoritmo de reducción útil. Cualquier vértice que no sea adyacente a al menos un miembro de un CCM no puede estar en una camarilla máxima, y por lo tanto puede eliminarse.

En la práctica, encontramos que la aplicación de MCC antes de los algoritmos de retroceso anteriores solo produce una mejora marginal. El concepto de MCC, sin embargo, conduce a un enfoque mucho más poderoso basado en vértices individuales. Dado que cualquier mejora realizada por MCC está subsumida por el siguiente enfoque, no probamos MCC por sí mismo.

Conjuntos de vértices esenciales

Nuestra investigación del algoritmo MCC reveló que normalmente no reduce el tamaño del gráfico más que las reglas de preprocesamiento ya incorporadas en MCF. Por ejemplo, MCF ya encuentra rápidamente un límite inferior en el tamaño máximo de camarilla y elimina cualquier vértice con grado inferior a este límite. Sin embargo, tras un examen más detenido, encontramos que para 74 de los 75 gráficos que probamos inicialmente para la versión de conferencia de este documento, solo se necesitaba una camarilla en un CCM. Es decir, una camarilla máxima cubría todas las demás camarillas máximas. Y en nuestro banco de pruebas actual de 100 gráficos, en todos los casos, una sola camarilla máxima es suficiente para un MCC. De hecho, esto coincide estrechamente con nuestra experiencia, en la que típicamente vemos una gran superposición entre grandes camarillas en los gráficos transcriptómicos que encontramos de forma regular. Sobre la base de esta observación, ahora perfeccionaremos el concepto de MCC. En lugar de cubrir las camarillas máximas con camarillas, cubrimos las camarillas máximas con vértices individuales.

Definimos un vértice esencial como uno que está contenido en cada camarilla máxima. Por supuesto, es posible que un gráfico dado no tenga tal vértice, incluso cuando contiene muchas camarillas máximas superpuestas. Pero las pruebas empíricas de grandes gráficos transcriptómicos muestran que un número abrumador contiene numerosos vértices esenciales. Y para reducir el gráfico, incluso uno bastará. Un vértice esencial tiene el potencial de ser extremadamente útil, ya que nos permite eliminar a todos sus no vecinos. Empleamos la siguiente observación: para cualquier grafo G, ω(G) >ω(G/v) si y solo si v cubre todas las camarillas máximas, donde ω(G) es el tamaño máximo de camarilla de G.

Definimos un conjunto esencial como el conjunto de todos los vértices esenciales. El algoritmo de Conjuntos esenciales, como se describe en la Figura 3, encuentra todos los vértices esenciales en un gráfico. A continuación, reduce el gráfico eliminando, para cada vértice esencial, todos los no vecinos de ese vértice. El algoritmo ES se puede ejecutar en conjunto con cualquiera de los algoritmos de MCE de retroceso, o incluso antes de cualquier algoritmo que realice MCE por cualquier método, ya que su salida es un gráfico reducido que aún contiene todas las camarillas máximas del gráfico original. Como muestran nuestras pruebas, la mejora del tiempo de ejecución que ofrece el algoritmo ES puede ser dramática.

Implementación

Implementamos todos los algoritmos en C o C++. El código fue compilado usando el compilador GCC 4.4.3 en el sistema operativo Ubuntu Linux versión 10.04.2, así como el compilador GCC 3.3.5 bajo Debian Linux versión 3.1. Todos los tiempos se llevaron a cabo en este último entorno Debian en nodos dedicados de un clúster para garantizar que no afectaran los tiempos de los procesos concurrentes. Cada nodo tenía un procesador Intel Xeon de doble núcleo que se ejecutaba a 3,20 GHz y 4 GB de memoria principal.

Testing

En la versión de conferencia de este documento, utilizamos tres conjuntos de datos diferentes con 25 umbrales cada uno para derivar un total de 75 gráficos en los que probar nuestras mejoras algorítmicas. Si bien estos gráficos bastaban sin duda como prueba inicial de concepto, se podían plantear dos preocupaciones al respecto. En primer lugar, se podría argumentar que tres conjuntos de datos no son un tamaño de muestra lo suficientemente grande como para proporcionar un verdadero sentido de la naturaleza general de los datos transcriptómicos o la efectividad general de una mejora algorítmica en dichos datos, a pesar del gran número de umbrales. Y en segundo lugar, dado que los tres conjuntos de datos son de propiedad privada y no están a disposición del público, los resultados no fueron tan fácilmente reproducibles como lo habrían sido de otro modo. La obtención de versiones no identificadas, aunque factible, era un obstáculo innecesario para la reproducibilidad.

Abordamos estas preocupaciones creando un nuevo conjunto de gráficos transcriptómicos en los que probar nuestras mejoras algorítmicas. El conjunto consta de gráficos derivados de 25 conjuntos de datos obtenidos del Omnibus de Expresión Génica (GEO) , un repositorio de acceso público. Para cada conjunto de datos, se crearon gráficos en cuatro umbrales diferentes, para un total de 100 gráficos. Los conjuntos de datos se seleccionaron para proporcionar un muestreo razonablemente diverso de tipo experimental, especie y tipo de chip de microarray de ARNm. Cubren 8 especies diferentes y una serie de condiciones experimentales diferentes, como series temporales, cepas, dosis y pacientes. Dado que nuestros gráficos se derivan de valores de correlación de umbral, excluimos de consideración cualquier conjunto de datos con menos de 12 condiciones. Las correlaciones de umbral calculadas utilizando tan pocas condiciones pueden producir tasas inaceptablemente grandes de falsos positivos y falsos negativos. El número de condiciones varía de un mínimo de 12 a un máximo de 153. Nueve de los conjuntos de datos no se habían transformado en registros, en cuyo caso se realizó la transformación de registros. Cuatro de los conjuntos de datos contenían valores faltantes; en estos casos, utilizamos valores de correlación p en lugar de correlaciones para el umbral. Consulte la Tabla 1 para obtener una lista de los conjuntos de datos GEOGRÁFICOS utilizados para las pruebas.

A partir de los datos de expresión, primero construimos gráficos ponderados en los que los vértices representaban sondas y los pesos de aristas eran coeficientes de correlación de Pearson calculados en condiciones experimentales. Luego convertimos los gráficos ponderados en gráficos no ponderados conservando solo aquellos bordes cuyos pesos estaban en o por encima de algún umbral elegido, t. Para cada conjunto de datos, elegimos cuatro valores para t.Todos los valores de tamaño/densidad estaban dentro del espectro que normalmente se ve en nuestro trabajo con conjuntos de datos biológicos. El grafo más pequeño tenía 3.828 vértices y 310.380 aristas; el más grande tenía 44.563 vértices y 2.052.228 aristas.

El número de camarillas máximas para los gráficos en nuestro banco de pruebas osciló entre 8 y 74486. Como se vio con nuestro banco de pruebas anterior, no había un patrón discernible basado en el tamaño o la densidad del gráfico. Uno podría preguntarse por qué hay una variabilidad tan amplia e impredecible. Resulta que el número de camarillas máximas puede ser extremadamente sensible a pequeños cambios en el gráfico. Incluso la modificación de un solo borde puede tener un efecto enorme. Considere, por ejemplo, un gráfico con una camarilla máxima única de tamaño k, junto con una serie de camarillas disjuntos de tamaño k – 1. La eliminación de una sola arista de la que era la camarilla más grande ahora puede resultar en muchas camarillas máximas de tamaño k – 1. Por supuesto, la adición de bordes puede tener efectos similares. Véase la Figura 4 para un ejemplo ilustrativo.

Para cada algoritmo de cada gráfico, realizamos tiempos en un nodo dedicado de un clúster para evitar interferencias de otros procesos. Si el algoritmo no se completaba en 24 horas, se detenía y se consideraba que el gráfico no se había resuelto. Elegimos umbrales para distribuir los tiempos de ejecución de los gráficos entre los cinco algoritmos que estábamos probando. Se seleccionó el umbral más grande (el más pequeño en el caso del valor p de correlación) para que la mayoría de los algoritmos, si no todos, resolvieran el gráfico. Se seleccionó el umbral más pequeño (el más grande en el caso del valor p de correlación) para que al menos uno de los algoritmos, pero no todos, resolviera el gráfico.

En cada gráfico, cronometramos el rendimiento de Backtracking Básico, Backtracking Inteligente y MC Paramaterizado. A continuación, redujimos los gráficos utilizando ES y volvimos a probar con Backtracking Inteligente y MC Parametrizado, en cuyo caso los tiempos de ejecución incluyen tanto la reducción como el paso de enumeración. Como era de esperar, se encontró que el Retroceso básico no era competitivo. Tanto el Backtracking Inteligente como el MC Parametrizado mostraron una mejora distintiva, a menudo dramática, con respecto al Backtracking Básico. La Figura 5 muestra los tiempos de ejecución de cada uno de los cinco métodos en los 100 gráficos de prueba. En algunos de los gráficos más fáciles, que tardan menos de tres minutos en resolverse, la sobrecarga de ES en realidad causó un aumento menor en el tiempo de ejecución general. Pero en los casos más difíciles, su verdadero beneficio se hizo evidente, reduciendo el tiempo de ejecución en un orden de magnitud o más. Y en todos los casos en los que dos o menos algoritmos resolvían el gráfico, el algoritmo era ES con Retroceso Inteligente, ES con MC Parametrizado,o ambos.