La massima clique problema di enumerazione: algoritmi, applicazioni e implementazioni

Utilizzando seminale massima clique enumerazione algoritmo a causa di Bron e Kerbosch come un punto di riferimento, abbiamo progettato, implementato e testato ampiamente tre miglioramenti algoritmico, l’ultima basata su osservazioni sulla natura dei grafici prodotti da trascrittomica dati. Oltre a descrivere questi miglioramenti, descriveremo il nostro strumento esistente per trovare una singola cricca massima, basata sulla teoria della trattabilità a parametro fisso (FPT) . Tale strumento è essenziale per tutti e tre i miglioramenti, poiché i primi due si basano sulla conoscenza della dimensione massima della cricca e l’ultimo utilizza lo strumento di ricerca della cricca massima come subroutine. Tutti i codici sono scritti in C / C++ e compilati in Linux. Per i test, utilizziamo 100 grafici derivati da 25 diversi set di dati che sono disponibili pubblicamente su GEO. Ci concentriamo sui dati trascrittomici, data la sua abbondanza, e evitiamo i dati sintetici, avendo imparato molto tempo fa che gli algoritmi efficaci per uno hanno poca influenza sull’altro. (Le corrispondenze patologiche annotate in vertex cover possono essere estese alla cricca, ma allo stesso modo anche loro sono ovviamente estremamente irrilevanti per i dati reali.) Nel tentativo di migliorare le prestazioni, esaminiamo la struttura dei grafici trascrittomici ed esploriamo la nozione di coperture massime della cricca e set di vertici essenziali. In effetti, troviamo che con la giusta pre-elaborazione siamo in grado di adattare gli algoritmi ai tipi di dati che incontriamo abitualmente e che ora possiamo risolvere istanze precedentemente considerate inattaccabili.

Algoritmi

Nelle sezioni seguenti, descriviamo ciascuno degli algoritmi MCE che abbiamo implementato e testato. Il primo è l’algoritmo di Bron e Kerbosch, che chiamiamo Backtracking di base e usiamo come punto di riferimento. Poiché tutti i nostri miglioramenti successivi fanno uso di un algoritmo che trova una singola cricca massima, descriviamo successivamente il nostro strumento esistente, chiamato Maximum Clique Finder (MCF), che fa proprio questo. Successivamente modifichiamo l’algoritmo di Backtracking di base per sfruttare il fatto che vogliamo solo trovare le cricche massime e possiamo calcolare rapidamente la dimensione massima della cricca. Chiamiamo questo approccio Backtracking intelligente, poiché ritorna attivamente presto da rami che non porteranno a una cricca massima. Quindi modifichiamo MCF stesso per enumerare tutte le cricche massime, un approccio che chiamiamo Cricca massima parametrizzata o MC parametrizzato. In un certo senso questo è un altro approccio di backtracking che va anche oltre per sfruttare il fatto che vogliamo solo trovare cricche massime. Infine, sulla base di osservazioni sulle proprietà dei grafici biologici, introduciamo i concetti di coperture massime della cricca e set di vertici essenziali e li applichiamo per migliorare significativamente il runtime degli algoritmi di backtracking.

Backtracking di base

La pubblicazione seminale maximal clique descrive due algoritmi. Viene fornita una presentazione dettagliata del secondo, che è una versione migliorata del primo. È questo secondo metodo, più efficiente, che implementiamo e testiamo. Ci riferiremo qui come Backtracking di base. Tutte le cricche massime sono enumerate con un attraversamento dell’albero di ricerca in profondità. Le strutture dati primarie utilizzate sono tre insiemi globali di vertici: COMPSUB, CANDIDATES e NOT. COMPSUB contiene i vertici nella cricca corrente ed è inizialmente vuoto. CANDIDATI contiene vertici inesplorati che possono estendere la cricca corrente e inizialmente contiene tutti i vertici nel grafico. NON contiene vertici esplorati che non possono estendere la cricca corrente ed è inizialmente vuoto. Ogni chiamata ricorsiva esegue tre passaggi:

• Selezionare un vertice v in CANDIDATI e spostarlo in COMPSUB.

