a maximális klikk-felsorolási probléma: algoritmusok, alkalmazások és implementációk

a Bron és Kerbosch által létrehozott alapvető maximális klikk-felsorolási algoritmust használva mérceként három algoritmikus fejlesztést terveztünk, implementáltunk és alaposan teszteltünk, az utolsót a transzkriptomikus adatok által előállított gráfok természetére vonatkozó megfigyelések alapján. Ezen fejlesztések leírásával együtt leírjuk meglévő eszközünket egyetlen maximális klikk megtalálásához, a rögzített paraméterű kezelhetőség (FPT) elmélete alapján . Egy ilyen eszköz elengedhetetlen mindhárom fejlesztéshez, mivel az első kettő a maximális klikkméret ismeretére támaszkodik, az utolsó pedig a maximális klikkkereső eszközt használja szubrutinként. Minden kód C/C++ nyelven íródott és Linuxban lett lefordítva. A teszteléshez 100 grafikont használunk, amelyek 25 különböző adatkészletből származnak, amelyek nyilvánosan elérhetők a GEO-n. A transzkriptomikus adatokra koncentrálunk, tekintettel azok bőségére, és kerüljük a szintetikus adatokat, miután már régen megtanultuk, hogy az egyik hatékony algoritmusának kevés hatása van a másikra. (A csúcsfedélnél megfigyelt kóros egyezések kiterjeszthetők a klikkre is, de természetesen ezek is rendkívül irrelevánsak a valós adatok szempontjából.) A teljesítmény javítása érdekében megvizsgáljuk a transzkriptomikus gráfok szerkezetét, és feltárjuk a maximális klikkborítók és az alapvető csúcskészletek fogalmát. Valóban, azt találjuk, hogy a megfelelő előfeldolgozással képesek vagyunk az algoritmusokat a rutinszerűen tapasztalt adatokhoz igazítani, és hogy most már megoldhatjuk a korábban támadhatatlannak ítélt példányokat.

algoritmusok

a következő szakaszokban leírjuk az általunk megvalósított és tesztelt MCE algoritmusokat. Az első a Bron és a Kerbosch algoritmusa, amelyet Basic Backtrackingnek nevezünk és referenciaként használunk. Mivel minden későbbi fejlesztésünk olyan algoritmust használ, amely egyetlen maximális klikket talál, ezután leírjuk meglévő eszközünket, az úgynevezett maximális Klikkkeresőt (MCF), amely éppen ezt teszi. Ezután módosítjuk az alapvető visszalépési algoritmust, hogy kihasználjuk azt a tényt, hogy csak a maximális klikkeket akarjuk megtalálni, és gyorsan kiszámíthatjuk a maximális klikk méretét. Ezt a megközelítést intelligens visszalépésnek nevezzük, mivel aktívan visszatér Korán az ágakból, amelyek nem vezetnek maximális klikkhez. Ezután módosítjuk magát az MCF-et az összes maximális klikk felsorolásához, ezt a megközelítést nevezzük paraméterezett maximális klikk, vagy paraméterezett MC. Bizonyos értelemben ez egy újabb visszalépési megközelítés, amely még tovább megy annak kihasználására, hogy csak maximális klikkeket akarunk találni. Végül a biológiai gráfok tulajdonságaira vonatkozó megfigyelések alapján bemutatjuk a maximális klikkborítók és az esszenciális csúcshalmazok fogalmát, és alkalmazzuk őket, hogy jelentősen javítsuk a visszalépő algoritmusok futási idejét.

alapvető visszalépés

az alapvető maximális klikk kiadvány két algoritmust ír le. A második részletes bemutatása, amely az első továbbfejlesztett változata. Ezt a második, hatékonyabb módszert alkalmazzuk és teszteljük. Mi fog hivatkozni, hogy itt, mint az alapvető Backtracking. Az összes maximális klikk egy mélység-első keresési fa bejárással van felsorolva. Az alkalmazott elsődleges adatstruktúrák három globális csúcshalmaz: COMPSUB, jelöltek és nem. A COMPSUB az aktuális klikk csúcsait tartalmazza, és kezdetben üres. A jelöltek olyan fel nem fedezett csúcsokat tartalmaznak, amelyek kiterjeszthetik az aktuális klikket, és kezdetben tartalmazzák a gráf összes csúcsát. A NOT olyan feltárt csúcsokat tartalmaz, amelyek nem tudják kiterjeszteni az aktuális klikket, és kezdetben üresek. Minden rekurzív hívás három lépést hajt végre:

• válasszon ki egy v csúcsot a jelöltekben, és helyezze át a COMPSUB – ba.

• távolítson el minden olyan csúcsot, amely nem szomszédos a v-vel mindkét jelöltből, vagy sem. Ezen a ponton, ha mindkét jelölt üres, akkor a COMPSUB maximális klikk. Ha igen, adja ki a COMPSUB-ot maximális cique-ként, és folytassa a következő lépést. Ha nem, akkor rekurzívan hívja az előző lépést.

• mozgassa a V-t a COMPSUB-ról a NOT-ra.

ne feledje, hogy a nem arra szolgál, hogy ne generáljon duplikált maximális klikkeket. A keresési fa metszhető egy ág korai befejezésével, ha a not valamelyik csúcsa kapcsolódik a jelöltek összes csúcsához.

a csúcsokat úgy választják ki, hogy ez a metszés a lehető leghamarabb megtörténjen. Kihagyjuk a részleteket, mivel azok nem relevánsak az algoritmus módosításaihoz.

az alapvető visszalépés tárolási követelményei viszonylag szerények. A korábbi maximális klikkekkel kapcsolatos információkat nem kell megőrizni. A tesztelni kívánt fejlesztések során a sebességre összpontosítunk, de javítjuk a memóriahasználatot is. Így az ilyen korlátozások semmilyen esetben sem tiltják a tesztelt módszereinket. Ennek ellenére bizonyos környezetekben a memória kihasználtsága szélsőséges lehet. Utaljuk az érdeklődő olvasót .

alapvető visszalépési implementációnk kezdeti referenciaértékként szolgál, amelyen most megpróbálhatunk javítani.

egyetlen maximális klikk keresése

a maximális Klikkkereső (MCF) kifejezést használjuk annak a szoftvernek a jelölésére, amelyet megvalósítottunk és finomítottunk egyetlen legnagyobb klikk megtalálásához . Az MCF egy előfeldolgozási szabálycsomagot alkalmaz egy elágazási stratégiával együtt, amely tükrözi a vertex cover jól ismert FPT megközelítését . Először egy egyszerű kapzsi heurisztikát hív fel, hogy gyorsan megtaláljon egy ésszerűen nagy klikket. Ezt a klikket ezután előfeldolgozásra használják, mivel alsó határt szab a maximális klikkméretnek. A heurisztikus úgy működik, hogy kiválasztja a legmagasabb fokú csúcsot, v, majd kiválasztja a legmagasabb fokú szomszédját v. Ez a két csúcs kezdeti klikket alkot C, amelyet ezután iteratív módon meghosszabbítanak az összes C-vel szomszédos legmagasabb fokú csúcs kiválasztásával. Mivel a| C / a maximális klikkméret alsó határa, a |C – 1| – nél kisebb fokú csúcsok véglegesen eltávolíthatók az eredeti gráfból. Ezután az összes N – 1 fokú csúcs ideiglenesen eltávolításra kerül a gráfból, de megmarad egy listában, mivel minden maximális klikk részének kell lennie. Az MCF kihasználja a színes előfeldolgozás új formáját, amelyet korábban az elágazás irányítására használtak. Az előfeldolgozás ezen formája a következőképpen próbálja csökkenteni a grafikont. Adott egy ismert alsó határ k a maximális klikk méretére, minden v csúcsra gyors kapzsi színezést alkalmazunk v és szomszédai számára. Ha ezeket a csúcsokat K-nál kevesebb színnel lehet színezni, akkor v nem lehet része a maximális klikknek, ezért eltávolítják a gráfból. Miután a gráf így redukálódott, az MCF szabványos rekurzív elágazást használ a csúcsokon, ahol minden ág feltételezi, hogy a csúcs vagy a maximális klikkben van, vagy nincs.

intelligens visszalépés

tekintettel arra a relatív hatékonyságra, amellyel egyetlen maximális klikk megtalálható, logikusnak tűnik megfontolni, hogy az adott klikk méretének ismerete hasznos lehet-e az összes maximális klikk felsorolásában. Mint kiderült, a K maximális klikkméret ismerete kicsi, egyértelmű változáshoz vezet az alapvető visszalépési algoritmusban. Pontosabban, a keresési fa minden csomópontján ellenőrizzük, hogy van-e kevesebb, mint k csúcs a COMPSUB és a jelöltek Uniójában. Ha igen, akkor ez az ág nem vezethet k méretű klikkhez,ezért visszatérünk. Lásd A 2. Ábrát. Bár a módosítás kisebbnek tűnhet, a keresési fa ebből eredő metszése a keresési terület jelentős csökkenéséhez vezethet. Az elágazás ezen kisebb változtatása mellett a korábban leírt színes előfeldolgozást alkalmazzuk a grafikon csökkentésére, mielőtt elküldenénk a továbbfejlesztett visszalépési algoritmusnak. Színes előfeldolgozás kombinálva a kisebb elágazási változással, amelyet intelligens visszalépésnek nevezünk.

