det maksimale kliktællingsproblem: algoritmer, applikationer og implementeringer

ved hjælp af den sædvanlige maksimale kliktællingsalgoritme på grund af Bron og Kerbosch som benchmark designede, implementerede og testede vi i vid udstrækning tre algoritmiske forbedringer, den sidste baseret på observationer om arten af grafer produceret af transkriptomiske data. Sammen med at beskrive disse forbedringer, vil vi beskrive vores eksisterende værktøj til at finde en enkelt maksimal klike, baseret på teorien om fast parameter tractability (FPT) . Et sådant værktøj er vigtigt for alle tre forbedringer, da de to første er afhængige af viden om den maksimale klikestørrelse, og den sidste bruger det maksimale klikfindingsværktøj som en subrutine. Alle koder er skrevet i C / C++ og kompileret i Linou. Til test bruger vi 100 grafer afledt af 25 forskellige datasæt, som er offentligt tilgængelige på GEO. Vi koncentrerer os om transkriptomiske data, givet dens overflod, og undgår syntetiske data, efter at have lært for længe siden, at effektive algoritmer for den ene har ringe betydning for den anden. (De patologiske matchninger noteret i for toppunkt dækning kan udvides til klike, men ligeledes de også er naturligvis enormt irrelevant for reelle data.) I et forsøg på at forbedre ydeevnen undersøger vi strukturen af transkriptomiske grafer og udforsker forestillingen om maksimale klikdæksler og essentielle toppunktsæt. Faktisk finder vi, at vi med den rigtige forbehandling er i stand til at skræddersy algoritmer til de slags data, vi rutinemæssigt støder på, og at vi nu kan løse tilfælde, der tidligere blev betragtet som utilgængelige.

algoritmer

i de følgende afsnit beskriver vi hver af de MCE-algoritmer, vi implementerede og testede. Den første er algoritmen for Bron og Kerbosch , som vi kalder grundlæggende Backtracking og bruger som benchmark. Da alle vores efterfølgende forbedringer gør brug af en algoritme, der finder en enkelt maksimal klik, beskriver vi Næste vores eksisterende værktøj, kaldet maksimal Klikfinder (MCF), hvilket gør netop det. Vi ændrer derefter den grundlæggende Backtracking-algoritme for at drage fordel af det faktum, at vi kun ønsker at finde de maksimale klikker og hurtigt kan beregne den maksimale klikstørrelse. Vi kalder denne tilgang Intelligent Backtracking, da den aktivt vender tilbage tidligt fra grene, der ikke vil føre til en maksimal klik. Vi ændrer derefter MCF selv for at opregne alle maksimale Klik, en tilgang, vi kalder parameteriseret maksimal klik, eller parameteriseret MC. På en måde er dette en anden backtracking-tilgang, der går endnu længere for at udnytte det faktum, at vi kun ønsker at finde maksimale klikker. Endelig, baseret på observationer om egenskaberne ved biologiske grafer, introducerer vi begreberne maksimale klikdæksler og essentielle toppunktsæt og anvender dem for at forbedre runtime for backtracking-algoritmer markant.

grundlæggende backtracking

den sædvanlige maksimale klikepublikation beskriver to algoritmer. En detaljeret præsentation af den anden, som er en forbedret version af den første, leveres. Det er denne anden, mere effektive metode, som vi implementerer og tester. Vi vil her henvise til det som grundlæggende Backtracking. Alle maksimale kliker er opregnet med en dybde-første søgning træ traversal. De primære datastrukturer, der anvendes, er tre globale sæt hjørner: COMPSUB, kandidater og ikke. COMPSUB indeholder hjørnerne i den aktuelle klik og er oprindeligt tom. Kandidater indeholder uudforskede hjørner, der kan udvide den aktuelle klik, og indeholder oprindeligt alle hjørner i grafen. Ikke indeholder udforskede hjørner, der ikke kan udvide den aktuelle klik, og er oprindeligt tom. Hvert rekursivt opkald udfører tre trin:

