den maximala klick uppräkning problem: algoritmer, applikationer och implementeringar

använda seminal maximal klick uppräkning algoritm på grund av Bron och Kerbosch som riktmärke, vi utformade, genomförs och omfattande testade tre algoritmiska förbättringar, den sista baserat på observationer om vilken typ av grafer som produceras av transkriptomiska data. Tillsammans med att beskriva dessa förbättringar kommer vi att beskriva vårt befintliga verktyg för att hitta en enda maximal klick, baserat på teorin om fast parameter tractability (FPT) . Ett sådant verktyg är viktigt för alla tre förbättringarna, eftersom de två första är beroende av kunskap om den maximala klickstorleken, och den sista använder det maximala klickfyndverktyget som en subrutin. Alla koder skrivs i C / C++ och sammanställs i Linux. För testning använder vi 100 grafer härledda från 25 olika dataset som är offentligt tillgängliga på GEO. Vi koncentrerar oss på transkriptomiska data, med tanke på dess överflöd, och undviker syntetiska data, efter att ha lärt oss för länge sedan att effektiva algoritmer för en har liten betydelse för den andra. (De patologiska matchningarna som noteras för vertex cover kan utvidgas till klick, men på samma sätt är de naturligtvis enormt irrelevanta för verkliga data.) I ett försök att förbättra prestanda granskar vi strukturen för transkriptomiska grafer och utforskar begreppet maximala klickomslag och väsentliga vertexuppsättningar. Vi finner faktiskt att med rätt förbehandling kan vi skräddarsy algoritmer till de typer av data vi rutinmässigt stöter på, och att vi nu kan lösa instanser som tidigare ansågs otillgängliga.

algoritmer

i följande avsnitt beskriver vi var och en av de MCE-algoritmer vi implementerade och testade. Den första är algoritmen för Bron och Kerbosch , som vi kallar grundläggande Backtracking och använder som riktmärke. Eftersom alla våra efterföljande förbättringar använder sig av en algoritm som hittar en enda maximal klick, beskriver vi nästa vårt befintliga verktyg, kallat Maximum Clique Finder (MCF), vilket gör just det. Vi ändrar sedan den grundläggande Backtracking-algoritmen för att dra nytta av det faktum att vi bara vill hitta de maximala klickarna och snabbt kan beräkna den maximala klickstorleken. Vi kallar detta tillvägagångssätt Intelligent Backtracking, eftersom det aktivt återvänder tidigt från grenar som inte leder till en maximal klick. Vi modifierar sedan MCF själv för att räkna upp alla maximala klick, ett tillvägagångssätt som vi kallar parametriserad maximal klick eller parametriserad MC. På ett sätt är detta ett annat backtracking-tillvägagångssätt som går ännu längre för att utnyttja det faktum att vi bara vill hitta maximala klick. Slutligen, baserat på observationer om egenskaperna hos biologiska grafer, introducerar vi begreppen maximum clique covers och essential vertex set, och tillämpar dem för att avsevärt förbättra körtiden för backtracking algoritmer.

grundläggande backtracking

seminal maximal klick publikation beskriver två algoritmer. En detaljerad presentation av den andra, som är en förbättrad version av den första, tillhandahålls. Det är denna andra, effektivare metod som vi implementerar och testar. Vi kommer att hänvisa till det här som grundläggande Backtracking. Alla maximala klick räknas upp med en djup första sökträd traversal. De primära datastrukturerna som används är tre globala uppsättningar av hörn: COMPSUB, kandidater och inte. COMPSUB innehåller hörn i den aktuella klicken,och är initialt tom. Kandidater innehåller outforskade hörn som kan förlänga den aktuella klicken och innehåller initialt alla hörn i diagrammet. NOT innehåller utforskade hörn som inte kan förlänga den aktuella klicken och är initialt tom. Varje rekursivt samtal utför tre steg:

• Välj ett vertex v I kandidater och flytta det till COMPSUB.

• ta bort alla hörn som inte gränsar till v från båda kandidaterna och inte. Vid denna tidpunkt, om båda kandidaterna och inte är tomma, är COMPSUB en maximal klick. Om så är fallet, mata ut COMPSUB som en maximal cique och fortsätt nästa steg. Om inte, ring sedan rekursivt föregående steg.

• flytta v från COMPSUB till inte.

Observera att inte används för att hålla från att generera dubbla maximala klick. Sökträdet kan beskäras genom att avsluta en gren tidigt om någon vertex av NOT är ansluten till alla hörn av kandidater.

hörn väljs på ett sätt som gör att denna beskärning sker så snart som möjligt. Vi utelämnar detaljerna eftersom de inte är relevanta för våra modifieringar av algoritmen.

