problema enumerării clicii maxime: algoritmi, aplicații și implementări

folosind algoritmul de enumerare a clicii maxime seminale datorită lui Bron și Kerbosch ca punct de referință, am proiectat, implementat și testat extensiv trei îmbunătățiri algoritmice, ultima bazată pe observații despre natura graficelor produse de datele transcriptomice. Împreună cu descrierea acestor îmbunătățiri, vom descrie instrumentul nostru existent pentru găsirea unei singure clici maxime, bazată pe teoria tractabilității parametrilor fixi (FPT) . Un astfel de instrument este esențial pentru toate cele trei îmbunătățiri, deoarece primele două se bazează pe cunoașterea dimensiunii maxime a clicii, iar ultima folosește instrumentul maxim de găsire a clicii ca subrutină. Toate codurile sunt scrise în C / C++ și compilate în Linux. Pentru testare, folosim 100 de grafice derivate din 25 de seturi de date diferite care sunt disponibile publicului pe GEO. Ne concentrăm pe datele transcriptomice, având în vedere abundența lor, și evităm datele sintetice, după ce am aflat cu mult timp în urmă că algoritmii eficienți pentru unul au o influență redusă asupra celuilalt. (Potrivirile patologice notate în pentru acoperirea vârfurilor pot fi extinse la clică, dar, de asemenea, și ele sunt, desigur, extrem de irelevante pentru datele reale.) Într-un efort de a îmbunătăți performanța, examinăm structura graficelor transcriptomice și explorăm noțiunea de capace maxime de clică și seturi de noduri esențiale. Într-adevăr, constatăm că, cu preprocesarea corectă, suntem capabili să adaptăm algoritmii la tipurile de date pe care le întâlnim în mod obișnuit și că acum putem rezolva instanțe considerate anterior inatacabile.

algoritmi

în secțiunile următoare, descriem fiecare dintre algoritmii MCE pe care i-am implementat și testat. Primul este algoritmul lui Bron și Kerbosch, pe care îl numim Backtracking de bază și îl folosim ca punct de referință. Deoarece toate îmbunătățirile noastre ulterioare folosesc un algoritm care găsește o singură clică maximă, vom descrie în continuare instrumentul nostru existent, numit Maxim Clique Finder (MCF), care face exact asta. În continuare, modificăm algoritmul de bază de Backtracking pentru a profita de faptul că dorim doar să găsim clicile maxime și putem calcula rapid dimensiunea maximă a clicii. Numim această abordare Backtracking inteligent, deoarece se întoarce activ devreme din ramuri care nu vor duce la o clică maximă. Apoi modificăm MCF în sine pentru a enumera toate clicile maxime, o abordare pe care o numim clică maximă parametrizată sau Mc parametrizată. Într-un anumit sens, aceasta este o altă abordare de backtracking care merge și mai departe pentru a exploata faptul că vrem doar să găsim clici maxime. În cele din urmă, pe baza observațiilor despre proprietățile graficelor biologice, introducem conceptele capace maxime de clică și seturi de noduri esențiale și le aplicăm pentru a îmbunătăți semnificativ timpul de rulare al algoritmilor de backtracking.

backtracking de bază

publicația clică maximă seminală descrie doi algoritmi. Este oferită o prezentare detaliată a celei de-a doua, care este o versiune îmbunătățită a primei. Este această a doua metodă, mai eficientă, pe care o implementăm și o testăm. Ne vom referi la aceasta aici ca Backtracking de bază. Toate clicile maxime sunt enumerate cu o traversare a arborelui de căutare în adâncime. Structurile de date primare utilizate sunt trei seturi globale de noduri: COMPSUB, candidați și nu. COMPSUB conține nodurile din clica curentă și este inițial gol. Candidații conțin vârfuri neexplorate care pot extinde clica curentă și conțin inițial toate vârfurile din grafic. Nu conține noduri explorate care nu pot extinde clica curentă și este inițial goală. Fiecare apel recursiv efectuează trei pași:

• selectați un vârf v în Candidați și mutați-l în COMPSUB.