Paramaterizált felsorolás

tekintettel arra, hogy az MCF csúcs elágazási stratégiát alkalmaz, megvizsgáltuk, hogy módosítható-e nemcsak egy, hanem az összes maximális klikk felsorolására. Kiderült, hogy az MCF egy egyszerű módosításra is alkalmas, amely az összes maximális klikk felsorolását eredményezi. A módosítás egyszerűen az eddig talált legnagyobb méretű klikkek globális listájának fenntartása. Ha nagyobb maximális klikk található, a lista kipirul és frissül, hogy csak az új maximális klikk legyen benne. Amikor a keresési terület kimerült, a maximális klikkek listája megjelenik.

különös figyelmet kell azonban fordítanunk arra, hogy az interleaving során alkalmazott egyes előfeldolgozási szabályok már nem érvényesek. Vegyük például a levélcsúcs eltávolítását. A Klikk analógja egy n-2 fokú csúcs megkeresése és a nem szomszédja eltávolítása. Ez a szabály nyilvánvalóan feltételezi, hogy csak egyetlen maximális klikkre van szükség, mert figyelmen kívül hagy minden klikket az eldobott csúcstól függően. Ezért ezt a különleges előfeldolgozási szabályt el kell hagyni, miután az elágazás megkezdődött.

maximális klikkborítók

ha az MCF-et fekete doboz alprogramnak tekintjük, amelyet ismételten meg lehet hívni, akkor egy egyszerű kapzsi algoritmusban használható a diszjunkt maximális klikkek maximális halmazának kiszámításához. Csak kiszámítunk egy maximális klikket, eltávolítjuk a gráfból, és addig iterálunk, amíg a maximális klikk mérete csökken. Az ilyen halmaz kiszámításának előnyeinek feltárásához a következő fogalmat vezetjük be:

definíció 1 A G = (V, E) maximális klikkborítója egy halmaz V’ V ‘ azzal a tulajdonsággal, hogy g minden maximális klikkje tartalmaz valamilyen csúcsot a borítóban.

a diszjunkt maximális klikkek maximális halmazában található összes csúcs Uniója természetesen maximális klikkfedél (a továbbiakban MCC), mert minden maximális klikknek átfedésben kell lennie egy ilyen halmazzal. Ez hasznos redukciós algoritmushoz vezet. Bármely csúcs, amely nem szomszédos az MCC legalább egy tagjával, nem lehet maximális klikkben, ezért eltávolítható.

a gyakorlatban azt tapasztaljuk, hogy az MCC alkalmazása a korábbi visszalépési algoritmusok előtt csak marginális javulást eredményez. Az MCC fogalma azonban sokkal erőteljesebb megközelítéshez vezet, amely az egyes csúcsokon alapul. Mivel az MCC által végzett bármilyen javulást a következő megközelítés foglalja magában, nem teszteljük az MCC-t önmagában.

esszenciális csúcskészletek

az MCC algoritmus vizsgálata során kiderült, hogy az általában nem csökkenti jobban a gráf méretét, mint az MCF-be már beépített előfeldolgozási szabályok. Például az MCF már gyorsan megtalálja a maximális klikkméret alsó határát, és eltávolítja az ennél a kötésnél alacsonyabb fokú csúcsokat. Alaposabb vizsgálat után, azonban, azt találtuk, hogy 74 nak, – nek 75 grafikonok, amelyeket eredetileg teszteltünk a cikk konferencia változatához, csak egy klikkre volt szükség egy MCC-ben. Vagyis egy maximális klikk lefedte az összes többi maximális klikket. És a jelenlegi 100 gráfos tesztágyunkban minden esetben egyetlen maximális klikk elegendő egy MCC – hez. Valójában ez szorosan egybeesik tapasztalatunkkal, amelyben jellemzően nagy átfedéseket látunk a transzkriptomikus gráfok nagy klikkjei között, amelyekkel rendszeresen találkozunk. E megfigyelés alapján most finomítjuk az MCC fogalmát. Ahelyett, hogy a maximális klikkeket klikkekkel lefednénk, a maximális klikkeket egyedi csúcsokkal fedjük le.