• Rimuovere tutti i vertici non adiacenti a v da entrambi i CANDIDATI e NON. A questo punto, se entrambi i CANDIDATI e NON sono vuoti, allora COMPSUB è una cricca massima. In tal caso, emetti COMPSUB come cique massimo e continua il passaggio successivo. In caso contrario, chiamare ricorsivamente il passaggio precedente.

• Sposta v da COMPSUB a NOT.

Si noti che NOT viene utilizzato per evitare di generare cricche massime duplicate. L’albero di ricerca può essere potato terminando un ramo in anticipo se un vertice di NOT è collegato a tutti i vertici dei CANDIDATI.

I vertici vengono selezionati in modo tale che questa potatura si verifichi il prima possibile. Omettiamo i dettagli poiché non sono pertinenti alle nostre modifiche dell’algoritmo.

I requisiti di archiviazione del Backtracking di base sono relativamente modesti. Nessuna informazione sulle cricche massime precedenti deve essere mantenuta. Nei miglioramenti che testeremo, ci concentriamo sulla velocità ma miglioriamo anche l’utilizzo della memoria. Pertanto, tali limitazioni non sono in alcun caso proibitive per nessuno dei nostri metodi testati. Tuttavia, in alcuni ambienti, l’utilizzo della memoria può essere estremo. Ci riferiamo al lettore interessato .

La nostra implementazione di Backtracking di base funge da punto di riferimento iniziale su cui ora possiamo cercare di migliorare.

Trovare una singola cricca massima

Usiamo il termine Maximum Clique Finder (MCF) per indicare il software che abbiamo implementato e perfezionato per trovare una singola cricca di dimensioni maggiori . MCF impiega una suite di regole di pre-elaborazione insieme a una strategia di ramificazione che rispecchia il noto approccio FPT alla copertura dei vertici . Per prima cosa invoca una semplice euristica avida per trovare rapidamente una cricca ragionevolmente grande. Questa cricca viene quindi utilizzata per la pre-elaborazione, poiché pone un limite inferiore alla dimensione massima della cricca. L’euristica funziona scegliendo il vertice di grado più alto, v, quindi scegliendo il vicino di grado più alto di v. Questi due vertici formano una cricca iniziale C, che viene poi estesa iterativamente scegliendo il vertice di grado più alto adiacente a tutto C. Su ogni iterazione, qualsiasi vertice non adiacente a tutto C viene rimosso. Il processo continua fino a quando non esistono più vertici al di fuori di C. Poiché |C| è un limite inferiore alla dimensione massima della cricca, tutti i vertici con grado inferiore a |C – 1| possono essere rimossi definitivamente dal grafico originale. Successivamente, tutti i vertici con grado n – 1 vengono temporaneamente rimossi dal grafico, ma mantenuti in una lista poiché devono far parte di qualsiasi cricca massima. MCF sfrutta una nuova forma di pre-elaborazione del colore, utilizzata in precedenza per guidare la ramificazione. Questa forma di pre-elaborazione tenta di ridurre il grafico come segue. Dato un noto limite inferiore k sulla dimensione della cricca massima, per ogni vertice v applichiamo una colorazione avida veloce a v e ai suoi vicini. Se questi vertici possono essere colorati con meno di k colori, allora v non può essere parte di una cricca massima e viene rimosso dal grafico. Una volta ridotto il grafico, MCF utilizza una ramificazione ricorsiva standard sui vertici, in cui ogni ramo presuppone che il vertice sia o non sia nella cricca massima.

Intelligent backtracking