• eliminați toate vârfurile care nu sunt adiacente v de la ambii candidați și nu. În acest moment, dacă ambii candidați și nu sunt goi, atunci COMPSUB este o clică maximă. Dacă da, ieșiți COMPSUB ca cique maxim și continuați pasul următor. Dacă nu, atunci apelați recursiv pasul anterior.

• mutați v de la COMPSUB la nu.

rețineți că NOT este utilizat pentru a împiedica generarea de clici maximale duplicate. Arborele de căutare poate fi tăiat prin terminarea timpurie a unei ramuri dacă un vârf de NOT este conectat la toate vârfurile candidaților.

nodurile sunt selectate într-un mod care face ca această tăiere să aibă loc cât mai curând posibil. Omitem detaliile, deoarece acestea nu sunt pertinente pentru modificările noastre ale algoritmului.

cerințele de stocare ale Backtracking-ului de bază sunt relativ modeste. Nu trebuie păstrate informații despre clicile maxime anterioare. În îmbunătățirile pe care le vom testa, ne concentrăm pe viteză, dar îmbunătățim și utilizarea memoriei. Astfel, astfel de limitări nu sunt în niciun caz prohibitive pentru niciuna dintre metodele noastre testate. Cu toate acestea, în unele medii, utilizarea memoriei poate fi extremă. Ne referim la cititorul interesat .

implementarea noastră de bază de Backtracking servește ca un punct de referință inițial pe care putem încerca acum să-l îmbunătățim.

găsirea unei singure clici maxime

folosim termenul maximum clique Finder (MCF) pentru a desemna software-ul pe care l-am implementat și rafinat pentru a găsi o singură clică de cea mai mare dimensiune . MCF folosește o suită de reguli de preprocesare împreună cu o strategie de ramificare care reflectă binecunoscuta abordare FPT a acoperirii vârfurilor . Mai întâi invocă o euristică simplă lacomă pentru a găsi rapid o clică destul de mare. Această clică este apoi utilizată pentru preprocesare, deoarece pune o limită inferioară pe dimensiunea maximă a clicii. Euristica funcționează alegând vertexul de cel mai înalt grad, v, apoi alegând vecinul de cel mai înalt grad al lui v. Aceste două vârfuri formează o clică inițială C, care este apoi extinsă iterativ prin alegerea vertexului de cel mai înalt grad adiacent întregului C. La fiecare iterație, orice vertex care nu este adiacent întregului C este eliminat. Procesul continuă până când nu mai există vârfuri în afara C. Deoarece |C / este o limită inferioară pe dimensiunea maximă a clicii, toate vârfurile cu grad mai mic de |C – 1| pot fi eliminate definitiv din graficul original. Apoi, toate vârfurile cu gradul n – 1 sunt eliminate temporar din grafic, dar păstrate într-o listă, deoarece trebuie să facă parte din orice clică maximă. MCF exploatează o nouă formă de preprocesare a culorilor, utilizată anterior pentru a ghida ramificarea. Această formă de preprocesare încearcă să reducă graficul după cum urmează. Având în vedere o limită inferioară cunoscută k pe dimensiunea clicii maxime, pentru fiecare vârf v aplicăm colorarea rapidă lacomă la v și vecinii săi. Dacă aceste vârfuri pot fi colorate cu mai puțin de K culori, atunci v nu poate face parte dintr-o clică maximă și este eliminat din grafic. Odată ce graficul este astfel redus, MCF folosește ramificarea recursivă standard pe vârfuri, unde fiecare ramură presupune că vârful este sau nu în clica maximă.

backtracking inteligent

având în vedere eficiența relativă cu care putem găsi o singură clică maximă, pare logic să ne gândim dacă cunoașterea dimensiunii acelei clici poate fi utilă în enumerarea tuturor clicilor maxime. După cum se dovedește, cunoașterea dimensiunii maxime a clicii k duce la o schimbare mică și simplă a algoritmului de bază de Backtracking. Mai exact, la fiecare nod din arborele de căutare verificăm dacă există mai puține noduri de k în Uniunea COMPSUB și candidați. Dacă da, acea ramură nu poate duce la o clică de mărimea k, așa că ne întoarcem. A Se Vedea Figura 2. În timp ce modificarea poate părea minoră, tăierea rezultată a arborelui de căutare poate duce la o reducere substanțială a spațiului de căutare. În plus față de această modificare minoră a ramificării, aplicăm preprocesarea culorilor așa cum s-a descris anterior pentru a reduce graficul înainte de a-l trimite algoritmului îmbunătățit de backtracking. Preprocesarea culorilor combinată cu schimbarea minoră de ramificare pe care o numim Backtracking inteligent.

