The maximum clique enumeration problem: algorithms, applications, and implementations

Unter Verwendung des bahnbrechenden maximalen Clique-Enumerationsalgorithmus von Bron und Kerbosch als Benchmark haben wir drei algorithmische Verbesserungen entworfen, implementiert und ausgiebig getestet, wobei die letzte auf Beobachtungen über die Art der durch transkriptomische Daten erzeugten Graphen basiert. Neben der Beschreibung dieser Verbesserungen werden wir unser vorhandenes Tool zum Finden einer einzelnen maximalen Clique beschreiben, das auf der Theorie der Fixed-Parameter-Tractability (FPT) basiert . Ein solches Werkzeug ist für alle drei Verbesserungen unerlässlich, da die ersten beiden auf der Kenntnis der maximalen Cliquengröße beruhen und die letzte das maximale Cliquenfindungstool als Unterprogramm verwendet. Alle Codes sind in C / C ++ geschrieben und in Linux kompiliert. Zum Testen verwenden wir 100 Grafiken aus 25 verschiedenen Datensätzen, die auf GEO öffentlich verfügbar sind. Wir konzentrieren uns angesichts seiner Fülle auf transkriptomische Daten und meiden synthetische Daten, da wir vor langer Zeit gelernt haben, dass effektive Algorithmen für den einen wenig Einfluss auf den anderen haben. (Die pathologischen Übereinstimmungen in for vertex cover können auf clique ausgedehnt werden, aber auch sie sind natürlich für reale Daten äußerst irrelevant.) Um die Leistung zu verbessern, untersuchen wir die Struktur transkriptomischer Graphen und untersuchen den Begriff maximaler Clique-Covers und essentieller Vertex-Sets. Tatsächlich stellen wir fest, dass wir mit der richtigen Vorverarbeitung Algorithmen an die Arten von Daten anpassen können, auf die wir routinemäßig stoßen, und dass wir jetzt Fälle lösen können, die zuvor als unangreifbar galten.

Algorithmen

In den folgenden Abschnitten beschreiben wir jeden der von uns implementierten und getesteten MCE-Algorithmen. Der erste ist der Algorithmus von Bron und Kerbosch , den wir Basic Backtracking nennen und als Benchmark verwenden. Da alle unsere nachfolgenden Verbesserungen einen Algorithmus verwenden, der eine einzelne maximale Clique findet, beschreiben wir als nächstes unser bestehendes Tool namens Maximum Clique Finder (MCF), das genau das tut. Als nächstes ändern wir den grundlegenden Backtracking-Algorithmus, um die Tatsache auszunutzen, dass wir nur die maximalen Cliquen finden möchten und schnell die maximale Cliquengröße berechnen können. Wir nennen diesen Ansatz intelligentes Backtracking, da er aktiv früh von Zweigen zurückkehrt, die nicht zu einer maximalen Clique führen. Wir modifizieren dann MCF selbst, um alle maximalen Cliquen aufzuzählen, ein Ansatz, den wir Parametrisierte maximale Clique oder parametrisierte MC nennen. In gewisser Weise ist dies ein weiterer Backtracking-Ansatz, der noch weiter geht, um die Tatsache auszunutzen, dass wir nur maximale Cliquen finden wollen. Schließlich, basierend auf Beobachtungen über die Eigenschaften biologischer Graphen, stellen wir die Konzepte maximale Clique-Covers und essentielle Vertex-Sets vor und wenden sie an, um die Laufzeit von Backtracking-Algorithmen signifikant zu verbessern.

Grundlegendes Backtracking

