maximální klika výčtu problém: algoritmy, aplikace a implementace

použití klíčového maximální klika výčtu algoritmus vzhledem k Bron a Kerbosch jako měřítko, jsme navrhli, implementovány a rozsáhle testovány tři algoritmické vylepšení, poslední na základě pozorování o povaze grafů produkovaných transkriptomických dat. Spolu s popisem těchto vylepšení popíšeme náš stávající nástroj pro nalezení jediné maximální kliky, založené na teorii tractability s pevným parametrem (FPT) . Takový nástroj je nezbytný pro všechna tři vylepšení, protože první dva se spoléhají na znalost maximální velikosti kliky a poslední používá jako podprogram nástroj pro hledání maximální kliky. Všechny kódy jsou psány v C / C++ a kompilovány v Linuxu. Pro testování používáme 100 grafů odvozených z 25 různých datových souborů, které jsou veřejně dostupné na GEO. Soustředíme se na transkriptomická data, vzhledem k jejich hojnosti, a vyhýbáme se syntetickým datům, když jsme se už dávno dozvěděli, že efektivní algoritmy pro jednoho mají malý vliv na druhého. (Patologické shody zaznamenané v pro krytí vrcholů mohou být rozšířeny na kliku, ale také jsou samozřejmě nesmírně irelevantní pro skutečná data.) Ve snaze zlepšit výkon zkoumáme strukturu transkriptomických grafů a zkoumáme pojem maximálních klikových obalů a základních množin vrcholů. Vskutku, zjistíme, že se správným předzpracováním jsme schopni přizpůsobit algoritmy druhům dat, se kterými se běžně setkáváme, a že nyní můžeme řešit případy dříve považované za nepřekonatelné.

algoritmy

v následujících částech popisujeme každý z algoritmů MCE, které jsme implementovali a testovali. Prvním z nich je algoritmus Bron a Kerbosch , který nazýváme základní Backtracking a používáme jako měřítko. Protože všechna naše následná vylepšení využívají algoritmus, který najde jednu maximální kliku, dále popíšeme náš stávající nástroj nazvaný Maximum Clique Finder (MCF), který to dělá. Dále upravíme základní algoritmus zpětného sledování, abychom využili skutečnosti, že chceme najít pouze maximální kliky a můžeme rychle vypočítat maximální velikost kliky. Tento přístup nazýváme inteligentním zpětným sledováním, protože se aktivně vrací brzy z větví, které nepovedou k maximální klice. Poté upravíme samotný MCF tak, aby vyjmenoval všechny maximální kliky, přístup, který nazýváme parametrizovaná maximální klika, nebo parametrizované MC. V jistém smyslu je to další přístup k zpětnému sledování, který jde ještě dále, aby využil skutečnosti, že chceme najít pouze maximální kliky. Konečně, na základě pozorování o vlastnostech biologických grafů, představíme koncepty maximální klikové kryty a základní vertexové sady, a aplikovat je pro výrazné zlepšení runtime algoritmů zpětného sledování.

základní zpětné sledování

klíčová publikace maximal clique popisuje dva algoritmy. Podrobná prezentace druhé, která je vylepšenou verzí první, je poskytnuta. Je to druhá, efektivnější metoda, kterou implementujeme a testujeme. Budeme to zde označovat jako základní zpětné sledování. Všechny maximální kliky jsou vyjmenovány s hloubkou první vyhledávací strom traversal. Použité primární datové struktury jsou tři globální sady vrcholů: COMPSUB, kandidáti a ne. COMPSUB obsahuje vrcholy v aktuální klice a je zpočátku prázdný. Kandidáti obsahuje neprozkoumané vrcholy, které mohou rozšířit aktuální kliku, a zpočátku obsahuje všechny vrcholy v grafu. NOT obsahuje prozkoumané vrcholy, které nemohou rozšířit aktuální kliku, a je zpočátku prázdný. Každé rekurzivní volání provádí tři kroky:

• vyberte vertex v v kandidátech a přesuňte jej na COMPSUB.