enumerare Paramaterizată

având în vedere că MCF folosește o strategie de ramificare a vârfurilor, am investigat dacă ar putea fi modificată pentru a enumera nu doar una, ci toate clicile maxime. Se pare că MCF, de asemenea, se pretează la o modificare simplă care are ca rezultat enumerarea tuturor clicilor maxime. Modificarea este pur și simplu pentru a menține o listă globală a tuturor clicilor de cea mai mare dimensiune găsite până acum. Ori de câte ori se găsește o clică maximă mai mare, lista este spălată și reîmprospătată pentru a conține doar noua clică maximă. Când spațiul de căutare a fost epuizat, se afișează lista de clici maxime.

cu toate acestea, trebuie să avem grijă deosebită să observăm că anumite reguli de preprocesare utilizate în timpul intercalării nu mai sunt valabile. Luați în considerare, de exemplu, îndepărtarea unui vârf de frunze. Analogul clicii este de a găsi un vârf cu gradul n – 2 și de a elimina singurul său non-vecin. Această regulă presupune în mod evident că este dorită doar o singură clică maximă, deoarece ignoră orice clică în funcție de vârful aruncat. Prin urmare, această regulă specială de preprocesare trebuie omisă odată ce a început ramificarea.

clica maximă acoperă

dacă privim MCF ca o subrutină cutie neagră care poate fi apelată în mod repetat, aceasta poate fi utilizată într-un algoritm greedy simplu pentru calcularea unui set maxim de clici maxime disjuncte. Calculăm doar o clică maximă, o eliminăm din grafic și repetăm până când dimensiunea unei clici maxime scade. Pentru a explora avantajele calculării unui astfel de set, introducem următoarea noțiune:

definiția 1 o acoperire maximă a clicii de G = (V, E) este o mulțime V’ Inktv cu proprietatea că fiecare clică maximă a lui G conține un nod în copertă.

unirea tuturor nodurilor conținute într-un set maxim de clici maxime disjuncte este desigur o acoperire maximă a clicii (de acum înainte MCC), deoarece toate clicile maxime trebuie să se suprapună cu un astfel de set. Acest lucru duce la un algoritm de reducere util. Orice nod care nu este adiacent la cel puțin un membru al unui MCC nu poate fi într-o clică maximă și poate fi astfel eliminat.

în practică, constatăm că aplicarea MCC înainte de algoritmii de backtracking anteriori produce doar o îmbunătățire marginală. Cu toate acestea, conceptul de MCC duce la o abordare mult mai puternică bazată pe vârfuri individuale. Deoarece orice îmbunătățire făcută de MCC este subsumată de următoarea abordare, nu testăm MCC de la sine.

seturi de noduri esențiale

investigația noastră asupra algoritmului MCC a arătat că de obicei nu reduce dimensiunea graficului mai mult decât regulile de preprocesare deja încorporate în MCF. De exemplu, MCF găsește deja rapid o limită inferioară pe dimensiunea maximă a clicii și elimină orice vârf cu un grad mai mic decât această limită. Cu toate acestea, la o examinare mai atentă, am constatat că pentru 74 din 75 de grafice pe care le-am testat inițial pentru versiunea de conferință a acestei lucrări, era nevoie de o singură clică într-un MCC. Adică, o clică maximă acoperea toate celelalte clici maxime. Și în testul nostru actual de 100 de grafice, în fiecare caz, o singură clică maximă este suficientă pentru un MCC. De fapt, acest lucru coincide îndeaproape cu experiența noastră, în care de obicei vedem suprapuneri mari între clicile mari din graficele transcriptomice pe care le întâlnim în mod regulat. Pe baza acestei observații, vom rafina acum conceptul de MCC. În loc să acoperim clici maxime cu clici, acoperim clici maxime cu vârfuri individuale.