• Vælg et toppunkt v I kandidater og flyt det til COMPSUB.

• Fjern alle hjørner, der ikke støder op til v fra begge kandidater og ikke. På dette tidspunkt, hvis begge kandidater og ikke er tomme, så er COMPSUB en maksimal klik. Hvis så, output COMPSUB som en maksimal Cik og fortsætte det næste trin. Hvis ikke, skal du ringe rekursivt til det forrige trin.

• Flyt v fra COMPSUB til ikke.

Bemærk, at ikke bruges til at holde fra at generere dublerede maksimale kliker. Søgetræet kan beskæres ved at afslutte en gren tidligt, hvis et toppunkt på ikke er forbundet med alle kandidater.

hjørner vælges på en måde, der får denne beskæring til at ske så hurtigt som muligt. Vi udelader detaljerne, da de ikke er relevante for vores ændringer af algoritmen.

lagringskravene til grundlæggende Backtracking er relativt beskedne. Ingen oplysninger om tidligere maksimale kliker skal opbevares. I de forbedringer, vi vil teste, fokuserer vi på hastighed, men forbedrer også hukommelsesforbruget. Sådanne begrænsninger er således under ingen omstændigheder uoverkommelige for nogen af vores testede metoder. Ikke desto mindre kan hukommelsesudnyttelse i nogle miljøer være ekstrem. Vi henviser den interesserede læser til .

vores grundlæggende Backtracking implementering fungerer som en indledende benchmark, som vi nu kan forsøge at forbedre.

Find en enkelt maksimal klike

vi bruger udtrykket maksimal Klikfinder (MCF) til at betegne det program, vi har implementeret og forfinet til at finde en enkelt klik af største størrelse . MCF anvender en række forbehandlingsregler sammen med en forgreningsstrategi, der afspejler den velkendte FPT-tilgang til toppunktdæksel . Det påberåber sig først en simpel grådig heuristisk for hurtigt at finde en rimelig stor klik. Denne Klik bruges derefter til forbehandling, da den sætter en nedre grænse for den maksimale klikestørrelse. De heuristiske værker ved at vælge den højeste grad toppunkt, v, derefter vælge den højeste grad nabo til v. Disse to hjørner danner en indledende klik C, som derefter udvides iterativt ved at vælge den højeste grad toppunkt ved siden af hele C. på hver iteration fjernes ethvert toppunkt, der ikke støder op til hele C. Processen fortsætter, indtil der ikke findes flere hjørner uden for C. Da |C| er en nedre grænse på den maksimale klikestørrelse, kan alle hjørner med grad mindre end |C – 1| fjernes permanent fra den originale graf. Dernæst fjernes alle hjørner med grad n – 1 midlertidigt fra grafen, men bevares på en liste, da de skal være en del af enhver maksimal klik. MCF udnytter en ny form for farveforarbejdning , tidligere brugt til at guide forgrening. Denne form for forbehandling forsøger at reducere grafen som følger. Givet en kendt nedre grænse k på størrelsen af den maksimale klik, for hvert toppunkt v anvender vi hurtig grådig farve til v og dets naboer. Hvis disse hjørner kan farves med færre end k-farver, kan v ikke være en del af en maksimal klik og fjernes fra grafen. Når grafen således er reduceret, bruger MCF standard rekursiv forgrening på hjørner, hvor hver gren antager, at toppunktet enten er eller ikke er i den maksimale klik.

Intelligent backtracking