• odstraňte všechny vrcholy, které nejsou přilehlé k v, z obou kandidátů a ne. V tomto bodě, pokud oba kandidáti a ne jsou prázdné, pak COMPSUB je maximální klika. Pokud ano, výstup COMPSUB jako maximální cique a pokračovat v dalším kroku. Pokud ne, rekurzivně zavolejte předchozí krok.

• přesunout v Z COMPSUB na ne.

Všimněte si, že NOT se používá k zabránění generování duplicitních maximálních klik. Vyhledávací strom může být prořezán předčasným ukončením větve, pokud je nějaký vrchol ne spojen se všemi vrcholy kandidátů.

vrcholy jsou vybírány způsobem, který způsobí, že toto prořezávání nastane co nejdříve. Vynecháme podrobnosti, protože nejsou relevantní pro naše modifikace algoritmu.

požadavky na skladování základního zpětného sledování jsou relativně skromné. Není třeba uchovávat žádné informace o předchozích maximálních klikách. Ve vylepšeních, které budeme testovat, se zaměřujeme na rychlost, ale také zlepšujeme využití paměti. Taková omezení tedy nejsou v žádném případě zakázána pro žádnou z našich testovaných metod. V některých prostředích však může být využití paměti extrémní. Odkazujeme na zainteresovaného čtenáře .

naše základní implementace zpětného sledování slouží jako počáteční měřítko, na kterém se nyní můžeme pokusit vylepšit.

nalezení jediné maximální kliky

používáme termín Maximum Clique Finder (MCF) k označení softwaru, který jsme implementovali a vylepšili pro nalezení jediné kliky největší velikosti . MCF využívá sadu pravidel předzpracování spolu se strategií větvení, která odráží známý přístup FPT k pokrytí vertexu . Nejprve vyvolá prostého chamtivého heuristu, aby rychle našel přiměřeně velkou kliku. Tato Klika se pak používá pro předzpracování, protože klade dolní hranici na maximální velikost kliky. Heuristické práce výběrem nejvyššího stupně vrchol, v, pak výběrem nejvyššího stupně soused v. tyto dva vrcholy tvoří počáteční kliku C, který je pak iterativně rozšířen výběrem nejvyššího stupně vrchol sousedící se všemi C. na každé iteraci, jakýkoli vrchol, který není přilehlý ke všem C, je odstraněn. Proces pokračuje, dokud neexistují žádné další vrcholy mimo C. Vzhledem k tomu, že |C / je dolní mez na maximální velikosti kliky, mohou být všechny vrcholy se stupněm menším než |C – 1| trvale odstraněny z původního grafu. Dále jsou všechny vrcholy se stupněm n – 1 dočasně odstraněny z grafu, ale zachovány v seznamu, protože musí být součástí jakékoli maximální kliky. MCF využívá novou formu předzpracování barev, dříve používané k vedení větvení. Tato forma předzpracování se pokouší graf zmenšit následujícím způsobem. Vzhledem ke známé dolní hranici k o velikosti maximální kliky, pro každý vrchol v aplikujeme rychlé chamtivé zbarvení na v a jeho sousedy. Pokud mohou být tyto vrcholy zbarveny méně než barvami k, pak v nemůže být součástí maximální kliky a je z grafu odstraněn. Jakmile je graf takto zmenšen, MCF používá standardní rekurzivní větvení na vrcholech, kde každá větev předpokládá, že vrchol je nebo není v maximální klice.

inteligentní zpětné sledování

vzhledem k relativní účinnosti, s níž můžeme najít jednu maximální kliku, se zdá logické zvážit, zda znalost velikosti této kliky může být užitečná při výčtu všech maximálních klik. Jak se ukazuje, znalost maximální velikosti kliky k vede k malému, přímá změna v základním algoritmu zpětného sledování. Konkrétně u každého uzlu ve vyhledávacím stromu zkontrolujeme, zda je ve spojení COMPSUB a kandidátů méně než k vrcholů. Pokud ano, tato větev nemůže vést ke klice velikosti k, a tak se vracíme. Viz Obrázek 2. I když se modifikace může zdát malá, výsledné prořezávání vyhledávacího stromu může vést k podstatnému zmenšení vyhledávacího prostoru. Kromě této drobné změny větvení, aplikujeme předzpracování barev, jak bylo popsáno výše, abychom zmenšili Graf před jeho odesláním do vylepšeného algoritmu zpětného sledování. Předzpracování barev v kombinaci s drobnou změnou větvení nazýváme inteligentní zpětné sledování.

