the maximum clique enumeration problem: algoritmer, applikasjoner og implementeringer

Ved hjelp av den seminal maximal clique enumeration algoritmen på Grunn Av Bron Og Kerbosch som en benchmark, vi designet, implementert, og grundig testet tre algoritmiske forbedringer, den siste basert på observasjoner om innholdet av grafer produsert av transkriptomic data. Sammen med å beskrive disse forbedringene, vil vi beskrive vårt eksisterende verktøy for å finne en enkelt maksimal klikk, basert på teorien om fast parameter tractability (FPT) . Et slikt verktøy er viktig for alle tre forbedringene, siden de to første er avhengige av kunnskap om maksimal klikkstørrelse, og den siste bruker det maksimale klikkfunnverktøyet som en subrutine. Alle koder er skrevet I C / C++ og kompilert I Linux. For testing bruker vi 100 grafer avledet fra 25 forskjellige datasett som er offentlig tilgjengelige PÅ GEO. Vi konsentrerer oss om transkriptomiske data, gitt sin overflod, og unngår syntetiske data, etter å ha lært for lenge siden at effektive algoritmer for en har liten betydning for den andre. (De patologiske matchingene som er nevnt i for vertex cover kan utvides til clique, men også de er selvsagt enormt irrelevante for ekte data.) I et forsøk på å forbedre ytelsen, undersøker vi strukturen av transkriptomiske grafer og undersøker begrepet maksimale klikkdeksler og essensielle vertex-sett. Faktisk finner vi at med riktig forbehandling er vi i stand til å skreddersy algoritmer til de slags data vi rutinemessig støter på, og at vi nå kan løse forekomster som tidligere ble ansett som utilgjengelige.

Algoritmer

i de følgende avsnittene beskriver vi HVER AV MCE-algoritmene vi implementerte og testet. Den første er algoritmen Til Bron Og Kerbosch, som vi kaller Grunnleggende Backtracking og bruker som referanse. Siden alle våre etterfølgende forbedringer gjør bruk av en algoritme som finner en enkelt maksimal klikk, beskriver vi neste vårt eksisterende verktøy, Kalt Maximum Clique Finder (MCF), som gjør nettopp det. Vi endrer Deretter Den Grunnleggende Backtracking algoritmen for å dra nytte av det faktum at vi bare vil finne de maksimale klikkene og raskt kan beregne maksimal klikkstørrelse. Vi kaller Denne tilnærmingen Intelligent Backtracking, siden den aktivt returnerer tidlig fra grener som ikke vil føre til en maksimal klikk. VI endrer DERETTER MCF selv for å nummerere alle maksimale klikker, en tilnærming vi kaller Parameterisert Maksimal Klikkeller Parameterisert MC. På en måte er dette en annen backtracking tilnærming som går enda lenger for å utnytte det faktum at vi bare ønsker å finne maksimale cliques. Til slutt, basert på observasjoner om egenskapene til biologiske grafer, introduserer vi konseptene maximum clique covers og essential vertex sets, og bruker dem til å forbedre kjøretiden til backtracking algoritmer betydelig.

Grunnleggende backtracking

den seminal maximal clique publikasjonen beskriver to algoritmer. En detaljert presentasjon av den andre, som er en forbedret versjon av den første, er gitt. Det er denne andre, mer effektive metoden som vi implementerer og tester. Vi skal referere til Det her Som Grunnleggende Backtracking. Alle maksimale klikkene er nummerert med en dybde-første søketreversering. De primære datastrukturene som brukes er tre globale sett med hjørner: COMPSUB, KANDIDATER og IKKE. COMPSUB inneholder punktene i den gjeldende klikken, og er i utgangspunktet tom. KANDIDATER inneholder uutforskede toppunkter som kan utvide den gjeldende klikken, og inneholder i utgangspunktet alle toppunktene i grafen. IKKE inneholder utforskede hjørner som ikke kan forlenge den gjeldende klikken, og er i utgangspunktet tom. Hver rekursiv samtale utfører tre trinn:

