O máximo panelinha problema de enumeração: algoritmos, aplicações e implementações

Usando o seminal máxima panelinha algoritmo de enumeração devido ao Bron e Kerbosch como referência, temos projetado, implementado e testado extensivamente três melhorias de algoritmos, a última com base em observações sobre a natureza dos gráficos produzidos pelo transcriptomic de dados. Juntamente com a descrição destas melhorias, vamos descrever a nossa ferramenta existente para encontrar um único clique máximo, com base na teoria da tractabilidade de parâmetros fixos (FPT) . Tal ferramenta é essencial para todas as três melhorias, uma vez que os dois primeiros dependem do conhecimento do tamanho máximo clique, e o último usa a ferramenta de busca máxima clique como uma sub-rotina. Todos os códigos são escritos em C / C++ e compilados em Linux. Para testes, usamos 100 grafos derivados de 25 conjuntos de dados diferentes que estão disponíveis publicamente no GEO. Concentramo-nos em dados transcriptômicos, dada a sua abundância, e evitamos os dados sintéticos, tendo aprendido há muito tempo que algoritmos eficazes para um têm pouco a ver com o outro. (The patological matchings noted in for vertex cover can be extended to clique, but also they too are of course hugely irrelevant to real data.) Em um esforço para melhorar o desempenho, nós examinamos a estrutura dos grafos transcriptômicos e exploramos a noção de máxima clique capas e conjuntos de vértices essenciais. Na verdade, descobrimos que com o pré-processamento certo somos capazes de adaptar algoritmos para os tipos de dados que encontramos rotineiramente, e que agora podemos resolver instâncias anteriormente consideradas inatacáveis.

algoritmos

nas seguintes seções, nós descrevemos cada um dos algoritmos MCE que implementamos e testamos. O primeiro é o algoritmo de Bron e Kerbosch , que chamamos de Backtracking básico e usar como referência. Uma vez que todas as nossas melhorias subsequentes fazem uso de um algoritmo que encontra um único clique máximo, a seguir descrevemos a nossa ferramenta existente, chamada Maximum Clique Finder (MCF), que faz exatamente isso. Em seguida, modificamos o algoritmo de Backtracking básico para tirar vantagem do fato de que só queremos encontrar os cliques máximos e pode calcular rapidamente o tamanho máximo do clique. Nós chamamos essa abordagem de Backtracking inteligente, uma vez que ela retorna ativamente cedo de ramos que não levará a um clique máximo. Nós então modificamos MCF para enumerar todos os cliques máximos, uma abordagem que chamamos de Clique máximo parametrizado, ou MC parametrizado. De certa forma, esta é outra abordagem de retrocesso que vai ainda mais longe para explorar o fato de que só queremos encontrar o máximo de cliques. Finalmente, com base em observações sobre as propriedades dos grafos biológicos, introduzimos os conceitos capas máximas clique e conjuntos essenciais de vértices, e aplicamo-los para melhorar significativamente o tempo de execução de algoritmos de backtracking.

Basic backtracking

The seminal maximal clique publication describes two algorithms. Uma apresentação detalhada da Segunda, que é uma versão melhorada da primeira, é fornecida. É este segundo, mais eficiente, método que implementamos e testamos. Referimo-nos a ele aqui como um Backtracking básico. Todas as cliques maximais são enumeradas com uma árvore de busca em profundidade. As estruturas de dados primárias empregadas são três conjuntos globais de vértices: COMPSUB, candidatos e não. COMPSUB contém os vértices no clique atual, e está inicialmente vazio. CANDIDATES contains unexplored vertices that can extend the current clique, and initially contains all vertices in the graph. NOT contains explored vertices that cannot extend the current clique, and is initially empty. Cada chamada recursiva executa três passos:

• selecione um vértice v em candidatos e mova-o para COMPSUB.

• remover todos os vértices não adjacentes a v de ambos os candidatos e não. Neste ponto, se ambos os candidatos e não estão vazios, então COMPSUB é um clique maximal. Se assim for, o compsub de saída como um clique maximal e continuar o próximo passo. Se não, então recursivamente chamar o passo anterior.

• mover v do COMPSUB para não.

Note que não é usado para evitar gerar cliques maximais duplicados. A árvore de busca pode ser podada por terminar um ramo mais cedo se algum vértice de não está conectado a todos os vértices de candidatos.

os vértices são selecionados de uma forma que faz com que esta poda ocorra o mais rápido possível. Omitimos os detalhes uma vez que não são pertinentes às nossas modificações do algoritmo.