definim un nod esențial ca unul care este conținut în fiecare clică maximă. Desigur, este posibil ca un grafic dat să nu aibă un astfel de vârf, chiar și atunci când conține multe clici maxime suprapuse. Dar testarea empirică a graficelor transcriptomice mari arată că un număr copleșitor conține numeroase vârfuri esențiale. Și în scopul reducerii graficului, chiar și unul va fi suficient. Un vârf esențial are potențialul de a fi extrem de util, deoarece ne permite să eliminăm toți non-vecinii săi. Folosim următoarea observație: pentru orice Grafic G, (G) >(g/v) dacă și numai dacă v acoperă toate clicile maxime, unde(G) este dimensiunea maximă a clicii lui G.

definim un set esențial pentru a fi mulțimea tuturor vârfurilor esențiale. Algoritmul Set (ES) esențial (e), așa cum este descris în Figura 3, găsește toate vârfurile esențiale într-un grafic. Apoi reduce graficul eliminând, pentru fiecare vârf esențial, toți non-vecinii acelui vârf. Algoritmul ES poate fi rulat împreună cu oricare dintre algoritmii MCE de backtracking, sau într-adevăr înainte de orice algoritm care face MCE prin orice metodă, deoarece ieșirea sa este un grafic redus care conține încă toate clicile maxime din graficul original. După cum arată testele noastre, îmbunătățirea runtime oferită de algoritmul ES poate fi dramatică.

implementare

am implementat toți algoritmii în C sau C++. Codul a fost compilat folosind compilatorul GCC 4.4.3 pe sistemul de operare Ubuntu Linux versiunea 10.04.2, precum și compilatorul GCC 3.3.5 sub Debian Linux versiunea 3.1. Toate temporizările au fost efectuate în ultimul Mediu Debian pe nodurile dedicate ale unui cluster pentru a asigura nici un efect asupra temporizărilor din procesele concurente. Fiecare nod avea un procesor Intel Xeon Dual-core care rulează la 3,20 GHz și 4 GB de memorie principală.

testare

în versiunea conferinței a acestei lucrări, am folosit trei seturi de date diferite la 25 de praguri fiecare pentru a obține un total de 75 de grafice pe care să testăm îmbunătățirile noastre algoritmice. În timp ce aceste grafice au fost cu siguranță suficiente ca dovadă inițială a conceptului, ar putea fi ridicate două preocupări cu privire la acestea. În primul rând, s-ar putea argumenta că trei seturi de date nu reprezintă o dimensiune suficient de mare a eșantionului pentru a oferi un adevărat sens al naturii generale a datelor transcriptomice sau a eficacității generale a unei îmbunătățiri algoritmice asupra acestor date, fără a aduce atingere numărului mare de praguri. În al doilea rând, deoarece cele trei seturi de date sunt brevetate și nu sunt disponibile publicului, rezultatele nu au fost atât de ușor de reprodus pe cât ar fi putut fi altfel. Obținerea versiunilor dezidentificate, deși fezabilă, a fost un obtacol inutil pentru reproductibilitate.

abordăm astfel de preocupări aici prin crearea unei noi suite de grafice transcriptomice pe care să testăm îmbunătățirile noastre algoritmice. Suita este formată din grafice derivate din 25 de seturi de date obținute din expresia genelor Omnibus (GEO) , un depozit accesibil publicului. Pentru fiecare set de date, graficele au fost create la patru praguri diferite, pentru un total de 100 de grafice. Seturile de date au fost selectate pentru a oferi o eșantionare destul de diversă a tipului experimental, a speciilor și a tipului de cip microarray mRNA. Acestea acoperă 8 specii diferite și o serie de condiții experimentale diferite, cum ar fi seriile de timp, tulpina, doza și pacientul. Deoarece graficele noastre sunt derivate din valorile de corelație de prag, am exclus din considerare orice set de date cu mai puțin de 12 condiții. Corelațiile de prag calculate folosind atât de puține condiții pot produce rate inacceptabil de mari de fals pozitive și fals negative. Numărul de condiții variază de la un minim de 12 la un maxim de 153. Nouă dintre seturile de date nu au fost transformate în jurnal, caz în care am efectuat transformarea jurnalului. Patru dintre seturile de date conțineau valori lipsă; în aceste cazuri am folosit valori P de corelație mai degrabă decât corelații pentru Prag. A se vedea tabelul 1 pentru o listă a seturilor de date GEO utilizate pentru testare.