Die bahnbrechende Publikation maximal clique beschreibt zwei Algorithmen. Eine detaillierte Präsentation der zweiten, die eine verbesserte Version der ersten ist, wird bereitgestellt. Es ist diese zweite, effizientere Methode, die wir implementieren und testen. Wir werden es hier als grundlegendes Backtracking bezeichnen. Alle maximalen Cliquen werden mit einem Tiefensuchbaum-Traversal aufgezählt. Als primäre Datenstrukturen werden drei globale Sätze von Vertices verwendet: COMPSUB, CANDIDATES und NOT . COMPSUB enthält die Scheitelpunkte in der aktuellen Clique und ist anfangs leer. CANDIDATES enthält unerforschte Scheitelpunkte, die die aktuelle Clique erweitern können, und enthält zunächst alle Scheitelpunkte im Diagramm. NOT enthält erkundete Scheitelpunkte, die die aktuelle Clique nicht erweitern können, und ist anfangs leer. Jeder rekursive Aufruf führt drei Schritte aus:

• Wählen Sie einen Scheitelpunkt v in KANDIDATEN aus und verschieben Sie ihn nach COMPSUB.

• Entfernen Sie alle Scheitelpunkte, die nicht an v angrenzen, von beiden KANDIDATEN und NICHT. An diesem Punkt, wenn beide KANDIDATEN leer sind und NICHT, dann ist COMPSUB eine maximale Clique. Wenn ja, geben Sie COMPSUB als maximalen cique aus und fahren Sie mit dem nächsten Schritt fort. Wenn nicht, rufen Sie den vorherigen Schritt rekursiv auf.

• Verschieben Sie v von COMPSUB nach NOT .

Beachten Sie, dass NOT verwendet wird, um zu verhindern, dass doppelte maximale Cliquen generiert werden. Der Suchbaum kann beschnitten werden, indem ein Zweig vorzeitig beendet wird, wenn ein Scheitelpunkt von NICHT mit allen Scheitelpunkten von KANDIDATEN verbunden ist.

Scheitelpunkte werden so ausgewählt, dass dieser Schnitt so schnell wie möglich erfolgt. Wir lassen die Details weg, da sie für unsere Änderungen des Algorithmus nicht relevant sind.

Die Speicheranforderungen von Basic Backtracking sind relativ bescheiden. Es müssen keine Informationen über frühere maximale Cliquen gespeichert werden. Bei den Verbesserungen, die wir testen werden, konzentrieren wir uns auf die Geschwindigkeit, verbessern aber auch die Speichernutzung. Daher sind solche Einschränkungen für keine unserer getesteten Methoden unerschwinglich. In einigen Umgebungen kann die Speichernutzung jedoch extrem sein. Wir verweisen den interessierten Leser auf .

Unsere grundlegende Backtracking-Implementierung dient als erste Benchmark, auf der wir nun versuchen können, uns zu verbessern.

Eine einzelne maximale Clique finden

Wir verwenden den Begriff Maximum Clique Finder (MCF), um die Software zu bezeichnen, die wir implementiert und verfeinert haben, um eine einzelne Clique der größten Größe zu finden . MCF verwendet eine Reihe von Vorverarbeitungsregeln zusammen mit einer Verzweigungsstrategie, die den bekannten FPT-Ansatz für die Scheitelpunktabdeckung widerspiegelt . Es ruft zuerst eine einfache gierige Heuristik auf, um schnell eine einigermaßen große Clique zu finden. Diese Clique wird dann für die Vorverarbeitung verwendet, da sie die maximale Clique-Größe unterschränkt. Diese beiden Scheitelpunkte bilden eine anfängliche Clique C , die dann iterativ erweitert wird, indem der Scheitelpunkt höchsten Grades neben ganz C ausgewählt wird. Da | C | eine untere Grenze für die maximale Clique-Größe ist, können alle Scheitelpunkte mit einem Grad kleiner als | C – 1 / dauerhaft aus dem ursprünglichen Diagramm entfernt werden. Als nächstes werden alle Eckpunkte mit dem Grad n – 1 vorübergehend aus dem Diagramm entfernt, aber in einer Liste beibehalten, da sie Teil einer maximalen Clique sein müssen. MCF nutzt eine neuartige Form der Farbvorverarbeitung , zuvor verwendet, um die Verzweigung zu leiten. Diese Form der Vorverarbeitung versucht, den Graphen wie folgt zu reduzieren. Bei einer bekannten Untergrenze k für die Größe der maximalen Clique wenden wir für jeden Scheitelpunkt v eine schnelle gierige Färbung auf v und seine Nachbarn an. Wenn diese Eckpunkte mit weniger als k Farben gefärbt werden können, kann v nicht Teil einer maximalen Clique sein und wird aus dem Diagramm entfernt. Sobald der Graph so reduziert ist, verwendet MCF die rekursive Standardverzweigung auf Scheitelpunkten, wobei jeder Zweig davon ausgeht, dass der Scheitelpunkt entweder in der maximalen Clique liegt oder nicht.