as necessidades de armazenamento do Backtracking básico são relativamente modestas. Nenhuma informação sobre cliques máximos anteriores precisa ser retida. Nas melhorias que vamos testar, focamos na velocidade, mas também melhorar o uso da memória. Assim, tais limitações não são, em caso algum, proibitivas para qualquer um dos nossos métodos testados. No entanto, em alguns ambientes, a utilização da memória pode ser extrema. Referimo-nos ao leitor interessado .

nossa implementação básica de Backtracking serve como uma referência inicial sobre a qual podemos agora tentar melhorar.

encontrando um único clique máximo

usamos o termo máximo Clique Finder (MCF) para denotar o software que implementamos e refinado para encontrar um único clique de maior tamanho . MCF emprega um conjunto de regras de pré-processamento, juntamente com uma estratégia de ramificação que espelha a bem conhecida abordagem FPT para cobertura de vértices . Primeiro invoca uma simples heurística gananciosa para encontrar um grupo razoavelmente grande rapidamente. Este clique é então usado para pré-processamento, uma vez que coloca um limite inferior no tamanho máximo do clique. A heurística funciona escolhendo o mais alto grau de vértices, v, em seguida, escolhendo o mais alto grau vizinho de v. Estes dois vértices formulário inicial do grupo C, que é, em seguida, iterativamente estendido escolhendo o mais alto grau de vértices adjacentes para todos do C. Em cada iteração, qualquer de vértices não adjacentes para todo C é removido. O processo continua até que não existam mais vértices fora de C. Desde |C| é um limite inferior no tamanho máximo clique, todos os vértices com grau inferior a |c – 1| podem ser removidos permanentemente do grafo original. Em seguida, todos os vértices com grau n – 1 são temporariamente removidos do grafo, mas mantidos em uma lista uma vez que eles devem ser parte de qualquer clique máximo. A MCF explora uma nova forma de pré-processamento de cores, usada anteriormente para orientar a ramificação. Esta forma de pré-processamento tenta reduzir o gráfico da seguinte forma. Dado um conhecido limite inferior k no tamanho do clique máximo, para cada vértice v aplicamos coloração gananciosa rápida para v e seus vizinhos. Se estes vértices podem ser coloridos com menos de k cores, então v não pode ser parte de um clique máximo e é removido do grafo. Uma vez que o grafo é assim reduzido, MCF usa ramificação recursiva padrão em vértices, onde cada ramo assume que o vértice ou está ou não no clique máximo.

backtracking inteligente

dada a eficácia relativa com que podemos encontrar um único clique máximo, parece lógico considerar se o conhecimento do tamanho desse clique pode ser útil na enumeração de todos os grupos máximos. Como acontece, o conhecimento do tamanho máximo do clique k leva a uma pequena e direta mudança no algoritmo básico de Backtracking. Especificamente, em cada nó na árvore de busca Nós verificamos se há menos de K vértices na União de COMPSUB e candidatos. Se assim for, esse ramo não pode levar a um grupo do tamanho k, e então nós retornamos. Ver Figura 2. Embora a modificação possa parecer menor, a poda resultante da árvore de busca pode levar a uma redução substancial no espaço de busca. Além desta pequena mudança de ramificação, aplicamos pré-processamento de cores como descrito anteriormente para reduzir o grafo antes de submetê-lo ao algoritmo de backtracking melhorado. Pré-processamento de cores combinado com a pequena mudança de ramificação que chamamos de Backtracking inteligente.

Paramaterized enumeração

Dado que MCF emprega um vértice de ramificação estratégia, investigamos se ele pode ser modificado para enumerar não apenas um, mas todos máximo de panelinhas. Acontece que MCF, também, se presta a uma modificação direta que resulta na enumeração de todos os cliques máximos. A modificação é simplesmente manter uma lista global de todos os cliques do maior tamanho encontrado até agora. Sempre que um clique máximo maior é encontrado, a lista é lavada e refrescada para conter apenas o novo clique máximo. Quando o espaço de pesquisa estiver esgotado, a lista de cliques máximos é de saída.No entanto, há que ter especial cuidado para que certas regras de pré-processamento utilizadas durante a interleaving deixem de ser válidas. Considere, por exemplo, a remoção de um vértice de folha. O clique analógico é encontrar um vértice com grau n – 2 e remover seu não-vizinho solitário. Esta regra assume que apenas um clique máximo é desejado, porque ignora qualquer clique dependendo do vértice descartado. Por conseguinte, esta regra específica de pré-processamento deve ser omitida logo que a ramificação tenha começado.

maximum clique covers

If we view MCF as a black box subrotine that can be called repeatedly, it can be used in a simple greedy algorithm for computing a maximal set of disjoint maximum cliques. Nós meramente computamos um clique máximo, removemo-lo do grafo, e iteramos até que o tamanho de um clique máximo diminui. Para explorar as vantagens de computar tal conjunto, introduzimos a seguinte noção:

Definição 1 uma cobertura máxima clique de G = (V, e) é um conjunto V’ ⊆ V com a propriedade de que cada clique máximo de G contém algum vértice na capa.

a união de todos os vértices contidos em um conjunto máximo de cliques máximos disjuntos é, naturalmente, uma cobertura de clique máxima (doravante MCC), porque todos os cliques máximos devem se sobrepor com tal conjunto. Isto leva a um algoritmo de redução útil. Qualquer vértice não adjacente a pelo menos um membro de um MCC não pode estar em um clique máximo, e pode, portanto, ser removido.

na prática, achamos que a aplicação de MCC antes dos algoritmos de backtracking anteriores produz apenas melhorias marginais. O conceito de MCC, no entanto, leva a uma abordagem muito mais poderosa baseada em vértices individuais. Uma vez que qualquer melhoria feita pela MCC é subsumida pela próxima abordagem, não testamos a MCC por si só.

conjuntos de vértices essenciais

a nossa investigação do algoritmo MCC revelou que normalmente não reduz o tamanho do gráfico mais do que as regras de pré-processamento já incorporadas no MCF. Por exemplo, MCF já encontra rapidamente um limite inferior no tamanho máximo do clique e remove qualquer vértice com grau inferior a este limite. Após uma análise mais aprofundada, no entanto, descobrimos que para 74 de 75 gráficos que inicialmente testamos para a versão de conferência deste artigo, apenas um clique era necessário em um MCC. Ou seja, um grupo máximo cobriu todos os outros grupos máximos. E em nosso testbed atual de 100 grafos, em todos os casos um único clique máximo é suficiente para um MCC. Na verdade, isso coincide estreitamente com a nossa experiência, na qual tipicamente vemos alta sobreposição entre grandes cliques nos grafos transcriptômicos que encontramos em uma base regular. Com base nesta observação, vamos agora aperfeiçoar o conceito de MCC. Ao invés de cobrir o máximo cliques com cliques, nós cobrimos o máximo cliques com vértices individuais.

definimos um vértice essencial como aquele que está contido em cada clique máximo. É claro que é possível para um dado grafo não ter tal vértice, mesmo quando ele contém muitos cliques máximos sobrepostos. Mas testes empíricos de grafos transcriptômicos grandes mostram que um número esmagador contém numerosos vértices essenciais. E para reduzir o gráfico, mesmo um será suficiente. Um vértice essencial tem o potencial de ser extremamente útil, porque nos permite remover todos os seus não-vizinhos. Nós empregamos a seguinte observação: para qualquer grafo G, ω(G) >ω(G/v) se e somente se v abrange todos os cliques máximos, onde ω(G) é o tamanho máximo de clique de G.

nós definimos um conjunto essencial para ser o conjunto de todos os vértices essenciais. O algoritmo de conjunto essencial (ES), como descrito na Figura 3, encontra todos os vértices essenciais em um grafo. Ele então reduz o grafo removendo, para cada vértice essencial, todos os não-vizinhos desse vértice. O algoritmo de ES pode ser executado em conjunto com qualquer um dos algoritmos de backtracking MCE, ou mesmo antes de qualquer algoritmo que faz MCE por qualquer método, uma vez que sua saída é um grafo reduzido que ainda contém todos os cliques máximos do grafo original. Como os nossos testes mostram, a melhoria do tempo de execução oferecida pelo algoritmo ES pode ser dramática.

Implementation

We implemented all algorithms in either C or C++. O código foi compilado usando o compilador gcc 4.4.3 no Ubuntu Linux versão 10.04.2, bem como o compilador gcc 3.3.5 sob Debian Linux Versão 3.1. Todos os horários foram conduzidos no último ambiente Debian em nós dedicados de um cluster para garantir que não afetem os horários de processos simultâneos. Cada nó tinha um processador Intel Xeon Dual-core rodando a 3,20 GHz e 4 GB de memória principal.

Testing

In the conference version of this paper, we used three different datasets at 25 thresholds each to derive a total of 75 graphs on which to test our algorithmic improvements. Embora estes gráficos fossem certamente suficientes como uma prova inicial do conceito, duas preocupações poderiam ser levantadas a respeito deles. Primeiro, pode-se argumentar que três conjuntos de dados não são um tamanho de amostra suficientemente grande para fornecer um verdadeiro sentido da natureza geral dos dados transcriptômicos ou a eficácia geral de uma melhoria algorítmica em tais dados, o grande número de limiares não obstante. E em segundo lugar, uma vez que os três conjuntos de dados são proprietários e não estão disponíveis ao público, os resultados não foram tão facilmente reprodutíveis como poderiam ter sido. A obtenção de versões desidentificadas, embora viável, era um obtáculo desnecessário para a reprodutibilidade.