egy esszenciális csúcsot úgy definiálunk, mint amely minden maximális klikkben megtalálható. Természetesen lehetséges, hogy egy adott gráfnak nincs ilyen csúcsa, még akkor is, ha sok átfedő maximális klikket tartalmaz. De a nagy transzkriptomikus gráfok empirikus tesztelése azt mutatja, hogy elsöprő szám számos lényeges csúcsot tartalmaz. A grafikon csökkentéséhez pedig még egy is elegendő. Az alapvető csúcs rendkívül hasznos lehet, mert lehetővé teszi számunkra, hogy eltávolítsuk az összes nem szomszédját. A következő megfigyelést alkalmazzuk: bármely g gráfra, ha és csak akkor, ha a G gráf(g) >(g/v) akkor és csak akkor, ha v lefedi az összes maximális klikket, ahol a G maximális klikkmérete.

definiálunk egy esszenciális halmazt, amely az összes lényeges csúcs halmaza. Az Essential Set (ES) algoritmus, amint azt a 3.ábra leírja, megtalálja az összes lényeges csúcsot egy gráfban. Ezután csökkenti a gráfot azáltal, hogy minden lényeges csúcsra eltávolítja az adott csúcs összes nem szomszédját. Az ES algoritmus futtatható bármelyik visszalépő MCE algoritmussal együtt, vagy akár bármely olyan algoritmus előtt, amely bármilyen módszerrel elvégzi az MCE-T, mivel kimenete redukált gráf, amely még mindig tartalmazza az eredeti gráf összes maximális klikkjét. Mint tesztjeink azt mutatják, az ES algoritmus által kínált futásidejű javulás drámai lehet.

implementáció

minden algoritmust C vagy C++nyelven implementáltunk. A kódot a GCC 4.4.3 fordító az Ubuntu Linux 10.04.2 verzió operációs rendszer, valamint a GCC 3.3.5 fordító alatt Debian Linux 3.1 verzió. Minden időzítést az utóbbi Debian környezetben hajtottak végre egy fürt dedikált csomópontjain, hogy biztosítsák, hogy az egyidejű folyamatok ne befolyásolják az időzítéseket. Mindegyik csomópont kétmagos Intel Xeon processzorral rendelkezett, 3,20 GHz-en és 4 GB fő memóriával.

tesztelés

a tanulmány konferencia változatában három különböző adatkészletet használtunk 25 küszöbértéken, hogy összesen 75 grafikont kapjunk, amelyeken tesztelhetjük algoritmikus fejlesztéseinket. Bár ezek a grafikonok minden bizonnyal elegendőek voltak a koncepció kezdeti bizonyítékaként, két aggodalom vethető fel velük kapcsolatban. Először is azt állíthatjuk, hogy három adatkészlet nem elég nagy mintaméret ahhoz, hogy valódi érzetet nyújtson a transzkriptomikus ADATOK Általános jellegéről vagy az algoritmikus javulás általános hatékonyságáról az ilyen adatokon, a küszöbértékek nagy száma ellenére. Másodszor, mivel a három adatkészlet védett és nem nyilvános, Az eredmények nem voltak olyan könnyen reprodukálhatók,mint egyébként. Az azonosított verziók megszerzése, bár megvalósítható, szükségtelen akadály volt a reprodukálhatóság szempontjából.

az ilyen aggályokat itt egy új transzkriptomikus gráfcsomag létrehozásával kezeljük, amelyen tesztelhetjük algoritmikus fejlesztéseinket. A csomag 25 adatkészletből származó grafikonokból áll , amelyeket a génexpresszió Omnibus (GEO), egy nyilvánosan hozzáférhető adattár. Minden adatkészlethez négy különböző küszöbértéken hoztak létre grafikonokat, összesen 100 grafikonra. Az adatkészleteket úgy választottuk ki, hogy meglehetősen változatos mintavételt biztosítsanak a kísérleti típusról, fajról és mRNS microarray chip típusról. Ezek 8 különböző fajra és számos különböző kísérleti körülményre terjednek ki, mint például az idősor, a törzs, a dózis és a beteg. Mivel grafikonjaink küszöbkorrelációs értékekből származnak, kizártunk minden olyan adatkészletet, amelynek kevesebb mint 12 feltétele van. Az ilyen kevés feltétel felhasználásával kiszámított küszöbérték-korrelációk elfogadhatatlanul nagy arányú hamis pozitív és hamis negatív eredményeket eredményezhetnek. A feltételek száma az alacsony 12-től a magas 153-ig terjed. Kilenc adatkészlet nem lett log-transzformálva, ebben az esetben log-transzformációt hajtottunk végre. Az adatkészletek közül négy hiányzó értékeket tartalmazott; ezekben az esetekben korrelációs p-értékeket használtunk, nem pedig a küszöb korrelációit. Lásd az 1. táblázatot a teszteléshez használt földrajzi adatkészletek felsorolásához.