Data l’efficacia relativa con cui possiamo trovare una singola cricca massima, sembra logico considerare se la conoscenza delle dimensioni di quella cricca può essere utile per enumerare tutte le cricche massime. A quanto pare, la conoscenza della dimensione massima della cricca k porta a un piccolo, semplice cambiamento nell’algoritmo di Backtracking di base. In particolare, ad ogni nodo nell’albero di ricerca controlliamo se ci sono meno di k vertici nell’unione di COMPSUB e CANDIDATI. Se è così, quel ramo non può portare a una cricca di dimensione k, e così torniamo. Vedi Figura 2. Mentre la modifica può sembrare minore, la potatura risultante dell’albero di ricerca può portare a una sostanziale riduzione dello spazio di ricerca. Oltre a questa piccola modifica alla ramificazione, applichiamo la pre-elaborazione del colore come descritto in precedenza per ridurre il grafico prima di inviarlo all’algoritmo di backtracking migliorato. Preprocessing del colore combinato con il cambiamento di ramificazione minore che chiamiamo Backtracking intelligente.

Enumerazione paramaterizzata

Dato che MCF impiega una strategia di ramificazione dei vertici, abbiamo studiato se potesse essere modificata per enumerare non solo una, ma tutte le cricche massime. Si scopre che MCF, inoltre, si presta a una modifica semplice che si traduce in enumerazione di tutte le cricche massime. La modifica consiste semplicemente nel mantenere un elenco globale di tutte le cricche di dimensioni maggiori trovate finora. Ogni volta che viene trovata una cricca massima più grande, l’elenco viene svuotato e aggiornato per contenere solo la nuova cricca massima. Quando lo spazio di ricerca è stato esaurito, viene emesso l’elenco delle cricche massime.

Dobbiamo prestare particolare attenzione, tuttavia, a notare che alcune regole di pre-elaborazione utilizzate durante l’interleaving non sono più valide. Si consideri, ad esempio, la rimozione di un vertice fogliare. L’analogo della cricca consiste nel trovare un vertice con grado n-2 e rimuovere il suo solitario non vicino. Questa regola presuppone chiaramente che sia desiderata solo una singola cricca massima, perché ignora qualsiasi cricca a seconda del vertice scartato. Pertanto questa particolare regola di pre-elaborazione deve essere omessa una volta iniziata la ramificazione.

Coperture della cricca massima

Se consideriamo MCF come una subroutine black box che può essere chiamata ripetutamente, può essere utilizzata in un semplice algoritmo greedy per calcolare un insieme massimo di cricche massime disgiunte. Calcoliamo semplicemente una cricca massima, la rimuoviamo dal grafico e iteriamo fino a quando la dimensione di una cricca massima diminuisce. Per esplorare i vantaggi del calcolo di un tale insieme, introduciamo la seguente nozione:

Definizione 1 Una copertura massima della cricca di G = (V, E) è un insieme V’ V V con la proprietà che ogni cricca massima di G contiene un vertice nella copertina.

L’unione di tutti i vertici contenuti in un insieme massimo di cricche massime disgiunte è ovviamente una copertura massima della cricca (d’ora in poi MCC), perché tutte le cricche massime devono sovrapporsi a tale insieme. Ciò porta a un utile algoritmo di riduzione. Qualsiasi vertice non adiacente ad almeno un membro di un MCC non può essere in una cricca massima e può quindi essere rimosso.

In pratica, troviamo che l’applicazione di MCC prima dei precedenti algoritmi di backtracking produce solo miglioramenti marginali. Il concetto di MCC, tuttavia, porta a un approccio molto più potente basato sui singoli vertici. Poiché qualsiasi miglioramento apportato da MCC è sussunto dal prossimo approccio, non testiamo MCC da solo.

Essential vertex sets

La nostra indagine sull’algoritmo MCC ha rivelato che in genere non riduce la dimensione del grafico più delle regole di pre-elaborazione già incorporate in MCF. Ad esempio, MCF trova già rapidamente un limite inferiore sulla dimensione massima della cricca e rimuove qualsiasi vertice con un grado inferiore a questo limite. Ad un esame più attento, tuttavia, abbiamo scoperto che per 74 dei 75 grafici che abbiamo inizialmente testato per la versione conferenza di questo documento, era necessaria una sola cricca in un MCC. Vale a dire, una cricca massima copriva tutte le altre cricche massime. E nel nostro attuale banco di prova di 100 grafici, in ogni caso una singola cricca massima è sufficiente per un MCC. In realtà questo coincide strettamente con la nostra esperienza, in cui in genere vediamo un’alta sovrapposizione tra grandi cricche nei grafici trascrittomici che incontriamo regolarmente. Sulla base di questa osservazione, ora perfezioneremo il concetto di MCC. Piuttosto che coprire le cricche massime con le cricche, copriamo le cricche massime con i singoli vertici.