din datele expresiei, am construit mai întâi grafice ponderate în care vârfurile reprezentau sonde și greutățile marginilor erau coeficienți de corelație Pearson calculați în condiții experimentale. Apoi am convertit graficele ponderate în grafice neponderate păstrând doar acele margini ale căror greutăți erau la sau peste un anumit prag ales, t. pentru fiecare set de date, am ales patru valori pentru t. toate valorile dimensiunii/densității se aflau în spectrul văzut de obicei în munca noastră cu seturi de date biologice. Cel mai mic grafic avea 3.828 vârfuri și 310.380 margini; cel mai mare avea 44.563 vârfuri și 2.052.228 margini.

numărul de clici maxime pentru graficele din patul nostru de testare a variat de la 8 la 74486. După cum s-a văzut cu patul nostru de testare anterior, nu a existat un model perceptibil bazat pe dimensiunea sau densitatea graficului. S-ar putea întreba De ce există o variabilitate atât de largă și imprevizibilă. Se pare că numărul de clici maxime poate fi extrem de sensibil la mici modificări ale graficului. Chiar și modificarea unei singure margini poate avea un efect imens. Luați în considerare, de exemplu, un grafic cu o clică maximă unică de dimensiunea k, împreună cu o serie de clici disjuncte de dimensiunea k – 1. Îndepărtarea unei singure margini din ceea ce era cea mai mare clică poate duce acum la multe clici maxime de dimensiune k – 1. Adăugarea de margine poate avea, desigur, efecte similare. A se vedea Figura 4 pentru un exemplu ilustrativ.

pentru fiecare algoritm de pe fiecare grafic, am efectuat temporizări pe un nod dedicat al unui cluster pentru a evita interferențele din alte procese. Dacă algoritmul nu s-a finalizat în 24 de ore, acesta a fost oprit și Graficul a fost considerat că nu a fost rezolvat. Am ales praguri pentru a răspândi timpul de rulare al graficelor peste cei cinci algoritmi pe care îi testam. Cel mai mare prag (cel mai mic în cazul corelației p-valoare) a fost selectat astfel încât majoritatea algoritmilor, dacă nu toți, au rezolvat graficul. Cel mai mic prag (cel mai mare în cazul corelației valorii p) a fost selectat astfel încât cel puțin unul dintre algoritmi, dar nu toți, a rezolvat graficul.

pe fiecare grafic am cronometrat performanța Backtracking de bază, Backtracking inteligent, și Paramaterizat Mc. Apoi am redus graficele folosind ES și am retestat cu Backtracking inteligent și Mc parametrizat, caz în care timpul de rulare include atât etapa de reducere, cât și etapa de enumerare. Așa cum era de așteptat, Backtrackingul de bază s-a dovedit a fi necompetitiv. Atât Backtrackingul inteligent, cât și Mc parametrizat au arătat o îmbunătățire distinctă, adesea dramatică, față de Backtrackingul de bază. Figura 5 prezintă timpul de rulare al fiecăreia dintre cele cinci metode pe toate cele 100 de grafice de testare. Pe unele dintre graficele mai ușoare, cele care durează mai puțin de trei minute pentru a rezolva, cheltuielile generale ale ES au provocat de fapt o creștere minoră a duratei generale de rulare. Dar, în cazurile mai dificile, adevăratul său beneficiu a devenit evident, reducând timpul de rulare cu un ordin de mărime sau mai mult. Și în toate cazurile în care doi sau mai puțini algoritmi au rezolvat graficul, algoritmul a fost fie ES cu Backtracking inteligent, ES Cu Mc parametrizat, fie ambele.