Paramaterizovaný výčet

vzhledem k tomu, že MCF používá strategii větvení vrcholů, zkoumali jsme, zda by mohl být upraven tak, aby vyjmenoval nejen jednu, ale všechny maximální kliky. Ukazuje se, že MCF se také hodí k přímé modifikaci, která má za následek výčet všech maximálních klik. Modifikací je jednoduše udržovat globální seznam všech dosud nalezených klik největší velikosti. Kdykoli je nalezena větší maximální klika, seznam je propláchnut a obnoven, aby obsahoval pouze novou maximální kliku. Po vyčerpání vyhledávacího prostoru se zobrazí seznam maximálních klik.

musíme však věnovat zvláštní pozornost tomu, že určitá pravidla předzpracování používaná při prokládání již nejsou platná. Zvažte například odstranění vrcholu listu. Klikový analog je najít vrchol se stupněm n-2 a odstranit jeho osamělého souseda. Toto pravidlo zjevně předpokládá, že je požadována pouze jedna maximální klika, protože ignoruje jakoukoli kliku v závislosti na vyřazeném vrcholu. Proto musí být toto konkrétní pravidlo předzpracování vynecháno, jakmile začne větvení.

maximální klika pokrývá

pokud vnímáme MCF jako podprogram černé skříňky, který lze volat opakovaně, lze jej použít v jednoduchém chamtivém algoritmu pro výpočet maximální sady disjunktních maximálních klik. Pouze vypočítáme maximální kliku, odstraníme ji z grafu a iterujeme, dokud velikost maximální kliky neklesne. Abychom prozkoumali výhody výpočtu takové sady, zavádíme následující pojem:

Definice 1 maximální klikový kryt G = (V, E) je množina V ‚ ⊆ V s vlastností, že každá maximální klika G obsahuje nějaký vrchol v krytu.

spojení všech vrcholů obsažených v maximální sadě disjunktních maximálních klik je samozřejmě maximálním klikovým krytem (od nynějška MCC), protože všechny maximální kliky se musí překrývat s takovou sadou. To vede k užitečnému redukčnímu algoritmu. Jakýkoli vrchol, který není přiléhající k alespoň jednomu členu MCC, nemůže být v maximální klice, a lze jej tedy odstranit.

v praxi zjistíme, že použití MCC před dřívějšími algoritmy zpětného sledování přináší pouze okrajové zlepšení. Koncept MCC však vede k mnohem silnějšímu přístupu založenému na jednotlivých vrcholech. Vzhledem k tomu, že jakékoli zlepšení provedené MCC je zahrnuto dalším přístupem, netestujeme MCC sám o sobě.

základní vertexové sady

naše zkoumání algoritmu MCC odhalilo, že obvykle nesnižuje velikost grafu více než pravidla předzpracování již začleněná do MCF. Například MCF již rychle najde dolní hranici na maximální velikosti kliky a odstraní jakýkoli vrchol se stupněm nižším, než je tato vazba. Při bližším zkoumání, nicméně, zjistili jsme, že pro 74 z 75 grafy, které jsme původně testovali pro konferenční verzi tohoto příspěvku, v MCC byla potřeba pouze jedna klika. To znamená, že jedna maximální klika pokrývala všechny ostatní maximální kliky. A v naší současné testbed 100 grafů, v každém případě jediná maximální klika postačuje pro MCC. Ve skutečnosti se to úzce shoduje s naší zkušeností, ve kterém obvykle vidíme vysoké překrývání mezi velkými klikami v transkriptomických grafech, se kterými se pravidelně setkáváme. Na základě tohoto pozorování nyní upřesníme koncept MCC. Spíše než pokrývat maximální kliky s klikami, pokrýváme maximální kliky s jednotlivými vrcholy.