Definiamo un vertice essenziale come uno che è contenuto in ogni cricca massima. Ovviamente è possibile che un dato grafico non abbia tale vertice, anche quando contiene molte cricche massime sovrapposte. Ma il test empirico di grandi grafici trascrittomici mostra che un numero schiacciante contiene numerosi vertici essenziali. E per ridurre il grafico, anche uno sarà sufficiente. Un vertice essenziale ha il potenziale per essere estremamente utile, perché ci permette di rimuovere tutti i suoi non vicini. Impieghiamo la seguente osservazione: per qualsiasi grafico G, ω(G) >ω(G/v) se e solo se v copre tutte le cricche massime, dove ω (G) è la dimensione massima della cricca di G.

Definiamo un insieme essenziale come l’insieme di tutti i vertici essenziali. L’algoritmo Essential Set (ES), come descritto in Figura 3, trova tutti i vertici essenziali in un grafico. Quindi riduce il grafico rimuovendo, per ogni vertice essenziale, tutti i non vicini di quel vertice. L’algoritmo ES può essere eseguito in combinazione con uno qualsiasi degli algoritmi MCE di backtracking, o addirittura prima di qualsiasi algoritmo che esegua MCE con qualsiasi metodo, poiché il suo output è un grafico ridotto che contiene ancora tutte le cricche massime dal grafico originale. Come mostrano i nostri test, il miglioramento del runtime offerto dall’algoritmo ES può essere drammatico.

Implementazione

Abbiamo implementato tutti gli algoritmi in C o C++. Il codice è stato compilato utilizzando il compilatore GCC 4.4.3 sul sistema operativo Ubuntu Linux versione 10.04.2 e il compilatore GCC 3.3.5 sotto Debian Linux versione 3.1. Tutti i tempi sono stati condotti in quest’ultimo ambiente Debian su nodi dedicati di un cluster per garantire che nessun effetto sui tempi dai processi concorrenti. Ogni nodo aveva un processore Intel Xeon dual-core in esecuzione a 3,20 GHz e 4 GB di memoria principale.

Testing

Nella versione conferenza di questo documento, abbiamo utilizzato tre diversi set di dati a 25 soglie ciascuno per ricavare un totale di 75 grafici su cui testare i nostri miglioramenti algoritmici. Mentre questi grafici certamente sufficiente come una prova iniziale di concetto, due preoccupazioni potrebbero essere sollevate al riguardo. In primo luogo, si potrebbe sostenere che tre set di dati non sono una dimensione del campione sufficientemente grande da fornire un vero senso della natura complessiva dei dati trascrittomici o dell’efficacia generale di un miglioramento algoritmico su tali dati, nonostante il gran numero di soglie. E in secondo luogo, dal momento che i tre set di dati sono proprietari e non disponibili al pubblico, i risultati non erano così facilmente riproducibili come avrebbero potuto altrimenti essere. Ottenere versioni de-identificate, mentre fattibile, era un obtacle inutile alla riproducibilità.

Affrontiamo tali preoccupazioni qui creando una nuova suite di grafici trascrittomici su cui testare i nostri miglioramenti algoritmici. La suite è composta da grafici derivati da 25 set di dati ottenuti dal Gene Expression Omnibus (GEO), un repository accessibile al pubblico. Per ogni set di dati, i grafici sono stati creati a quattro soglie diverse, per un totale di 100 grafici. I set di dati sono stati selezionati per fornire un campionamento ragionevolmente diversificato di tipo sperimentale, specie e tipo di chip microarray mRNA. Coprono 8 specie diverse e un certo numero di diverse condizioni sperimentali come serie temporali, ceppo, dose e paziente. Poiché i nostri grafici derivano da valori di correlazione di soglia, abbiamo escluso dalla considerazione qualsiasi set di dati con meno di 12 condizioni. Le correlazioni di soglia calcolate utilizzando così poche condizioni possono produrre tassi inaccettabilmente elevati di falsi positivi e falsi negativi. Il numero di condizioni varia da un minimo di 12 a un massimo di 153. Nove dei set di dati non erano stati log-trasformati, nel qual caso abbiamo eseguito log-trasformazione. Quattro dei set di dati contenevano valori mancanti; in questi casi abbiamo usato valori p di correlazione piuttosto che correlazioni per la soglia. Vedere la Tabella 1 per un elenco dei set di dati GEO utilizzati per il test.