• Velg et toppunkt v I KANDIDATER og flytt det til COMPSUB.

• Fjern alle hjørner som ikke støter til v fra BEGGE KANDIDATENE og IKKE. På dette punktet, hvis BEGGE KANDIDATENE og IKKE er tomme, ER COMPSUB en maksimal klikk. Hvis ja, skriv UT COMPSUB som en maksimal cique og fortsett neste trinn. Hvis ikke, ring rekursivt det forrige trinnet.

• Flytt v fra COMPSUB TIL IKKE.

Merk AT IKKE brukes til å holde fra å generere like maksimale cliques. Søketreet kan beskjæres ved å avslutte en gren tidlig hvis noen toppunkt AV IKKE er koblet til ALLE hjørner AV KANDIDATER.

Hjørner velges på en måte som gjør at beskjæringen skjer så snart som mulig. Vi utelater detaljene siden de ikke er relevante for våre modifikasjoner av algoritmen.

lagringskravene Til Grunnleggende Backtracking er relativt beskjedne. Ingen informasjon om tidligere maksimale klikkene må beholdes. I forbedringene vi vil teste, fokuserer vi på hastighet, men forbedrer også minnebruken. Dermed er slike begrensninger i intet tilfelle uoverkommelige for noen av våre testede metoder. Likevel, i noen miljøer, kan minneutnyttelsen være ekstrem. Vi henviser den interesserte leseren til .

Vår Grunnleggende Backtracking implementering fungerer som en første benchmark hvorpå vi kan nå prøve å forbedre.

Finne en enkelt maksimal klikk

Vi bruker begrepet Maksimal Clique Finder (MCF) for å betegne programvaren vi har implementert og raffinert for å finne en enkelt klikk av største størrelse . MCF benytter en pakke med forbehandlingsregler sammen med en forgreningsstrategi som speiler den velkjente fpt-tilnærmingen til vertex-dekselet . Det påkaller først en enkel grådig heuristisk å finne en rimelig stor klikk raskt. Denne klikken brukes da til forbehandling, siden den setter en nedre grense på maksimal klikkstørrelse. De heuristiske arbeider ved å velge den høyeste grad toppunktet, v, deretter velge den høyeste grad nabo av v. Disse to toppunktene danner en første klikk C, som deretter iterativt utvides ved å velge den høyeste grad toppunktet ved siden Av Alle C. på hver iterasjon fjernes ethvert toppunkt som ikke er tilstøtende Til Alle C. Prosessen fortsetter til det ikke finnes flere hjørner utenfor C. Siden / C / er en nedre grense på maksimal klikkstørrelse, kan alle hjørner med grad mindre enn |C – 1| fjernes permanent fra den opprinnelige grafen. Deretter fjernes alle hjørner med grad n – 1 midlertidig fra grafen, men beholdes i en liste siden de må være en del av en maksimal klikk. MCF utnytter en ny form for fargeforbehandling, brukt tidligere i å veilede forgrening. Denne form for forbehandling forsøker å redusere grafen som følger. Gitt en kjent nedre grense k på størrelsen på den maksimale klikken, for hvert vertex v bruker vi rask grådig farging til v og naboene. Hvis disse hjørnene kan farges med færre enn k-farger, kan de ikke v re en del av en maksimal klikk og fjernes fra grafen. NÅR grafen er dermed redusert, BRUKER MCF standard rekursiv forgrening på hjørner, hvor hver gren antar at toppunktet enten er eller ikke er i maksimal klikk.

Intelligent backtracking