Intelligentes Backtracking

Angesichts der relativen Effektivität, mit der wir eine einzelne maximale Clique finden können, erscheint es logisch zu überlegen, ob die Kenntnis der Größe dieser Clique hilfreich sein kann, um alle maximalen Cliquen aufzuzählen. Wie sich herausstellt, führt die Kenntnis der maximalen Cliquengröße k zu einer kleinen, unkomplizierten Änderung des grundlegenden Backtracking-Algorithmus. Insbesondere prüfen wir an jedem Knoten im Suchbaum, ob weniger als k Scheitelpunkte in der Vereinigung von COMPSUB und KANDIDATEN vorhanden sind. Wenn ja, kann dieser Zweig nicht zu einer Clique der Größe k führen, und so kehren wir zurück. Siehe Abbildung 2. Während die Modifikation geringfügig erscheinen mag, kann das resultierende Beschneiden des Suchbaums zu einer erheblichen Verringerung des Suchraums führen. Zusätzlich zu dieser geringfügigen Änderung der Verzweigung wenden wir die zuvor beschriebene Farbvorverarbeitung an, um das Diagramm zu reduzieren, bevor wir es an den verbesserten Backtracking-Algorithmus senden. Farbvorverarbeitung kombiniert mit der geringfügigen Verzweigungsänderung, die wir intelligentes Backtracking nennen.

Paramaterisierte Enumeration

Da MCF eine Vertex-Verzweigungsstrategie verwendet, haben wir untersucht, ob sie geändert werden kann, um nicht nur eine, sondern alle maximalen Cliquen aufzulisten. Es stellt sich heraus, dass sich MCF auch für eine einfache Modifikation eignet, die zur Aufzählung aller maximalen Cliquen führt. Die Modifikation besteht einfach darin, eine globale Liste aller bisher gefundenen Cliquen der größten Größe zu führen. Wenn eine größere maximale Clique gefunden wird, wird die Liste geleert und aktualisiert, um nur die neue maximale Clique zu enthalten. Wenn der Suchraum erschöpft ist, wird die Liste der maximalen Cliquen ausgegeben.

Wir müssen jedoch besonders darauf achten, dass bestimmte Vorverarbeitungsregeln, die beim Interleaving verwendet werden, nicht mehr gültig sind. Betrachten Sie zum Beispiel die Entfernung eines Blattscheitelpunkts. Das Clique-Analogon besteht darin, einen Scheitelpunkt mit dem Grad n – 2 zu finden und seinen einsamen Nichtnachbarn zu entfernen. Diese Regel geht offensichtlich davon aus, dass nur eine einzige maximale Clique gewünscht wird, da sie jede Clique in Abhängigkeit vom verworfenen Scheitelpunkt ignoriert. Daher muss diese spezielle Vorverarbeitungsregel weggelassen werden, sobald die Verzweigung begonnen hat.

Maximum Clique covers

Wenn wir MCF als eine Blackbox-Unterroutine betrachten, die wiederholt aufgerufen werden kann, kann sie in einem einfachen gierigen Algorithmus zur Berechnung eines maximalen Satzes von disjunkten maximalen Cliquen verwendet werden. Wir berechnen lediglich eine maximale Clique, entfernen sie aus dem Diagramm und iterieren, bis die Größe einer maximalen Clique abnimmt. Um die Vorteile der Berechnung einer solchen Menge zu untersuchen, stellen wir den folgenden Begriff vor:

Definition 1 Eine maximale Clique-Abdeckung von G = (V, E) ist eine Menge V‘ ⊆ V mit der Eigenschaft, dass jede maximale Clique von G einen Scheitelpunkt in der Abdeckung enthält.

Die Vereinigung aller Scheitelpunkte, die in einer maximalen Menge von disjunkten maximalen Cliquen enthalten sind, ist natürlich eine maximale Clique-Abdeckung (fortan MCC), da sich alle maximalen Cliquen mit einer solchen Menge überlappen müssen. Dies führt zu einem nützlichen Reduktionsalgorithmus. Jeder Scheitelpunkt, der nicht an mindestens ein Mitglied eines MCC angrenzt, kann sich nicht in einer maximalen Clique befinden und kann daher entfernt werden.

In der Praxis stellen wir fest, dass die Anwendung von MCC vor den früheren Backtracking-Algorithmen nur marginale Verbesserungen bringt. Das Konzept von MCC führt jedoch zu einem viel leistungsfähigeren Ansatz, der auf einzelnen Eckpunkten basiert. Da jede von MCC vorgenommene Verbesserung durch den nächsten Ansatz subsumiert wird, testen wir MCC nicht selbst.

Wesentliche Scheitelpunktsätze

Unsere Untersuchung des MCC-Algorithmus ergab, dass er die Größe des Diagramms normalerweise nicht stärker reduziert als die bereits in MCF integrierten Vorverarbeitungsregeln. Zum Beispiel findet MCF bereits schnell eine untere Grenze für die maximale Clique-Größe und entfernt jeden Scheitelpunkt mit einem niedrigeren Grad als dieser Grenze. Bei näherer Betrachtung stellten wir jedoch fest, dass für 74 von 75 Diagrammen, die wir ursprünglich für die Konferenzversion dieses Papiers getestet hatten, nur eine Clique in einem MCC benötigt wurde. Das heißt, eine maximale Clique deckte alle anderen maximalen Cliquen ab. Und in unserem aktuellen Testbed von 100 Graphen reicht in jedem Fall eine einzige maximale Clique für einen MCC. In der Tat fällt dies eng mit unserer Erfahrung zusammen, in der wir typischerweise hohe Überschneidungen zwischen großen Cliquen in den transkriptomischen Graphen sehen, denen wir regelmäßig begegnen. Basierend auf dieser Beobachtung werden wir nun das Konzept von MCC verfeinern. Anstatt maximale Cliquen mit Cliquen abzudecken, decken wir maximale Cliquen mit einzelnen Eckpunkten ab.

Wir definieren einen wesentlichen Scheitelpunkt als einen, der in jeder maximalen Clique enthalten ist. Natürlich ist es möglich, dass ein gegebener Graph keinen solchen Scheitelpunkt hat, selbst wenn er viele überlappende maximale Cliquen enthält. Empirische Tests großer transkriptomischer Graphen zeigen jedoch, dass eine überwältigende Anzahl zahlreiche wesentliche Eckpunkte enthält. Und um die Grafik zu reduzieren, reicht sogar eine aus. Ein wesentlicher Scheitelpunkt hat das Potenzial, äußerst hilfreich zu sein, da er es uns ermöglicht, alle seine Nichtnachbarn zu entfernen. Wir wenden die folgende Beobachtung an: Für jeden Graphen G, ω (G) > ω (G / v) genau dann, wenn v alle maximalen Cliquen abdeckt, wobei ω (G) die maximale Cliquengröße von G ist.

Wir definieren eine wesentliche Menge als die Menge aller wesentlichen Eckpunkte. Der Essential Set (ES)-Algorithmus, wie in Abbildung 3 beschrieben, findet alle wesentlichen Eckpunkte in einem Diagramm. Anschließend wird das Diagramm reduziert, indem für jeden wesentlichen Scheitelpunkt alle Nichtnachbarn dieses Scheitelpunkts entfernt werden. Der ES-Algorithmus kann in Verbindung mit jedem der Backtracking-MCE-Algorithmen oder sogar vor jedem Algorithmus ausgeführt werden, der MCE auf irgendeine Weise ausführt, da seine Ausgabe ein reduzierter Graph ist, der immer noch alle maximalen Cliquen aus dem ursprünglichen Graph enthält. Wie unsere Tests zeigen, kann die Laufzeitverbesserung durch den ES-Algorithmus dramatisch sein.