Dai dati di espressione, per prima cosa abbiamo costruito grafici ponderati in cui i vertici rappresentavano sonde e i pesi dei bordi erano coefficienti di correlazione di Pearson calcolati in condizioni sperimentali. Abbiamo quindi convertito i grafici ponderati in grafici non ponderati mantenendo solo quei bordi i cui pesi erano pari o superiori a qualche soglia scelta, t. Per ogni set di dati, abbiamo scelto quattro valori per t. Tutti i valori di dimensione/densità erano all’interno dello spettro tipicamente visto nel nostro lavoro con set di dati biologici. Il grafico più piccolo aveva 3.828 vertici e 310.380 bordi; il più grande aveva 44.563 vertici e 2.052.228 bordi.

Il numero di cricche massime per i grafici nel nostro banco di prova variava da 8 a 74486. Come visto con il nostro banco di prova precedente, non c’era un modello distinguibile in base alla dimensione o alla densità del grafico. Ci si potrebbe chiedere perché c’è una variabilità così ampia e imprevedibile. Si scopre che il numero di cricche massime può essere estremamente sensibile a piccoli cambiamenti nel grafico. Anche la modifica di un singolo bordo può avere un effetto enorme. Si consideri, ad esempio, un grafico con una cricca massima unica di dimensione k, insieme a una serie di cricche disgiunte di dimensione k – 1. La rimozione di un solo bordo da quella che era la cricca più grande può ora portare a molte cricche massime di dimensioni k – 1. L’aggiunta di bordi può ovviamente avere effetti simili. Vedere la Figura 4 per un esempio illustrativo.

Per ogni algoritmo su ogni grafico, abbiamo condotto i tempi su un nodo dedicato di un cluster per evitare interferenze da altri processi. Se l’algoritmo non è stato completato entro 24 ore, è stato fermato e il grafico è stato ritenuto non essere stato risolto. Abbiamo scelto le soglie per distribuire i runtime dei grafici sui cinque algoritmi che stavamo testando. La soglia più grande (più piccola nel caso della correlazione p-value) è stata selezionata in modo che la maggior parte degli algoritmi, se non tutti, risolvesse il grafico. La soglia più piccola (più grande nel caso della correlazione p-value) è stata selezionata in modo che almeno uno degli algoritmi, ma non tutti, abbia risolto il grafico.

Su ogni grafico abbiamo cronometrato le prestazioni di Backtracking di base, Backtracking intelligente e MC paramaterizzato. Abbiamo quindi ridotto i grafici utilizzando ES e riprovato con Backtracking intelligente e MC parametrizzato, nel qual caso i runtime includono sia la fase di riduzione che quella di enumerazione. Come previsto, il Backtracking di base è risultato non competitivo. Sia il Backtracking intelligente che l’MC parametrizzato hanno mostrato un netto, spesso drammatico, miglioramento rispetto al Backtracking di base. La figura 5 mostra i runtime di ciascuno dei cinque metodi su tutti i 100 grafici di test. Su alcuni dei grafici più semplici, quelli che impiegano meno di tre minuti per risolvere, il sovraccarico di ES ha effettivamente causato un lieve aumento del runtime complessivo. Ma nei casi più difficili il suo vero vantaggio è diventato evidente, riducendo il runtime di un ordine di grandezza o più. E in tutti i casi in cui due o meno algoritmi risolvevano il grafico, l’algoritmo era ES con Backtracking intelligente, ES con MC parametrizzato o entrambi.