lagringskraven för grundläggande Backtracking är relativt blygsamma. Ingen information om tidigare maximala klick behöver behållas. I de förbättringar vi kommer att testa fokuserar vi på hastighet men förbättrar också minnesanvändningen. Sådana begränsningar är således inte i något fall oöverkomliga för någon av våra testade metoder. I vissa miljöer kan dock minnesutnyttjandet vara extremt. Vi hänvisar den intresserade läsaren till .

vår grundläggande Backtracking-implementering fungerar som ett första riktmärke som vi nu kan försöka förbättra.

hitta en enda maximal klick

vi använder termen maximal klick Finder (MCF) för att beteckna den programvara vi har implementerat och förfinat för att hitta en enda klick av största storlek . MCF använder en serie förbehandlingsregler tillsammans med en förgreningsstrategi som speglar den välkända FPT-metoden för vertex-omslag . Det åberopar först en enkel girig heuristik för att snabbt hitta en ganska stor klick. Denna klick används sedan för förbehandling, eftersom det sätter en nedre gräns på den maximala klick storlek. De heuristiska verk genom att välja den högsta graden vertex, v, sedan välja den högsta graden granne v. Dessa två hörn bildar en initial klick C, som sedan iterativt utvidgas genom att välja den högsta graden vertex intill alla C. på varje iteration, någon vertex inte intill alla C tas bort. Processen fortsätter tills inga fler hörn finns utanför C. Eftersom |C / är en nedre gräns på den maximala klickstorleken kan alla hörn med grad mindre än| C – 1 / tas bort permanent från den ursprungliga grafen. Därefter tas alla hörn med grad n – 1 tillfälligt bort från grafen, men behålls i en lista eftersom de måste vara en del av en maximal klick. MCF utnyttjar en ny form av färgförbehandling, som tidigare använts för att styra förgrening. Denna form av förbehandling försöker minska grafen enligt följande. Med tanke på en känd nedre gräns k på storleken på den maximala klicken, för varje vertex v applicerar vi snabb girig färgning till v och dess grannar. Om dessa hörn kan färgas med färre än k-färger, kan v inte vara en del av en maximal klick och tas bort från diagrammet. När grafen har reducerats använder MCF standard rekursiv förgrening på hörn, där varje gren antar att toppunktet antingen är eller inte är i den maximala klicken.

Intelligent backtracking

med tanke på den relativa effektiviteten som vi kan hitta en enda maximal klick, verkar det logiskt att överväga om kunskap om den klickens storlek kan vara till hjälp för att räkna upp alla maximala klick. Som det visar sig leder kunskap om den maximala klickstorleken k till en liten, enkel förändring i den grundläggande Backtracking-algoritmen. Specifikt kontrollerar vi vid varje nod i sökträdet om det finns färre än k-hörn i föreningen av COMPSUB och kandidater. Om så är fallet kan den grenen inte leda till en klick av storlek k, och så återvänder vi. Se Figur 2. Medan modifieringen kan verka mindre kan den resulterande beskärningen av sökträdet leda till en betydande minskning av sökutrymmet. Förutom denna mindre ändring av förgrening tillämpar vi färgförbehandling som tidigare beskrivits för att minska grafen innan den skickas till den förbättrade backtracking-algoritmen. Färgförbehandling i kombination med den mindre förgreningsförändringen vi kallar Intelligent Backtracking.

Paramateriserad uppräkning

med tanke på att MCF använder en vertexförgreningsstrategi undersökte vi om den kunde modifieras för att räkna upp inte bara en, utan alla maximala klick. Det visar sig att MCF också lämpar sig för en enkel modifiering som resulterar i uppräkning av alla maximala klick. Ändringen är helt enkelt att upprätthålla en global lista över alla klick av den största storleken som hittills hittats. När en större maximal klick hittas, listan spolas och uppdateras för att innehålla endast den nya maximala klick. När sökutrymmet har uttömts matas listan över maximala klick ut.

vi måste dock vara särskilt försiktiga med att notera att vissa förbehandlingsregler som används vid interfoliering inte längre är giltiga. Tänk till exempel avlägsnandet av ett blad vertex. Klickanalogen är att hitta ett toppunkt med grad n-2 och ta bort sin ensamma icke-granne. Denna regel antar uppenbarligen att endast en enda maximal klick önskas, eftersom den ignorerar någon klick beroende på det kasserade toppunktet. Därför måste denna speciella förbehandlingsregel utelämnas när förgreningen har börjat.

maximal klick täcker