Gitt den relative effektiviteten som vi kan finne en enkelt maksimal klikk, virker det logisk å vurdere om kunnskap om klikkens størrelse kan være nyttig for å oppregne alle maksimale klikker. Som det viser seg, fører kunnskap om maksimal klikkstørrelse k til en liten, enkel endring i Den Grunnleggende Backtracking algoritmen. Spesielt ved hver node i søketreet sjekker vi om det er færre enn k-hjørner i foreningen AV COMPSUB og KANDIDATER. I så fall kan den grenen ikke føre til en klikk av størrelse k, og så kommer vi tilbake. Se Figur 2. Mens modifikasjonen kan virke mindre, kan den resulterende beskjæring av søketreet føre til en betydelig reduksjon i søkeområdet. I tillegg til denne mindre endringen i forgrening, bruker vi fargeforprosessering som tidligere beskrevet for å redusere grafen før du sender den til den forbedrede backtracking algoritmen. Fargeforbehandling kombinert med den mindre forgreningsendringen vi kaller Intelligent Backtracking.

Paramaterisert opplisting

Gitt AT MCF benytter en toppunkt forgreningsstrategi, undersøkte vi om DET kunne endres for å oppregne ikke bare en, men alle maksimale klikkene. DET viser seg AT MCF, også, gir seg til en grei modifikasjon som resulterer i opplisting av alle maksimale cliques. Modifikasjonen er ganske enkelt å opprettholde en global liste over alle klikkene av den største størrelsen som hittil er funnet. Når en større maksimal klikken er funnet, er listen tømmes og oppdateres til å inneholde bare den nye maksimal klikken. Når søkeområdet er oppbrukt, vises listen over maksimale klikkerutgang.

vi må imidlertid være spesielt oppmerksom på at visse forbehandlingsregler som brukes under interleaving, ikke lenger er gyldige. Tenk for eksempel fjerning av et blad vertex. Klikkanalogen er å finne et toppunkt med grad n – 2 og fjerne sin ensomme ikke-nabo. Denne regelen forutsetter åpenbart at bare en enkelt maksimal klikk er ønsket, fordi den ignorerer enhver klikk avhengig av det kasserte toppunktet. Derfor må denne spesielle forbehandlingsregelen utelates når forgreningen har begynt.

Maksimale klikkdeksler

hvis VI ser MCF som en svart boks subrutine som kan kalles gjentatte ganger, kan DEN brukes i en enkel grådig algoritme for å beregne et maksimalt sett med usammenhengende maksimale klikker. Vi beregner bare en maksimal klikk, fjerner den fra grafen, og itererer til størrelsen på en maksimal klikk reduseres. For å utforske fordelene ved å beregne et slikt sett, introduserer vi følgende begrep:

Definisjon 1 en maksimal klikkdeksel På G = (V, E) er et sett V’ ⊆ V med egenskapen at hver maksimal klikk Av G inneholder noe toppunkt i dekselet.

foreningen av alle hjørner som finnes i et maksimalt sett av usammenhengende maksimale klikker er selvfølgelig et maksimalt klikkdeksel (heretter MCC), fordi alle maksimale klikker må overlappe med et slikt sett. Dette fører til en nyttig reduksjonsalgoritme. Ethvert toppunkt som ikke er tilstøtende til minst ett medlem AV EN MCC, kan ikke være i en maksimal klikk, og kan dermed fjernes.

i praksis finner vi at bruk AV MCC før de tidligere backtracking algoritmer gir bare marginal forbedring. BEGREPET MCC fører imidlertid til en mye kraftigere tilnærming basert på individuelle hjørner. Siden noen forbedring GJORT AV MCC er subsumert av neste tilnærming, tester VI IKKE MCC av seg selv.

Essential vertex sets

vår undersøkelse av MCC-algoritmen viste at den vanligvis ikke reduserer størrelsen på grafen mer enn forbehandlingsreglene som allerede er innlemmet I MCF. FOR EKSEMPEL FINNER MCF allerede raskt en nedre grense på maksimal klikkstørrelse og fjerner ethvert toppunkt med grad lavere enn denne bunden. Ved nærmere undersøkelse fant vi imidlertid at for 74 av 75 grafer som vi først testet for konferanseversjonen av dette papiret, var det bare nødvendig med en klikk i EN MCC. Det vil si, en maksimal klikken dekket alle andre maksimale klikkene. Og i vår nåværende testbed på 100 grafer, er det i hvert tilfelle en enkelt maksimal klik nok FOR EN MCC. Faktisk faller dette tett sammen med vår erfaring, der vi vanligvis ser høy overlapping blant store klikkar i de transkriptomiske grafene vi møter regelmessig. Basert på denne observasjonen skal vi nå forfine KONSEPTET MCC. I stedet for å dekke maksimale klikkar med klikkar, dekker vi maksimale klikkar med individuelle hjørner.