Implementierung

Wir haben alle Algorithmen entweder in C oder C ++ implementiert. Der Code wurde mit dem Compiler GCC 4.4.3 auf dem Betriebssystem Ubuntu Linux Version 10.04.2 sowie mit dem Compiler GCC 3.3.5 unter Debian Linux Version 3.1 kompiliert. Alle Timings wurden in der letztgenannten Debian-Umgebung auf dedizierten Knoten eines Clusters durchgeführt, um sicherzustellen, dass die Timings von gleichzeitigen Prozessen nicht beeinflusst werden. Jeder Knoten hatte einen Dual-Core-Intel Xeon-Prozessor mit 3,20 GHz und 4 GB Hauptspeicher.

Testen

In der Konferenzversion dieses Artikels haben wir drei verschiedene Datensätze mit jeweils 25 Schwellenwerten verwendet, um insgesamt 75 Diagramme abzuleiten, anhand derer wir unsere algorithmischen Verbesserungen testen können. Während diese Grafiken sicherlich als erster Proof-of-Concept ausreichten, könnten zwei Bedenken in Bezug auf sie geäußert werden. Erstens könnte man argumentieren, dass drei Datensätze trotz der großen Anzahl von Schwellenwerten keine ausreichend große Stichprobengröße sind, um einen echten Eindruck von der Gesamtnatur transkriptomischer Daten oder der allgemeinen Wirksamkeit einer algorithmischen Verbesserung bei solchen Daten zu vermitteln. Und zweitens, da die drei Datensätze proprietär und nicht öffentlich zugänglich sind, waren die Ergebnisse nicht so leicht reproduzierbar, wie sie es sonst gewesen wären. De-identifizierte Versionen zu erhalten, war zwar machbar, aber ein unnötiges Hindernis für die Reproduzierbarkeit.

Wir gehen hier auf solche Bedenken ein, indem wir eine neue Suite transkriptomischer Graphen erstellen, an denen wir unsere algorithmischen Verbesserungen testen können. Die Suite besteht aus Grafiken, die aus 25 Datensätzen stammen, die aus dem Gene Expression Omnibus (GEO) , einem öffentlich zugänglichen Repository, stammen. Für jeden Datensatz wurden Diagramme mit vier verschiedenen Schwellenwerten für insgesamt 100 Diagramme erstellt. Die Datensätze wurden ausgewählt, um eine einigermaßen vielfältige Stichprobe von experimentellem Typ, Spezies und mRNA-Microarray-Chip-Typ bereitzustellen. Sie decken 8 verschiedene Arten und eine Reihe verschiedener experimenteller Bedingungen wie Zeitreihen, Stamm, Dosis und Patient ab. Da unsere Graphen von Schwellwertkorrelationswerten abgeleitet sind, haben wir jeden Datensatz mit weniger als 12 Bedingungen von der Betrachtung ausgeschlossen. Schwellwertkorrelationen, die mit so wenigen Bedingungen berechnet werden, können zu inakzeptabel hohen Raten von falsch positiven und falsch negativen Ergebnissen führen. Die Anzahl der Bedingungen reicht von einem Tief von 12 bis zu einem Hoch von 153. Neun der Datensätze waren nicht logtransformiert worden, in diesem Fall haben wir eine Logtransformation durchgeführt. Vier der Datensätze enthielten fehlende Werte; In diesen Fällen verwendeten wir Korrelations-p-Werte anstelle von Korrelationen für den Schwellenwert. Eine Auflistung der zum Testen verwendeten Geodatensätze finden Sie in Tabelle 1.