i betragtning af den relative effektivitet, hvormed vi kan finde en enkelt maksimal klike, synes det logisk at overveje, om viden om klikens størrelse kan være nyttig til at opregne alle maksimale kliker. Som det viser sig, viden om den maksimale klikstørrelse k fører til en lille, ligetil ændring i den grundlæggende Backtracking-algoritme. Specifikt kontrollerer vi ved hver knude i søgetræet, om der er færre end k-hjørner i foreningen af COMPSUB og kandidater. I så fald kan den gren ikke føre til en Klik af størrelse k, og så vender vi tilbage. Se Figur 2. Mens ændringen kan virke mindre, kan den resulterende beskæring af søgetræet føre til en betydelig reduktion i søgeområdet. Ud over denne mindre ændring til forgrening anvender vi farveforarbejdning som tidligere beskrevet for at reducere grafen, inden vi sender den til den forbedrede backtracking-algoritme. Farveforarbejdning kombineret med den mindre forgreningsændring, vi kalder Intelligent Backtracking.

Paramateriseret optælling

i betragtning af at MCF anvender en toppunktsforgreningsstrategi, undersøgte vi, om den kunne ændres til at opregne ikke kun en, men alle maksimale klikker. Det viser sig, at MCF også egner sig til en ligetil ændring, der resulterer i opregning af alle maksimale klikker. Ændringen er simpelthen at opretholde en global liste over alle kliker af den hidtil største størrelse. Når der findes en større maksimal klik, skylles listen og opdateres for kun at indeholde den nye maksimale klik. Når søgeområdet er opbrugt, vises listen over maksimale klik.

vi skal dog være særlig opmærksomme på at bemærke, at visse forbehandlingsregler, der anvendes under interleaving, ikke længere er gyldige. Overvej for eksempel fjernelse af et bladhjørne. Klikanalogen er at finde et toppunkt med grad n – 2 og fjerne dets ensomme ikke-nabo. Denne regel antager åbenlyst, at kun en enkelt maksimal klik ønskes, fordi den ignorerer enhver klik afhængigt af det kasserede toppunkt. Derfor skal denne særlige forbehandlingsregel udelades, når forgreningen er begyndt.

maksimal klikomslag

hvis vi ser MCF som en sort boks subrutine, der kan kaldes gentagne gange, kan den bruges i en simpel grådig algoritme til beregning af et maksimalt sæt uensartede maksimale klikker. Vi beregner blot en maksimal klik, fjerner den fra grafen og gentager, indtil størrelsen af en maksimal klik falder. For at undersøge fordelene ved at beregne et sådant sæt introducerer vi følgende forestilling:

Definition 1 et maksimalt klikdæksel på G = (V, E) er et sæt v’ Kurvv med den egenskab, at hver maksimale klik på G indeholder noget toppunkt i dækslet.

foreningen af alle hjørner indeholdt i et maksimalt sæt uensartede maksimale klikker er selvfølgelig et maksimalt klikdæksel (fremover MCC), fordi alle maksimale klikker skal overlappe hinanden med et sådant sæt. Dette fører til en nyttig reduktionsalgoritme. Ethvert toppunkt, der ikke støder op til mindst et medlem af en MCC, kan ikke være i en maksimal klik og kan således fjernes.

i praksis finder vi, at anvendelse af MCC før de tidligere backtracking algoritmer kun giver marginal forbedring. Begrebet MCC fører imidlertid til en meget mere kraftfuld tilgang baseret på individuelle hjørner. Da enhver forbedring foretaget af MCC er underlagt den næste tilgang, tester vi ikke MCC af sig selv.

væsentlige toppunktsæt

vores undersøgelse af MCC-algoritmen afslørede, at den typisk ikke reducerer størrelsen på grafen mere end de forbehandlingsregler, der allerede er indarbejdet i MCF. For eksempel finder MCF allerede hurtigt en nedre grænse på den maksimale klikstørrelse og fjerner ethvert toppunkt med grad lavere end denne grænse. Ved nærmere undersøgelse fandt vi imidlertid, at for 74 af 75 grafer, som vi oprindeligt testede for konferenceversionen af dette papir, var der kun brug for en klik i en MCC. Det vil sige, en maksimal klik dækkede alle andre maksimale klik. Og i vores nuværende testbed på 100 grafer er i hvert tilfælde en enkelt maksimal klik tilstrækkelig til en MCC. Faktisk falder dette tæt sammen med vores erfaring, hvor vi typisk ser høj overlapning mellem store kliker i de transkriptomiske grafer, vi støder på regelmæssigt. På baggrund af denne observation vil vi nu forfine begrebet MCC. I stedet for at dække maksimale klikker med klikker dækker vi maksimale klikker med individuelle hjørner.

