het probleem met maximale clique-opsomming: algoritmen, toepassingen en implementaties

met behulp van het algoritme voor maximale clique-opsomming vanwege Bron en Kerbosch als benchmark, hebben we drie algoritmische verbeteringen ontworpen, geïmplementeerd en uitgebreid getest, de laatste gebaseerd op waarnemingen over de aard van grafieken geproduceerd door transcriptomische gegevens. Samen met het beschrijven van deze verbeteringen, zullen we onze bestaande tool beschrijven voor het vinden van een enkele maximale kliek, gebaseerd op de theorie van fixed-parameter tractability (FPT) . Een dergelijke tool is essentieel voor alle drie de verbeteringen, omdat de eerste twee vertrouwen op kennis van de maximale kliek grootte, en de laatste gebruikt de maximale kliek vinden tool als een subroutine. Alle codes zijn geschreven in C / C++ en gecompileerd in Linux. Voor het testen gebruiken we 100 grafieken afgeleid van 25 verschillende datasets die publiekelijk beschikbaar zijn op GEO. We concentreren ons op transcriptomische gegevens, gezien de overvloed ervan, en vermijd synthetische gegevens, nadat we lang geleden hebben geleerd dat effectieve algoritmen voor de een weinig invloed hebben op de ander. (De pathologische matchings die in voor vertex dekking worden genoteerd kunnen tot kliek worden uitgebreid, maar ook zij zijn natuurlijk enorm irrelevant voor echte gegevens. In een poging om de prestaties te verbeteren, onderzoeken we de structuur van transcriptomische grafieken en onderzoeken we het begrip van maximale kliek covers en essentiële vertex sets. Inderdaad, we vinden dat we met de juiste voorbewerking in staat zijn om algoritmen af te stemmen op de soorten gegevens die we routinematig tegenkomen, en dat we nu gevallen kunnen oplossen die eerder als onaantastbaar werden beschouwd.

algoritmen

in de volgende secties beschrijven we elk van de MCE-algoritmen die we hebben geïmplementeerd en getest. Het eerste is het algoritme van Bron en Kerbosch, dat we Basic Backtracking noemen en als benchmark gebruiken. Aangezien al onze volgende verbeteringen gebruik maken van een algoritme dat een enkele maximale kliek vindt, beschrijven we vervolgens onze bestaande tool, genaamd Maximum kliek Finder (MCF), die precies dat doet. Vervolgens Wijzigen we het basis Backtracking-algoritme om te profiteren van het feit dat we alleen de maximale klieken willen vinden en snel de maximale kliekgrootte kunnen berekenen. We noemen deze aanpak Intelligent Backtracking, omdat het actief vroegtijdig terugkeert van takken die niet zullen leiden tot een maximale kliek. Vervolgens Wijzigen we MCF zelf om alle maximale kliekjes op te sommen, een benadering die we geparametriseerde maximale kliek noemen, of geparametriseerde MC. In zekere zin is dit weer een terugtrekkende aanpak die nog verder gaat om het feit dat we alleen maar maximale kliekjes willen vinden. Tot slot, op basis van waarnemingen over de eigenschappen van biologische grafieken, introduceren we de concepten maximale kliek covers en essentiële vertex sets, en passen ze toe om de runtime van backtracking algoritmen aanzienlijk te verbeteren.

basic backtracking

de rudimentaire maximale kliekpublicatie beschrijft twee algoritmen. Een gedetailleerde presentatie van de tweede, dat is een verbeterde versie van de eerste, wordt verstrekt. Het is deze tweede, efficiëntere methode die we implementeren en testen. Wij zullen het hier als fundamentele terugslag bestempelen. Alle maximale kliekjes worden opgesomd met een depth-first search tree traversal. De gebruikte primaire datastructuren zijn drie globale sets van hoekpunten: COMPSUB, kandidaten en niet. COMPSUB bevat de hoekpunten in de huidige kliek, en is aanvankelijk leeg. CANDIDATES bevat onontgonnen hoekpunten die de huidige kliek kunnen uitbreiden, en bevat aanvankelijk alle hoekpunten in de grafiek. Bevat geen verkende hoekpunten die de huidige kliek niet kunnen uitbreiden, en is aanvankelijk leeg. Elke recursieve aanroep voert drie stappen uit:

• selecteer een vertex v in kandidaten en verplaats het naar COMPSUB.

• Verwijder alle hoekpunten niet grenzend aan v van beide kandidaten en niet. Op dit punt, als beide kandidaten en niet leeg zijn, dan is COMPSUB een maximale kliek. Als dat zo is, output COMPSUB als een maximale cique en ga verder met de volgende stap. Zo niet, roep dan recursief de vorige stap aan.

• Verplaats v van COMPSUB naar niet.

merk op dat niet wordt gebruikt om te voorkomen dat dubbele maximale kliekjes worden gegenereerd. De zoekboom kan worden gesnoeid door een tak vroeg te beëindigen als een hoekpunt van niet is verbonden met alle hoekpunten van kandidaten.

hoekpunten worden zodanig geselecteerd dat deze snoei zo snel mogelijk plaatsvindt. We laten de details weg omdat ze niet relevant zijn voor onze wijzigingen van het algoritme.

de opslagbehoeften voor Basistracking zijn relatief bescheiden. Er hoeft geen informatie over eerdere maximale klieken bewaard te worden. In de verbeteringen die we zullen testen, richten we ons op snelheid, maar verbeteren ook het geheugengebruik. Dus, dergelijke beperkingen zijn in geen geval prohibitief voor een van onze geteste methoden. Niettemin, in sommige omgevingen, geheugengebruik kan extreem zijn. We verwijzen de geïnteresseerde lezer naar .

onze basis implementatie van Backtracking dient als een eerste benchmark waarop we nu kunnen proberen te verbeteren.

het vinden van een enkele maximale kliek

we gebruiken de term Maximum kliek Finder (MCF) om de software aan te duiden die we hebben geà mplementeerd en verfijnd voor het vinden van een enkele kliek van de grootste grootte . MCF maakt gebruik van een suite van preprocessing regels samen met een vertakking strategie die de bekende FPT benadering van vertex dekking weerspiegelt . Het roept eerst een eenvoudige hebzuchtige heurist op om snel een redelijk grote kliek te vinden. Deze kliek wordt dan gebruikt voor voorbewerking, omdat het een ondergrens op de maximale kliek grootte. De heuristische werken door de hoogste graad vertex v te kiezen, en vervolgens de hoogste graad buur van V te kiezen.deze twee hoekpunten vormen een initiële kliek C, die vervolgens iteratief wordt uitgebreid door de hoogste graad vertex naast alle C te kiezen. Het proces gaat door totdat er buiten C. Geen hoekpunten meer bestaan omdat |C| een ondergrens is op de maximale kliekgrootte, kunnen alle hoekpunten met een graad kleiner dan |C – 1| permanent uit de oorspronkelijke grafiek worden verwijderd. Vervolgens worden alle hoekpunten met graad n – 1 tijdelijk verwijderd uit de grafiek, maar behouden in een lijst omdat ze deel moeten uitmaken van een maximale kliek. MCF exploiteert een nieuwe vorm van kleur voorbewerking, eerder gebruikt in om vertakking te begeleiden. Deze vorm van voorbewerking probeert de grafiek als volgt te verminderen. Gegeven een bekende ondergrens k op de grootte van de maximale kliek, voor elke hoekpunt v passen we snel hebzuchtige kleuren toe op v en zijn buren. Als deze hoekpunten kunnen worden gekleurd met minder dan k kleuren, dan v kan geen deel uitmaken van een maximale kliek en wordt verwijderd uit de grafiek. Zodra de grafiek zo is gereduceerd, gebruikt MCF standaard recursieve vertakkingen op hoekpunten, waarbij elke tak ervan uitgaat dat de vertex ofwel wel of niet in de maximale kliek zit.

Intelligent backtracking

gezien de relatieve effectiviteit waarmee we een enkele maximale kliek kunnen vinden, lijkt het logisch om te overwegen of kennis van de grootte van die kliek nuttig kan zijn bij het opsommen van alle maximale kliek. Het blijkt dat kennis van de maximale kliek k leidt tot een kleine, eenvoudige verandering in de basis Backtracking algoritme. Specifiek, bij elk knooppunt in de zoekboom controleren we of er minder dan k hoekpunten zijn in de Vereniging van COMPSUB en kandidaten. Als dat zo is, kan die tak niet leiden tot een kliek van grootte k, en dus keren we terug. Zie Figuur 2. Hoewel de wijziging misschien klein lijkt, kan de resulterende snoei van de zoekboom leiden tot een aanzienlijke vermindering van de zoekruimte. Naast deze kleine verandering in vertakking passen we kleurvoorverwerking toe zoals eerder beschreven om de grafiek te verminderen voordat we deze naar het verbeterde backtracking-algoritme sturen. Kleur voorbewerking gecombineerd met de kleine vertakking verandering noemen we intelligente Backtracking.

Paramaterized enumeration

gegeven het feit dat MCF een vertex branching strategie gebruikt, hebben we onderzocht of het kon worden aangepast om niet slechts één, maar alle maximale klieken op te sommen. Het blijkt dat MCF zich ook leent voor een rechttoe rechtaan modificatie die resulteert in het opsommen van alle maximale kliekjes. De wijziging is gewoon om een globale lijst van alle kliekjes van de grootste grootte tot nu toe gevonden te houden. Wanneer een grotere maximale kliek wordt gevonden, wordt de lijst gespoeld en ververst om alleen de nieuwe maximale kliek te bevatten. Wanneer de zoekruimte is uitgeput, wordt de lijst met maximale kliekjes uitgevoerd.

er dient echter op te worden gelet dat bepaalde regels voor de voorbewerking die tijdens de interleaving worden toegepast, niet meer geldig zijn. Denk bijvoorbeeld aan het verwijderen van een bladpunt. De kliek analoog is om een vertex met graad n – 2 te vinden en zijn eenzame niet-buurman te verwijderen. Deze regel gaat ervan uit dat slechts een enkele maximale kliek gewenst is, omdat het elke kliek negeert afhankelijk van de afgedankte Top. Daarom moet deze specifieke voorbewerkingsregel worden weggelaten zodra de vertakking is begonnen.

maximale kliek dekt

als we MCF zien als een black box-subroutine die herhaaldelijk kan worden aangeroepen, kan het worden gebruikt in een eenvoudig hebzuchtig algoritme voor het berekenen van een maximale set van disjuncte maximale kliekjes. We berekenen alleen een maximale kliek, verwijderen deze uit de grafiek en herhalen totdat de grootte van een maximale kliek afneemt. Om de voordelen van het berekenen van een dergelijke verzameling te onderzoeken, introduceren we het volgende begrip:

definitie 1 een maximale kliek cover van G = (V, E) is een verzameling V’ ⊆ V met de eigenschap dat elke maximale kliek van G een punt in de cover bevat.

de Vereniging van alle hoekpunten in een maximale verzameling van disjuncte maximale klieken is natuurlijk een maximale kliekdekking (voortaan MCC), omdat alle maximale klieken met een dergelijke verzameling moeten overlappen. Dit leidt tot een nuttig reductiealgoritme. Een vertex die niet grenst aan ten minste één lid van een MCC kan niet in een maximale kliek zijn, en kan dus worden verwijderd.

in de praktijk blijkt dat het toepassen van MCC vóór de eerdere backtracking-algoritmen slechts een marginale verbetering oplevert. Het concept van MCC leidt echter tot een veel krachtiger benadering op basis van individuele hoekpunten. Aangezien elke verbetering door MCC wordt gesubsumeerd door de next approach, testen we MCC niet op zichzelf.

essentiële vertexverzamelingen

ons onderzoek naar het MCC-algoritme toonde aan dat het de grootte van de grafiek doorgaans niet meer vermindert dan de regels voor voorbewerking die al in MCF zijn opgenomen. MCF vindt bijvoorbeeld al snel een ondergrens op de maximale kliekgrootte en verwijdert alle vertex met een graad lager dan deze grens. Bij nader onderzoek, echter, vonden we dat Voor 74 van 75 grafieken die we in eerste instantie getest voor de conferentie versie van dit document, slechts één kliek nodig was in een MCC. Dat wil zeggen, één maximale kliek bedekte alle andere maximale kliek. En in onze huidige testbed van 100 grafieken, in elk geval een enkele maximale kliek volstaat voor een MCC. In feite valt dit nauw samen met onze ervaring, waarin we typisch hoge overlap zien tussen grote kliekjes in de transcriptomische grafieken die we regelmatig tegenkomen. Op basis van deze constatering zullen we nu het concept MCC verfijnen. In plaats van de maximale klieken met klieken te bedekken, bedekken we de maximale klieken met individuele hoekpunten.

we definiëren een essentieel punt als een punt dat zich in elke maximale kliek bevindt. Natuurlijk is het mogelijk dat een gegeven grafiek niet zo ‘ n top heeft, zelfs als het veel overlappende maximale kliekjes bevat. Maar empirisch testen van grote transcriptomische grafieken toont aan dat een overweldigend aantal talrijke essentiële hoekpunten bevat. En om de grafiek te verminderen, is zelfs één voldoende. Een essentieel punt heeft het potentieel om zeer nuttig te zijn, omdat het ons in staat stelt om al zijn niet-buren te verwijderen. We gebruiken de volgende waarneming: voor elke grafiek g, ω(g) > ω(G/v) dan en alleen als v Alle maximale kliekjes omvat, waarbij ω (G) de maximale kliekgrootte van G.

is, definiëren we een essentiële verzameling als de verzameling van alle essentiële hoekpunten. Het algoritme essentiële verzameling (ES), zoals beschreven in Figuur 3, vindt alle essentiële hoekpunten in een grafiek. Het reduceert vervolgens de grafiek door voor elk essentieel vertex alle niet-buren van dat vertex te verwijderen. Het Es-algoritme kan worden uitgevoerd in combinatie met een van de backtracking MCE-algoritmen, of zelfs voorafgaand aan een algoritme dat MCE doet door elke methode, omdat de output een gereduceerde grafiek is die nog steeds alle maximale kliekjes van de oorspronkelijke grafiek bevat. Zoals uit onze tests blijkt, kan de runtime-verbetering van het Es-algoritme dramatisch zijn.

implementatie

we hebben alle algoritmen geïmplementeerd in C of C++. De code werd gecompileerd met behulp van de GCC 4.4.3 compiler op het Ubuntu Linux versie 10.04.2 besturingssysteem en de GCC 3.3.5 compiler onder Debian Linux versie 3.1. Alle timings werden uitgevoerd in de laatste Debian-omgeving op speciale knooppunten van een cluster om ervoor te zorgen dat de timings van gelijktijdige processen niet worden beïnvloed. Elk knooppunt had een dual-core Intel Xeon processor die op 3,20 GHz en 4 GB van het hoofdgeheugen.

testen

in de conference version van dit paper gebruikten we drie verschillende datasets met elk 25 drempels om in totaal 75 grafieken af te leiden waarop we onze algoritmische verbeteringen konden testen. Hoewel deze grafieken zeker voldeden als een eerste bewijs van concept, kunnen er twee zorgen over worden geuit. Ten eerste zou men kunnen stellen dat drie datasets niet een voldoende grote steekproefomvang zijn om een echt gevoel van de algemene aard van transcriptomische gegevens of de algemene effectiviteit van een algoritmische verbetering op dergelijke gegevens te geven, ondanks het grote aantal drempels. En ten tweede, omdat de drie datasets propriëtair zijn en niet openbaar beschikbaar, waren de resultaten niet zo gemakkelijk reproduceerbaar als ze anders zouden zijn geweest. Het verkrijgen van gedeïdentificeerde versies, hoewel haalbaar, was een onnodige obtacle voor reproduceerbaarheid.

we pakken deze problemen hier aan door een nieuwe reeks transcriptomische grafieken te creëren waarop we onze algoritmische verbeteringen kunnen testen. De suite bestaat uit grafieken afgeleid van 25 datasets verkregen uit de genexpressie Omnibus (GEO) , een publiek toegankelijke repository. Voor elke dataset werden grafieken gemaakt op vier verschillende drempels, voor een totaal van 100 grafieken. De datasets werden geselecteerd om een redelijk diverse bemonstering van experimenteel type, species, en mRNA microarray spaandertype te verstrekken. Ze bestrijken 8 verschillende soorten en een aantal verschillende experimentele omstandigheden zoals tijdreeksen, stam, dosis en patiënt. Omdat onze grafieken zijn afgeleid van drempelcorrelatiewaarden, hebben we elke dataset met minder dan 12 voorwaarden uitgesloten. Drempelcorrelaties berekend met behulp van zo weinig omstandigheden kunnen onaanvaardbaar hoge percentages valse positieven en valse negatieven veroorzaken. Het aantal omstandigheden varieert van een laag van 12 tot een hoog van 153. Negen van de datasets waren niet log-getransformeerd, in welk geval we log-transformatie hebben uitgevoerd. Vier van de datasets bevatten ontbrekende waarden; in deze gevallen gebruikten we correlatie p-waarden in plaats van correlaties voor de drempel. Zie Tabel 1 voor een lijst van de GEO-datasets die voor het testen zijn gebruikt.

uit de expressiegegevens construeerden we eerst gewogen grafieken waarin hoekpunten sondes representeerden en randgewichten Pearson correlatiecoëfficiënten werden berekend over experimentele omstandigheden. Vervolgens hebben we de gewogen grafieken omgezet in ongewogen grafieken door alleen die randen te behouden waarvan de gewichten op of boven een bepaalde gekozen drempel lagen, t. voor elke dataset kozen we vier waarden voor t. Alle grootte/dichtheidswaarden lagen binnen het spectrum dat we typisch zien in ons werk met biologische datasets. De kleinste grafiek had 3.828 hoekpunten en 310.380 randen; de grootste had 44.563 hoekpunten en 2.052.228 randen.

het aantal maximale kliekjes voor de grafieken in onze proefbank varieerde van 8 tot 74486. Zoals Gezien met ons vorige testbed, was er geen waarneembaar patroon gebaseerd op grafiekgrootte of dichtheid. Je zou je kunnen afvragen waarom er zo ‘ n grote, onvoorspelbare variabiliteit is. Het blijkt dat het aantal maximale kliekjes extreem gevoelig kan zijn voor kleine veranderingen in de grafiek. Zelfs de wijziging van een enkele rand kan een enorm effect hebben. Denk bijvoorbeeld aan een grafiek met een unieke maximale kliek van maat k, samen met een groot aantal disjuncte kliek van maat k – 1. Het verwijderen van slechts één rand van wat de grootste kliek was kan nu resulteren in veel maximale kliekjes van grootte k – 1. Rand toevoeging kan natuurlijk soortgelijke effecten hebben. Zie Figuur 4 voor een illustratief voorbeeld.

voor elk algoritme op elke grafiek hebben we timings uitgevoerd op een speciaal knooppunt van een cluster om interferentie van andere processen te voorkomen. Als het algoritme niet binnen 24 uur werd voltooid, werd het gestopt en werd de grafiek geacht niet te zijn opgelost. We kozen drempels om de looptijd van de grafieken te spreiden over de vijf algoritmen die we testten. De grootste (kleinste in het geval van correlatie p-waarde) drempel werd geselecteerd zodat een meerderheid van de algoritmen, zo niet alle, de grafiek opgelost. De kleinste (grootste in het geval van correlatie p-waarde) drempel werd geselecteerd zodat ten minste een van de algoritmen, maar niet alle, de grafiek opgelost.

op elke grafiek hebben we de prestaties van Basic Backtracking, Intelligent Backtracking en Geparamateriseerd MC getimed. Vervolgens hebben we de grafieken gereduceerd met behulp van ES en opnieuw getest met intelligente Backtracking en geparametreerd MC, in welk geval de runtimes zowel de reductie als de opsomming stap bevatten. Zoals verwacht bleek Backtracking niet concurrerend te zijn. Zowel Intelligent Backtracking als geparametreerd MC vertoonden een duidelijke, vaak dramatische verbetering ten opzichte van Basic Backtracking. Figuur 5 toont de looptijd van elk van de vijf methoden op alle 100 testgrafieken. Op sommige van de gemakkelijkere grafieken, die minder dan drie minuten duren om op te lossen, veroorzaakte de overhead van ES eigenlijk een kleine toename in de totale runtime. Maar in de meer moeilijke gevallen werd het werkelijke voordeel duidelijk, waardoor de looptijd met een orde van grootte of meer werd verminderd. In alle gevallen waarin twee of minder algoritmen de grafiek oplosten, was het algoritme ofwel ES met intelligente Backtracking, ES met geparametriseerde MC, of beide.