az expressziós adatokból először súlyozott grafikonokat készítettünk, amelyekben a csúcsok próbákat képviseltek, az élsúlyok pedig Pearson-korrelációs együtthatók voltak, amelyeket kísérleti körülmények között számítottak ki. Ezután a súlyozott gráfokat súlyozatlan gráfokká alakítottuk át úgy, hogy csak azokat az éleket tartottuk meg, amelyek súlya valamilyen választott küszöbértéken vagy annál magasabb volt, t. minden adatkészlethez négy értéket választottunk t. minden méret/sűrűség érték azon a spektrumon belül volt, amelyet általában a biológiai adatkészletekkel végzett munkánk során láttunk. A legkisebb gráfnak 3828 csúcsa és 310 380 éle volt, a legnagyobbnak 44 563 csúcsa és 2 052 228 éle.

a tesztágyban lévő gráfok maximális klikkjeinek száma 8-tól 74486-ig terjedt. Amint az előző tesztágyunknál látható, nem volt észrevehető minta a gráf mérete vagy sűrűsége alapján. Felmerül a kérdés, hogy miért van ilyen széles, kiszámíthatatlan változékonyság. Kiderül, hogy a maximális klikkek száma rendkívül érzékeny lehet A grafikon kis változásaira. Még az egyetlen él módosítása is hatalmas hatással lehet. Vegyünk például egy gráfot, amelynek egyedi maximális k méretű klikkje van, valamint egy sor K – 1 méretű diszjunkt klikk. Csak egy él eltávolítása a legnagyobb klikkből sok maximális K-1 méretű klikkhez vezethet. Az él hozzáadása természetesen hasonló hatásokkal járhat. A szemléltető példát lásd a 4. ábrán.

az egyes gráfok minden algoritmusához időzítést végeztünk egy klaszter dedikált csomópontján, hogy elkerüljük a többi folyamat interferenciáját. Ha az algoritmus nem fejeződött be 24 órán belül, akkor leállították, és a gráfot nem tekintették megoldottnak. Küszöbértékeket választottunk a Grafikonok futási idejének elosztására az általunk tesztelt öt algoritmus felett. A legnagyobb (korreláció esetén a legkisebb p-érték) küszöböt úgy választottuk meg, hogy az algoritmusok többsége, ha nem az összes, megoldotta a gráfot. A legkisebb (a p-érték korreláció esetén a legnagyobb) küszöböt úgy választottuk meg, hogy az algoritmusok közül legalább az egyik, de nem az összes megoldotta a gráfot.

minden grafikonon időzítettük az alapvető Visszalépés, az intelligens visszalépés és a Paramaterizált MC teljesítményét. Ezután es-vel redukáltuk a grafikonokat, majd intelligens visszalépéssel és paraméterezett MC-vel teszteltük őket, ebben az esetben a futási idők Tartalmazzák mind a redukciós, mind a felsorolási lépést. Ahogy az várható volt, az alapvető visszalépés nem volt versenyképes. Mind az intelligens visszalépés, mind a paraméterezett MC egyértelmű, gyakran drámai javulást mutatott az alapvető visszalépéshez képest. Az 5. ábra mind az öt módszer futási idejét mutatja mind a 100 tesztgráfon. Néhány könnyebb grafikonon, amelyek megoldása kevesebb, mint három percet vesz igénybe, az ES rezsi valójában a teljes futási idő kismértékű növekedését okozta. De a nehezebb esetekben valódi előnye nyilvánvalóvá vált, csökkentve a futási időt nagyságrenddel vagy annál nagyobb mértékben. Minden olyan esetben, amikor két vagy kevesebb algoritmus oldotta meg a gráfot, az algoritmus vagy es volt intelligens visszalépéssel, es paraméterezett MC-vel, vagy mindkettő.