vi definerer et essentielt toppunkt som et, der er indeholdt i hver maksimal klik. Selvfølgelig er det muligt for en given graf At have noget sådant toppunkt, selv når det indeholder mange overlappende maksimale klikker. Men empirisk test af store transkriptomiske grafer viser, at et overvældende antal indeholder adskillige væsentlige hjørner. Og med henblik på at reducere grafen vil selv en være tilstrækkelig. Et vigtigt toppunkt har potentialet til at være yderst nyttigt, fordi det giver os mulighed for at fjerne alle dets ikke-naboer. Vi anvender følgende observation: for en hvilken som helst graf G, Kurt(g) >Kurt(G/v) hvis og kun hvis v dækker alle maksimale klikker, hvor Kurt(G) er den maksimale klikstørrelse på G.

vi definerer et væsentligt sæt, der skal være sættet med alle væsentlige hjørner. Det Essential Set (ES) algoritme, som beskrevet i figur 3, finder alle væsentlige hjørner i en graf. Det reducerer derefter grafen ved at fjerne, for hvert essentielt toppunkt, alle ikke-naboer til det toppunkt. ES-algoritmen kan køres i forbindelse med en hvilken som helst af backtracking MCE-algoritmerne eller faktisk forud for enhver algoritme, der udfører MCE efter en hvilken som helst metode, da dens output er en reduceret graf, der stadig indeholder alle maksimale klik fra den originale graf. Som vores test viser, kan runtime-forbedringen, der tilbydes af ES-algoritmen, være dramatisk.

implementering

Vi implementerede alle algoritmer i enten C eller C++. Koden blev kompileret ved hjælp af GCC 4.4.3 compiler på Ubuntu version 10.04.2 operativsystem samt GCC 3.3.5 compiler under Debian version 3.1. Alle tider blev udført i sidstnævnte Debian-miljø på dedikerede knudepunkter i en klynge for at sikre, at ingen indflydelse på tider fra samtidige processer. Hver node havde en dual-core Intel – processor, der kører på 3,20 GH og 4 GB hovedhukommelse.

test

i konferenceversionen af dette papir brugte vi tre forskellige datasæt ved 25 tærskler hver for at udlede i alt 75 grafer til at teste vores algoritmiske forbedringer. Mens disse grafer bestemt var tilstrækkelige som et indledende bevis på konceptet, kunne der rejses to bekymringer vedrørende dem. For det første kan man hævde, at tre datasæt ikke er en tilstrækkelig stor stikprøvestørrelse til at give en ægte fornemmelse af den overordnede karakter af transkriptomiske data eller en algoritmisk forbedrings generelle effektivitet på sådanne data, uanset det store antal tærskler. Og for det andet, da de tre datasæt er proprietære og ikke offentligt tilgængelige, var resultaterne ikke så let reproducerbare, som de ellers kunne have været. At opnå de-identificerede versioner, mens det var muligt, var en unødvendig hindring for Reproducerbarhed.

vi adresserer sådanne bekymringer her ved at oprette en ny pakke med transkriptomiske grafer, som vi kan teste vores algoritmiske forbedringer på. Pakken består af grafer afledt af 25 datasæt opnået fra genekspression Omnibus (GEO) , et offentligt tilgængeligt lager. For hvert datasæt blev der oprettet grafer ved fire forskellige tærskler for i alt 100 grafer. Datasættene blev valgt til at tilvejebringe en rimelig forskelligartet prøveudtagning af eksperimentel type, arter, og mRNA microarray chip type. De dækker 8 forskellige arter og en række forskellige eksperimentelle tilstande såsom tidsserier, stamme, dosis og patient. Da vores grafer er afledt af tærskelværdier korrelationsværdier, vi udelukket fra overvejelse ethvert datasæt med færre end 12 betingelser. Tærskelkorrelationer beregnet ved hjælp af så få forhold kan producere uacceptabelt store mængder falske positive og falske negativer. Antallet af betingelser spænder fra en lav på 12 til en høj på 153. Ni af datasættene var ikke blevet log-transformeret, i hvilket tilfælde Vi udførte log-transformation. Fire af datasættene indeholdt manglende værdier; i disse tilfælde brugte vi korrelation p-værdier snarere end korrelationer for tærsklen. Se tabel 1 For en liste over de geodatasæt, der anvendes til test.