Aus den Expressionsdaten konstruierten wir zunächst gewichtete Graphen, in denen Scheitelpunkte Sonden darstellten und Kantengewichte Pearson-Korrelationskoeffizienten waren, die unter experimentellen Bedingungen berechnet wurden. Wir wandelten dann die gewichteten Graphen in ungewichtete Graphen um, indem wir nur die Kanten beibehielten, deren Gewichte bei oder über einem ausgewählten Schwellenwert lagen, t. Für jeden Datensatz wählten wir vier Werte für t. Alle Größen- / Dichtewerte lagen innerhalb des Spektrums, das typischerweise in unserer Arbeit mit biologischen Datensätzen zu sehen ist. Der kleinste Graph hatte 3.828 Eckpunkte und 310.380 Kanten; Der größte hatte 44.563 Eckpunkte und 2.052.228 Kanten.

Die Anzahl der maximalen Cliquen für die Graphen in unserem Testbed lag zwischen 8 und 74486. Wie in unserem vorherigen Testbed zu sehen war, gab es kein erkennbares Muster basierend auf der Diagrammgröße oder -dichte. Man könnte fragen, warum es eine so große, unvorhersehbare Variabilität gibt. Es stellt sich heraus, dass die Anzahl der maximalen Cliquen extrem empfindlich auf kleine Änderungen in der Grafik reagieren kann. Selbst die Modifikation einer einzelnen Kante kann einen großen Effekt haben. Betrachten Sie zum Beispiel ein Diagramm mit einer eindeutigen maximalen Clique der Größe k zusammen mit einer Vielzahl von disjunkten Cliquen der Größe k – 1. Die Entfernung von nur einer Kante von der größten Clique kann nun zu vielen maximalen Cliquen der Größe k – 1 führen. Kantenzusatz kann natürlich ähnliche Effekte haben. Ein anschauliches Beispiel finden Sie in Abbildung 4.

Für jeden Algorithmus in jedem Diagramm haben wir Timings auf einem dedizierten Knoten eines Clusters durchgeführt, um Störungen durch andere Prozesse zu vermeiden. Wenn der Algorithmus nicht innerhalb von 24 Stunden abgeschlossen wurde, wurde er angehalten und das Diagramm galt als nicht gelöst. Wir haben Schwellenwerte gewählt, um die Laufzeiten der Diagramme auf die fünf von uns getesteten Algorithmen zu verteilen. Der größte (kleinste im Falle des Korrelations-p-Wertes) Schwellenwert wurde so gewählt, dass eine Mehrheit der Algorithmen, wenn nicht alle, den Graphen lösten. Der kleinste (größte im Falle des Korrelations-p-Wertes) Schwellenwert wurde so gewählt, dass mindestens einer der Algorithmen, aber nicht alle, den Graphen lösten.

In jedem Diagramm haben wir die Leistung von Basic Backtracking, Intelligent Backtracking und Paramaterized MC zeitlich festgelegt. Wir haben dann die Diagramme mit ES reduziert und mit intelligentem Backtracking und parametrisiertem MC erneut getestet. Wie erwartet erwies sich das grundlegende Backtracking als nicht wettbewerbsfähig. Sowohl intelligentes Backtracking als auch parametrisiertes MC zeigten eine deutliche, oft dramatische Verbesserung gegenüber dem grundlegenden Backtracking. Abbildung 5 zeigt die Laufzeiten jeder der fünf Methoden auf allen 100 Testgraphen. Bei einigen der einfacheren Diagramme, deren Lösung weniger als drei Minuten dauerte, führte der Overhead von ES tatsächlich zu einer geringfügigen Erhöhung der Gesamtlaufzeit. In den schwierigeren Fällen zeigte sich jedoch der wahre Vorteil, dass die Laufzeit um eine Größenordnung oder mehr reduziert wurde. Und in allen Fällen, in denen zwei oder weniger Algorithmen den Graphen lösten, war der Algorithmus entweder ES mit intelligentem Backtracking, ES mit parametrisiertem MC oder beides.