om vi ser MCF som en svart låda subrutin som kan kallas upprepade gånger, kan den användas i en enkel girig algoritm för att beräkna en maximal uppsättning ojämna maximala klick. Vi beräknar bara en maximal klick, tar bort den från grafen och itererar tills storleken på en maximal klick minskar. För att utforska fördelarna med att beräkna en sådan uppsättning introducerar vi följande begrepp:

Definition 1 ett maximalt klickomslag på G = (V, E) är en uppsättning V’ Bisexuell V med egenskapen att varje maximal klick på G innehåller något toppunkt i omslaget.

föreningen av alla hörn som ingår i en maximal uppsättning av ojämna maximala klick är naturligtvis ett maximalt klickskydd (hädanefter MCC), eftersom alla maximala klick måste överlappa med en sådan uppsättning. Detta leder till en användbar reduktionsalgoritm. Varje toppunkt som inte gränsar till minst en medlem av en MCC kan inte vara i en maximal klick och kan därmed tas bort.

i praktiken finner vi att tillämpningen av MCC innan de tidigare backtracking algoritmerna ger endast marginell förbättring. Begreppet MCC leder emellertid till ett mycket kraftfullare tillvägagångssätt baserat på enskilda hörn. Eftersom någon förbättring som gjorts av MCC inordnas av nästa tillvägagångssätt, testar vi inte MCC av sig själv.

väsentliga vertexuppsättningar

vår undersökning av MCC-algoritmen avslöjade att det vanligtvis inte minskar grafens storlek mer än de förbehandlingsregler som redan införlivats i MCF. Till exempel hittar MCF redan snabbt en nedre gräns på den maximala klickstorleken och tar bort alla vertex med grad lägre än den här gränsen. Vid närmare granskning fann vi dock att för 74 av 75 grafer som vi ursprungligen testade för konferensversionen av detta papper behövdes bara en klick i en MCC. Det vill säga, en maximal klick täckte alla andra maximala klick. Och i vår nuvarande testbädd med 100 grafer räcker i alla fall en enda maximal klick för en MCC. I själva verket sammanfaller detta nära med vår erfarenhet, där vi vanligtvis ser Hög överlappning mellan stora klick i de transkriptomiska graferna vi möter regelbundet. Baserat på denna observation ska vi nu förfina begreppet MCC. I stället för att täcka maximala klick med klick, täcker vi maximala klick med enskilda hörn.

vi definierar ett väsentligt toppunkt som en som finns i varje maximal klick. Naturligtvis är det möjligt för en given graf att inte ha något sådant toppunkt, även om det innehåller många överlappande maximala klick. Men empirisk testning av stora transkriptomiska grafer visar att ett överväldigande antal innehåller många väsentliga hörn. Och för att minska grafen kommer även en att räcka. Ett viktigt toppunkt har potential att vara till stor hjälp, eftersom det gör att vi kan ta bort alla dess icke-grannar. Vi använder följande observation: för varje graf g, 0234(g) >6240(g/v) om och endast om v täcker alla maximala klick, där 2738(G) är den maximala klickstorleken på G.

definierar vi en väsentlig uppsättning för att vara uppsättningen av alla väsentliga hörn. Essential Set (ES) – algoritmen, som beskrivs i Figur 3, hittar alla väsentliga hörn i en graf. Det minskar sedan grafen genom att ta bort, för varje väsentligt toppunkt, alla icke-grannar i det toppunktet. ES-algoritmen kan köras i samband med någon av backtracking MCE-algoritmerna, eller faktiskt före någon algoritm som gör MCE med vilken metod som helst, eftersom dess utgång är en reducerad graf som fortfarande innehåller alla maximala klick från den ursprungliga grafen. Som våra tester visar kan körtidsförbättringen som erbjuds av ES-algoritmen vara dramatisk.

implementering

vi implementerade alla algoritmer i antingen C eller C++. Koden sammanställdes med hjälp av GCC 4.4.3-kompilatorn på operativsystemet Ubuntu Linux version 10.04.2 samt GCC 3.3.5-kompilatorn under Debian Linux version 3.1. Alla tidpunkter utfördes i den senare Debianmiljön på dedikerade noder i ett kluster för att säkerställa ingen påverkan på tidpunkter från samtidiga processer. Varje nod hade en dual-core Intel Xeon-processor som kördes med 3, 20 GHz och 4 GB huvudminne.

testning

i konferensversionen av detta dokument använde vi tre olika dataset vid 25 tröskelvärden vardera för att härleda totalt 75 grafer för att testa våra algoritmiska förbättringar. Även om dessa grafer verkligen räckte som ett första bevis på konceptet, kunde två farhågor tas upp angående dem. För det första kan man hävda att tre datamängder inte är en tillräckligt stor provstorlek för att ge en verklig känsla av den övergripande karaktären hos transkriptomiska data eller en algoritmisk förbättrings allmänna effektivitet på sådana data, trots det stora antalet tröskelvärden. Och för det andra, eftersom de tre datamängderna är proprietära och inte offentligt tillgängliga, var resultaten inte lika lätt reproducerbara som de annars skulle ha varit. Att få avidentifierade versioner, även om det var möjligt, var ett onödigt hinder för Reproducerbarhet.