fra ekspressionsdataene konstruerede vi først vægtede grafer, hvor hjørner repræsenterede prober og kantvægte var Pearson-korrelationskoefficienter beregnet på tværs af eksperimentelle forhold. Vi konverterede derefter de vægtede grafer til uvægtede grafer ved kun at beholde de kanter, hvis vægt var på eller over en valgt tærskel, t. for hvert datasæt valgte vi fire værdier for t. Alle størrelse/densitetsværdier var inden for det spektrum, der typisk ses i vores arbejde med biologiske datasæt. Den mindste graf havde 3.828 hjørner og 310.380 kanter; den største havde 44.563 hjørner og 2.052.228 kanter.

antallet af maksimale klik for graferne i vores testbed varierede fra 8 til 74486. Som det ses med vores tidligere testbed, der var ikke noget synligt mønster baseret på grafstørrelse eller densitet. Man kan spørge, hvorfor der er så bred, uforudsigelig variation. Det viser sig, at antallet af maksimale klikker kan være yderst følsomt for små ændringer i grafen. Selv modifikationen af en enkelt kant kan have en enorm effekt. Overvej for eksempel en graf med en unik maksimal klike af størrelse k sammen med en række uensartede kliker af størrelse k – 1. Fjernelsen af kun en kant fra det, der var den største klik, kan nu resultere i mange maksimale klik i størrelse k – 1. Kanttilsætning kan selvfølgelig have lignende effekter. Se figur 4 for et illustrativt eksempel.

For hver algoritme på hver graf gennemførte vi tider på en dedikeret node i en klynge for at undgå interferens fra andre processer. Hvis algoritmen ikke blev afsluttet inden for 24 timer, blev den stoppet, og grafen blev anset for ikke at være løst. Vi valgte tærskler for at sprede grafernes driftstider ud over de fem algoritmer, vi testede. Den største (mindste i tilfælde af korrelation p-værdi) tærskel blev valgt således, at et flertal af algoritmerne, hvis ikke alle, løste grafen. Den mindste (største i tilfælde af korrelation p-værdi) tærskel blev valgt således, at mindst en af algoritmerne, men ikke alle, løste grafen.

på hver graf timede vi udførelsen af grundlæggende Backtracking, Intelligent Backtracking og Paramateriseret MC. Vi reducerede derefter graferne ved hjælp af ES og testede igen med Intelligent Backtracking og parameteriseret MC, i hvilket tilfælde driftstiderne inkluderer både reduktions-og optællingstrinnet. Som forventet viste det sig, at grundlæggende Backtracking var ikke-konkurrencedygtig. Både Intelligent Backtracking og parameteriseret MC viste en tydelig, ofte dramatisk, forbedring i forhold til grundlæggende Backtracking. Figur 5 viser driftstiderne for hver af de fem metoder på alle 100 testgrafer. På nogle af de lettere grafer, der tager mindre end tre minutter at løse, forårsagede overhead af ES faktisk en mindre stigning i den samlede driftstid. Men i de vanskeligere tilfælde blev dens sande fordel tydelig, hvilket reducerede runtime med en størrelsesorden eller mere. Og i alle tilfælde, hvor to eller færre algoritmer løste grafen, var algoritmen enten ES med Intelligent Backtracking, ES med parameteriseret MC eller begge dele.