definujeme základní vrchol jako vrchol, který je obsažen v každé maximální klice. Samozřejmě je možné, že daný graf nemá takový vrchol, i když obsahuje mnoho překrývajících se maximálních klik. Empirické testování velkých transkriptomických grafů však ukazuje, že drtivá většina obsahuje řadu základních vrcholů. A pro účely zmenšení grafu stačí i jeden. Základní vrchol má potenciál být velmi užitečný, protože nám umožňuje odstranit všechny jeho sousedy. Používáme následující pozorování: pro jakýkoli graf G, ω (G) >ω (G/v) pouze tehdy, pokud v pokrývá všechny maximální kliky, kde ω (G) je maximální velikost kliky G.

definujeme základní sadu, která má být sadou všech základních vrcholů. Algoritmus Essential Set (ES), jak je popsáno na obrázku 3, najde všechny podstatné vrcholy v grafu. To pak snižuje graf odstraněním, pro každý základní vrchol, všechny non-sousedy tohoto vrcholu. Es algoritmus může být spuštěn ve spojení s některým z algoritmů zpětného sledování MCE, nebo dokonce před jakýmkoli algoritmem, který dělá MCE jakoukoli metodou, protože jeho výstupem je snížený graf, který stále obsahuje všechny maximální kliky z původního grafu. Jak ukazují naše testy, vylepšení běhu nabízené algoritmem ES může být dramatické.

implementace

implementovali jsme všechny algoritmy v jazyce C nebo C++. Kód byl sestaven pomocí kompilátoru gcc 4.4.3 na operačním systému Ubuntu Linux verze 10.04.2 a kompilátoru gcc 3.3.5 pod Debian Linux verze 3.1. Všechna časování byla provedena v druhém prostředí Debianu na vyhrazených uzlech clusteru, aby nedošlo k ovlivnění časování souběžných procesů. Každý uzel měl dvoujádrový procesor Intel Xeon běžící na 3, 20 GHz a 4 GB hlavní paměti.

testování

v konferenční verzi tohoto článku jsme použili tři různé datové sady při 25 prahových hodnotách, z nichž každý odvodil celkem 75 grafů, na kterých otestoval naše algoritmická vylepšení. I když tyto grafy jistě postačovaly jako počáteční důkaz konceptu, mohly by být ohledně nich vzneseny dvě obavy. Za prvé, dalo by se namítnout, že tři datové sady nejsou dostatečně velké velikosti vzorku, aby poskytly skutečný smysl pro celkovou povahu transkriptomických dat nebo obecnou účinnost algoritmického zlepšení na těchto datech, bez ohledu na velký počet prahových hodnot. A za druhé, protože tyto tři datové soubory jsou vlastnictvím a nejsou veřejně dostupné, výsledky nebyly tak snadno reprodukovatelné, jak by jinak mohly být. Získání de-identifikované verze, zatímco proveditelné, byl zbytečný obtacle reprodukovatelnosti.

tyto obavy zde řešíme vytvořením nové sady transkriptomických grafů, na kterých otestujeme naše algoritmická vylepšení. Sada se skládá z grafů odvozených z 25 datových sad získaných z genové exprese Omnibus (GEO) , veřejně přístupného úložiště. Pro každou datovou sadu byly vytvořeny grafy ve čtyřech různých prahových hodnotách pro celkem 100 grafů. Datové sady byly vybrány tak, aby poskytovaly přiměřeně různorodý odběr vzorků experimentálního typu, druh, a typ mikroarray čipu mRNA. Pokrývají 8 různých druhů a řadu různých experimentálních podmínek, jako jsou časové řady, kmen, dávka a pacient. Protože naše grafy jsou odvozeny z prahových korelačních hodnot, vyloučili jsme z úvahy jakoukoli datovou sadu s méně než 12 podmínky. Prahování korelace vypočtené za použití tak málo podmínek může produkovat nepřijatelně velké míry falešně pozitivních a falešně negativních. Počet podmínek se pohybuje od minima 12 do maxima 153. Devět datových souborů nebylo log-transformováno, v tom případě jsme provedli log-transformaci. Čtyři datové sady obsahovaly chybějící hodnoty; v těchto případech jsme použili korelační p-hodnoty spíše než korelace pro prahovou hodnotu. Seznam geodetických souborů používaných pro testování naleznete v tabulce 1.