nós abordamos essas preocupações aqui criando um novo conjunto de grafos transcriptômicos sobre os quais testar nossas melhorias algorítmicas. O conjunto consiste de grafos derivados de 25 conjuntos de dados obtidos a partir da expressão genética Omnibus (GEO) , um repositório acessível ao público. Para cada conjunto de dados, grafos foram criados em quatro limiares diferentes, para um total de 100 grafos. Os conjuntos de dados foram selecionados para fornecer uma amostragem razoavelmente diversificada de tipo experimental, espécie e tipo de chip de microarray mRNA. Abrangem 8 espécies diferentes e uma série de condições experimentais diferentes, tais como séries temporais, estirpe, dose e paciente. Uma vez que nossos grafos são derivados de valores de correlação de thresholding, excluímos da consideração qualquer conjunto de dados com menos de 12 condições. Limitar correlações calculadas usando tão poucas condições pode produzir taxas inaceitavelmente grandes de falsos positivos e falsos negativos. O número de condições varia de um baixo de 12 a um alto de 153. Nove dos conjuntos de dados não tinham sido log-transformados, e nesse caso realizamos log-transformação. Quatro dos conjuntos de dados continham valores em falta; nestes casos, utilizámos valores-p de correlação em vez de correlações para o limiar. Ver Quadro 1 para uma lista dos conjuntos de dados geográficos utilizados para os ensaios.

a partir dos dados de expressão, nós primeiro construímos grafos ponderados nos quais vértices representavam sondas e pesos de aresta eram coeficientes de correlação de Pearson computados através de condições experimentais. Nós, em seguida, convertido ponderada de gráficos em não ponderada gráficos, retendo apenas aquelas arestas cujos pesos foram no ou acima do limiar escolhido, t. Para cada conjunto de dados, optou-se por quatro valores para t. Todos os tamanho/densidade os valores estavam dentro do espectro normalmente visto em nosso trabalho com conjuntos de dados biológicos. O menor grafo tinha 3.828 vértices e 310.380 arestas; o maior tinha 44.563 vértices e 2.052.228 arestas.

o número de cliques máximos para os grafos em nosso testbed variou de 8 a 74486. Como visto no nosso testbed anterior, não havia nenhum padrão discernível baseado no tamanho do grafo ou densidade. Pode-se perguntar Por que há uma variabilidade tão grande e imprevisível. Acontece que o número de cliques máximos pode ser extremamente sensível a pequenas mudanças no grafo. Mesmo a modificação de uma única borda pode ter um efeito enorme. Considere, por exemplo, um grafo com um clique máximo único de tamanho k, juntamente com uma série de cliques disjuntos de tamanho k – 1. A remoção de apenas uma aresta do que era o maior clique pode agora resultar em muitos cliques máximos de tamanho k – 1. A adição de borda pode, naturalmente, ter efeitos semelhantes. Ver Figura 4 para um exemplo ilustrativo.

para cada algoritmo em cada grafo, nós realizamos timings em um nó dedicado de um conjunto para evitar interferência de outros processos. Se o algoritmo não terminou em 24 horas, foi interrompido e o grafo foi considerado como não tendo sido resolvido. Escolhemos limiares para espalhar os períodos de execução dos gráficos pelos cinco algoritmos que estávamos a testar. O maior (menor no caso do valor p de correlação) limiar foi selecionado de modo que a maioria dos algoritmos, se não todos, resolveu o grafo. O menor (maior no caso do valor p de correlação) limiar foi selecionado de modo que pelo menos um dos algoritmos, mas não todos, resolveu o grafo.

On each graph we timed the performance of Basic Backtracking, Intelligent Backtracking, and Paramaterized MC. Nós então reduzimos os grafos usando ES e repetimos com Backtracking inteligente e MC parametrizado, e nesse caso os períodos de execução incluem tanto a redução quanto o passo de enumeração. Como esperado, o Backtracking básico não foi considerado competitivo. Tanto o Backtracking inteligente quanto o MC parametrizado mostraram uma melhora distinta, muitas vezes dramática, sobre o Backtracking básico. A figura 5 mostra os períodos de execução de cada um dos cinco métodos em todos os 100 gráficos de ensaio. Em alguns dos grafos mais fáceis, aqueles que levam menos de três minutos para resolver, a sobrecarga de ES realmente causou um pequeno aumento no tempo de execução global. Mas nos casos mais difíceis o seu verdadeiro benefício tornou-se aparente, reduzindo o tempo de execução por uma ordem de magnitude ou mais. E em todos os casos onde dois ou menos algoritmos resolveram o grafo, o algoritmo era ou ES com Backtracking Inteligente, ES com MC parametrizado, ou ambos.