vi definerer et essensielt toppunkt som en som finnes i hver maksimal klikk. Selvfølgelig er det mulig for en gitt graf å ikke ha et slikt toppunkt, selv når det inneholder mange overlappende maksimale klikker. Men empirisk testing av store transkriptomiske grafer viser at et overveldende antall inneholder mange viktige hjørner. Og for å redusere grafen, vil selv en være tilstrekkelig. Et viktig toppunkt har potensial til å være svært nyttig, fordi det tillater oss å fjerne alle sine ikke-naboer. Vi gjør følgende observasjon: for enhver graf G, ω(g) >ω(G/v) hvis og bare hvis v dekker alle maksimale klikker, hvor ω(G) er maksimal klikkstørrelse På G.

definerer Vi et essensielt sett til å være settet av alle essensielle hjørner. Essential Set (ES) algoritmen, som beskrevet i Figur 3, finner alle essensielle hjørner i en graf. Det reduserer deretter grafen ved å fjerne, for hvert viktig toppunkt, alle ikke-naboer av det toppunktet. ES algoritmen kan kjøres i forbindelse med noen av backtracking mce algoritmer, eller faktisk før noen algoritme som GJØR MCE av noen metode, siden produksjonen er en redusert graf som fortsatt inneholder alle maksimale klikkene fra den opprinnelige grafen. Som våre tester viser, kan kjøretidsforbedringen SOM TILBYS AV ES-algoritmen være dramatisk.

Implementering

vi implementerte alle algoritmer I Enten C eller C++. Koden ble kompilert ved HJELP AV gcc 4.4.3 kompilatoren På Ubuntu Linux versjon 10.04.2 operativsystem samt GCC 3.3.5 kompilatoren Under Debian Linux versjon 3.1. Alle timings ble gjennomført i det Sistnevnte Debian-miljøet på dedikerte noder i en klynge for å sikre at ingen innvirkning på timings fra samtidige prosesser. Hver node hadde En Dual-core Intel Xeon-prosessor som kjører på 3, 20 GHz og 4 GB hovedminne.

Testing

i konferanseversjonen av dette papiret brukte vi tre forskjellige datasett på 25 terskler hver for å utlede totalt 75 grafer for å teste våre algoritmiske forbedringer. Selv om disse grafene sikkert var tilstrekkelig som et innledende bevis på konsept, kunne to bekymringer heves om dem. For det første kan man hevde at tre datasett ikke er en tilstrekkelig stor utvalgsstørrelse for å gi en sann følelse av den generelle naturen til transkriptomiske data eller en algoritmisk forbedrings generelle effektivitet på slike data, det store antall terskler til tross for. Og for det andre, siden de tre datasettene er proprietære og ikke offentlig tilgjengelige, var resultatene ikke så lett reproduserbare som de ellers kunne ha vært. Innhenting av de-identifiserte versjoner, mens det var mulig, var en unødvendig hindring for reproduserbarhet.