z výrazových dat, nejprve jsme vytvořili vážené grafy, ve kterých vrcholy představovaly sondy a hmotnosti hran byly Pearsonovy korelační koeficienty vypočítané napříč experimentálními podmínkami. Vážené grafy jsme pak převedli na nevážené grafy zachováním pouze těch hran, jejichž váhy byly na nebo nad určitou zvolenou prahovou hodnotou, t. pro každou datovou sadu jsme vybrali čtyři hodnoty pro t. všechny hodnoty velikosti/hustoty byly ve spektru, které je obvykle vidět v naší práci s biologickými datovými sadami. Nejmenší graf měl 3 828 vrcholů a 310 380 hran; největší měl 44 563 vrcholů a 2 052 228 hran.

počet maximálních klik pro grafy v našem testbedu se pohyboval od 8 do 74486. Jak je vidět na našem předchozím testbedu, neexistoval žádný rozpoznatelný vzor založený na velikosti nebo hustotě grafu. Člověk by se mohl ptát, proč existuje tak široká, nepředvídatelná variabilita. Ukazuje se, že počet maximálních klik může být extrémně citlivý na malé změny v grafu. Dokonce i modifikace jedné hrany může mít obrovský účinek. Zvažte například graf s jedinečnou maximální klikou velikosti k spolu s řadou nesouvislých klik velikosti k-1. Odstranění pouze jedné hrany z největší kliky může nyní vést k mnoha maximálním klikám velikosti k-1. Přidání hran může mít samozřejmě podobné účinky. Viz obrázek 4 pro ilustrativní příklad.

pro každý algoritmus v každém grafu jsme provedli časování na vyhrazeném uzlu clusteru, abychom zabránili rušení jinými procesy. Pokud algoritmus nebyl dokončen do 24 hodin, byl zastaven a graf byl považován za nevyřešený. Vybrali jsme prahové hodnoty, abychom rozložili doby běhu grafů na pět algoritmů, které jsme testovali. Největší (nejmenší v případě korelace p-hodnota) prahová hodnota byla zvolena tak, aby většina algoritmů, ne-li všechny, vyřešila graf. Nejmenší (největší v případě korelace p-hodnota) prahová hodnota byla zvolena tak, aby alespoň jeden z algoritmů, ale ne všechny, vyřešil graf.

na každém grafu jsme načasovali výkon základního zpětného sledování, inteligentního zpětného sledování a Paramaterizovaného MC. Poté jsme snížili grafy pomocí ES a znovu otestovali pomocí inteligentního zpětného sledování a Parametrizovaného MC, v tomto případě doby běhu zahrnují jak redukci, tak krok výčtu. Podle očekávání bylo zjištěno, že základní zpětné sledování není konkurenceschopné. Jak inteligentní zpětné sledování, tak parametrizované MC vykazovaly zřetelné, často dramatické zlepšení oproti základnímu zpětnému sledování. Obrázek 5 ukazuje doby běhu každé z pěti metod na všech 100 testovacích grafech. Na některých jednodušších grafech, jejichž vyřešení trvá méně než tři minuty, režie ES ve skutečnosti způsobila menší nárůst celkové doby běhu. V obtížnějších případech se však projevil jeho skutečný přínos, snížení doby běhu o řád nebo více. A ve všech případech, kdy graf vyřešily dva nebo méně algoritmů, byl algoritmus buď ES s inteligentním zpětným sledováním, ES s Parametrizovaným MC, nebo obojí.