vi tar upp sådana problem här genom att skapa en ny serie transkriptomiska grafer för att testa våra algoritmiska förbättringar. Sviten består av grafer härledda från 25 dataset erhållna från genuttrycket Omnibus (GEO) , ett offentligt tillgängligt arkiv. För varje dataset skapades grafer med fyra olika tröskelvärden, för totalt 100 grafer. Datamängderna valdes för att ge en rimligt varierande provtagning av experimentell typ, Art och mRNA-mikroarraychiptyp. De täcker 8 olika arter och ett antal olika experimentella förhållanden som tidsserier, stam, dos och patient. Eftersom våra grafer är härledda från tröskelkorrelationsvärden, utesluter vi från övervägande alla dataset med färre än 12 villkor. Tröskelkorrelationer beräknade med så få villkor kan ge oacceptabelt stora mängder falska positiva och falska negativa. Antalet förhållanden sträcker sig från en låg av 12 till en hög av 153. Nio av datamängderna hade inte loggtransformerats, i vilket fall vi utförde loggtransformation. Fyra av datamängderna innehöll saknade värden; i dessa fall använde vi korrelation p-värden snarare än korrelationer för tröskeln. Se Tabell 1 för en lista över de GEO-dataset som används för testning.

från uttrycksdata konstruerade vi först viktade grafer där hörn representerade sonder och kantvikter var Pearson korrelationskoefficienter beräknade över experimentella förhållanden. Vi konverterade sedan de viktade graferna till ovägda grafer genom att behålla endast de kanter vars vikter var vid eller över någon vald tröskel, t. för varje dataset valde vi fyra värden för t. alla storlek/densitetsvärden var inom det spektrum som vanligtvis ses i vårt arbete med biologiska dataset. Den minsta grafen hade 3 828 hörn och 310 380 kanter; den största hade 44 563 hörn och 2 052 228 kanter.

antalet maximala klick för graferna i vår testbädd varierade från 8 till 74486. Som vi sett med vår tidigare testbädd fanns det inget märkbart mönster baserat på grafstorlek eller densitet. Man kan fråga sig varför det finns så stor, oförutsägbar variation. Det visar sig att antalet maximala klick kan vara extremt känsliga för små förändringar i grafen. Även modifieringen av en enda kant kan ha en enorm effekt. Tänk till exempel på en graf med en unik maximal klick av storlek k, tillsammans med en mängd ojämna klick av storlek k – 1. Avlägsnandet av bara en kant från vad som var den största klicken kan nu resultera i många maximala klick av storlek k – 1. Edge addition kan naturligtvis ha liknande effekter. Se Figur 4 för ett illustrativt exempel.

för varje algoritm på varje graf genomförde vi tidpunkter på en dedikerad nod i ett kluster för att undvika störningar från andra processer. Om algoritmen inte slutfördes inom 24 timmar stoppades den och grafen ansågs inte ha lösts. Vi valde trösklar för att sprida körtiderna för graferna över de fem algoritmerna vi testade. Den största (minsta i fallet med korrelation p-värde) tröskeln valdes så att en majoritet av algoritmerna, om inte alla, löste grafen. Den minsta (största i fallet med korrelation p-värde) tröskeln valdes så att minst en av algoritmerna, men inte alla, löste grafen.

på varje graf vi tids prestanda grundläggande Backtracking, Intelligent Backtracking, och Paramaterized MC. Vi reducerade sedan graferna med ES och testade om med Intelligent Backtracking och parametriserad MC, i vilket fall körtiderna inkluderar både reduktions-och uppräkningssteget. Som förväntat befanns grundläggande Backtracking vara icke-konkurrenskraftig. Både Intelligent Backtracking och parametriserad MC visade en distinkt, ofta dramatisk förbättring jämfört med grundläggande Backtracking. Figur 5 visar körtiderna för var och en av de fem metoderna på alla 100 testdiagram. På några av de enklare graferna, som tar mindre än tre minuter att lösa, orsakade es-overhead faktiskt en mindre ökning av den totala körtiden. Men i de svårare fallen blev dess verkliga fördel uppenbar, vilket minskade körtiden med en storleksordning eller mer. Och i alla fall där två eller färre algoritmer löste grafen var algoritmen antingen ES med Intelligent Backtracking, ES med parametriserad MC eller båda.