vi tar opp slike bekymringer her ved å lage en ny pakke med transkriptomiske grafer for å teste våre algoritmiske forbedringer. Suiten består av grafer avledet fra 25 datasett hentet fra Genuttrykket OMNIBUS (GEO), et offentlig tilgjengelig depot. For hvert datasett ble grafer opprettet på fire forskjellige terskler, for totalt 100 grafer. Datasettene ble valgt for å gi et rimelig variert utvalg av eksperimentell type, art, og mRNA microarray chip type. De dekker 8 forskjellige arter og en rekke forskjellige eksperimentelle forhold som tidsserier, belastning, dose og pasient. Siden våre grafer er avledet fra terskel korrelasjonsverdier, ekskluderte vi fra vurdering av datasett med færre enn 12 forhold. Terskelkorrelasjoner beregnet ved hjelp av så få forhold kan produsere uakseptabelt store mengder falske positiver og falske negativer. Antall forhold varierer fra en lav av 12 til en høy av 153. Ni av datasettene hadde ikke blitt log-transformert, i så fall utførte vi log-transformasjon. Fire av datasettene inneholdt manglende verdier; i disse tilfellene brukte vi korrelasjon p-verdier i stedet for korrelasjoner for terskelen. Se Tabell 1 for en liste OVER GEODATASETTENE som brukes til testing.

fra uttrykksdataene konstruerte vi først vektede grafer der hjørner representerte prober og kantvekter var Pearson korrelasjonskoeffisienter beregnet på tvers av eksperimentelle forhold. Vi konverterte deretter de vektede grafene til uveide grafer ved å beholde bare de kantene hvis vekter var på eller over en valgt terskel, t. for hvert datasett valgte vi fire verdier For T. Alle størrelse / tetthetsverdier var innenfor spektret som vanligvis ble sett i vårt arbeid med biologiske datasett. Den minste grafen hadde 3 828 hjørner og 310 380 kanter; den største hadde 44 563 hjørner og 2 052 228 kanter.

antall maksimale klikkar for grafene i vår testbed varierte fra 8 til 74486. Som sett med vår tidligere testbed, var det ingen merkbar mønster basert på grafstørrelse eller tetthet. Man kan spørre seg hvorfor det er så stor og uforutsigbar variasjon. Det viser seg at antall maksimale klikker kan være ekstremt følsomme for små endringer i grafen. Selv modifikasjonen av en enkelt kant kan ha stor effekt. Tenk for eksempel en graf med en unik maksimal klikkstørrelse k, sammen med en rekke uensartede klikk av størrelse k – 1. Fjerning av bare en kant fra det som var den største klikken kan nå resultere i mange maksimale cliques av størrelse k – 1. Edge tillegg kan selvfolgelig ha lignende effekter. Se figur 4 for et illustrerende eksempel.

for hver algoritme på hver graf gjennomførte vi timings på en dedikert node av en klynge for å unngå forstyrrelser fra andre prosesser. Hvis algoritmen ikke fullførte innen 24 timer, ble den stoppet og grafen ble ansett som ikke løst. Vi valgte terskler for å spre kjøretidene til grafene ut over de fem algoritmene vi testet. Den største (minste i tilfelle korrelasjon p-verdi) terskelen ble valgt slik at et flertall av algoritmene, om ikke alle, løste grafen. Den minste (største i tilfelle korrelasjon p-verdi) terskelen ble valgt slik at minst en av algoritmene, men ikke alle, løste grafen.

på hver graf timet vi ytelsen Til Grunnleggende Backtracking, Intelligent Backtracking og Paramaterisert MC. Vi reduserte deretter grafene ved HJELP AV ES og testet På Nytt Med Intelligent Backtracking og Parameterisert MC, i så fall inkluderer kjøretidene både reduksjons-og opplistingstrinnet. Som forventet Ble Grunnleggende Backtracking funnet å være ikke-konkurransedyktig. Både Intelligent Backtracking og Parameterisert MC viste en tydelig, ofte dramatisk forbedring over Grunnleggende Backtracking. Figur 5 viser kjøretidene til hver av de fem metodene på alle 100 testgrafer. På noen av de enklere grafene, som tar mindre enn tre minutter å løse, forårsaket overhead AV ES faktisk en liten økning i den totale kjøretiden. Men på de vanskeligere tilfellene ble den sanne fordelen tydelig, og reduserte kjøretiden med en størrelsesorden eller mer. Og i alle tilfeller hvor to eller færre algoritmer løste grafen, var algoritmen ENTEN ES MED Intelligent Backtracking, ES med Parameterisert MC, eller begge deler.