the maximum clique enumeration problem: algorithms, applications, and implementations

korzystając z przełomowego algorytmu maximal clique enumeration opracowanego przez Brona i Kerboscha jako benchmark, zaprojektowaliśmy, wdrożyliśmy i dokładnie przetestowaliśmy trzy ulepszenia algorytmiczne, Ostatnie oparte na obserwacjach na temat natury Wykresów wytwarzanych przez dane transkryptomiczne. Wraz z opisaniem tych ulepszeń, opiszemy nasze istniejące narzędzie do znajdowania pojedynczej maksymalnej kliki, w oparciu o teorię ciągliwości o stałych parametrach (FPT) . Takie narzędzie jest niezbędne dla wszystkich trzech ulepszeń, ponieważ pierwsze dwa opierają się na wiedzy o maksymalnym rozmiarze kliki, a ostatni wykorzystuje narzędzie do znajdowania maksymalnej kliki jako podprogram. Wszystkie kody są napisane w C / C++ i skompilowane w Linuksie. Do testowania używamy 100 wykresów pochodzących z 25 różnych zestawów danych, które są publicznie dostępne na GEO. Koncentrujemy się na danych transkryptomicznych, biorąc pod uwagę ich obfitość, i unikamy danych syntetycznych, dowiedziawszy się dawno temu, że skuteczne algorytmy dla jednego mają niewielki wpływ na drugi. (Patologiczne dopasowania odnotowane w odniesieniu do pokrywy wierzchołków mogą być rozszerzone na kliki, ale podobnie też są oczywiście nieistotne dla rzeczywistych danych.) W celu poprawy wydajności badamy strukturę grafów transkryptomicznych i badamy pojęcie maksymalnych okładek klikowych i podstawowych zestawów wierzchołków. Rzeczywiście, stwierdzamy, że przy odpowiednim przetwarzaniu wstępnym jesteśmy w stanie dostosować algorytmy do rodzaju danych, które rutynowo napotykamy, i że możemy teraz rozwiązać instancje wcześniej uważane za niedostępne.

algorytmy

w poniższych sekcjach opisujemy każdy z algorytmów MCE, które zaimplementowaliśmy i przetestowaliśmy. Pierwszym z nich jest algorytm Brona i Kerboscha, który nazywamy podstawowym Backtrackingiem i używamy jako benchmark. Ponieważ wszystkie nasze późniejsze ulepszenia wykorzystują algorytm, który znajduje pojedynczą maksymalną klikę, następnie opisujemy nasze istniejące narzędzie o nazwie Maximum Clique Finder (MCF), które właśnie to robi. Następnie modyfikujemy podstawowy algorytm cofania, aby wykorzystać fakt, że chcemy tylko znaleźć maksymalne kliki i możemy szybko obliczyć maksymalny rozmiar kliki. Nazywamy to podejście inteligentnym Backtrackingiem, ponieważ aktywnie powraca wcześnie z gałęzi, które nie doprowadzą do maksymalnej kliki. Następnie modyfikujemy MCF, aby wyliczyć wszystkie maksymalne kliki, podejście nazywamy Parametryzowanym maksymalnym klikiem lub Parametryzowanym MC. W pewnym sensie jest to kolejne podejście do backtrackingu, które idzie jeszcze dalej, aby wykorzystać fakt, że chcemy znaleźć tylko maksymalne kliki. Na koniec, na podstawie obserwacji właściwości Wykresów biologicznych, Wprowadzamy pojęcia maksimum okładek klik i podstawowych zestawów wierzchołków i stosujemy je w celu znaczącej poprawy działania algorytmów backtrackingu.

Basic backtracking

przełomowa Publikacja maximal clique opisuje dwa algorytmy. Szczegółowa Prezentacja drugiego, który jest ulepszoną wersją pierwszego, jest dostarczana. Jest to druga, bardziej efektywna metoda, którą wdrażamy i testujemy. Określimy to tutaj jako podstawowe śledzenie. Wszystkie maksymalne kliki są wyliczane za pomocą drzewa wyszukiwania wgłębnego. Podstawowe struktury danych stosowane są trzy globalne zestawy wierzchołków: COMPSUB, CANDIDATES I NOT. COMPSUB zawiera wierzchołki w bieżącej klice i jest początkowo pusty. Kandydaci zawierają niezbadane wierzchołki, które mogą rozszerzyć bieżącą klikę i początkowo zawierają wszystkie wierzchołki na wykresie. Nie zawiera zbadanych wierzchołków, które nie mogą rozszerzyć bieżącej kliki i jest początkowo pusta. Każde wywołanie rekurencyjne wykonuje trzy kroki:

• Wybierz wierzchołek v w kandydatach i przenieś go do COMPSUB.

• Usuń wszystkie wierzchołki nie sąsiadujące z v z obu kandydatów i nie. W tym momencie, jeśli zarówno kandydaci, jak i nie są puste, COMPSUB jest maksymalną kliką. Jeśli tak, wyprowadź COMPSUB jako maksymalny cique i kontynuuj następny krok. Jeśli nie, to rekurencyjnie wywołaj poprzedni krok.

• Przenieś v z COMPSUB na NOT.

zauważ, że NOT jest używany do zapobiegania generowaniu duplikatów maksymalnych klików. Drzewo wyszukiwania może zostać przycięte przez wcześniejsze zakończenie gałęzi, jeśli jakiś wierzchołek nie jest połączony ze wszystkimi wierzchołkami kandydatów.

wierzchołki są wybierane w sposób, który powoduje, że przycinanie następuje jak najszybciej. Pomijamy szczegóły, ponieważ nie są one istotne dla naszych modyfikacji algorytmu.

wymagania dotyczące przechowywania podstawowego Backtrackingu są stosunkowo niewielkie. Nie trzeba przechowywać żadnych informacji o poprzednich klikach. W ulepszeniach, które przetestujemy, skupiamy się na szybkości, ale także poprawiamy wykorzystanie pamięci. W związku z tym takie ograniczenia nie są w żadnym wypadku zaporowe dla żadnej z naszych przetestowanych metod. Niemniej jednak w niektórych środowiskach wykorzystanie pamięci może być ekstremalne. Odsyłamy zainteresowanego czytelnika .

nasza podstawowa implementacja Backtrackingu służy jako wstępny benchmark, na którym możemy teraz spróbować ulepszyć.

znajdowanie pojedynczej maksymalnej kliki

używamy terminu Maximum Clique Finder (MCF), aby określić oprogramowanie, które wdrożyliśmy i udoskonaliliśmy w celu znalezienia pojedynczej kliki o największym rozmiarze . MCF stosuje zestaw zasad wstępnego przetwarzania wraz ze strategią rozgałęzienia, która odzwierciedla dobrze znane podejście FPT do pokrywania wierzchołków . Najpierw powołuje się na prostego chciwego heurystę, aby szybko znaleźć dość dużą klikę. Ta klika jest następnie używana do wstępnego przetwarzania, ponieważ nakłada dolną granicę na maksymalny rozmiar kliki. Heurystyka działa poprzez wybranie najwyższego wierzchołka stopnia v, a następnie wybranie najwyższego sąsiada stopnia V. te dwa wierzchołki tworzą początkową klikę C, która jest następnie iteracyjnie rozszerzana przez wybranie najwyższego wierzchołka stopnia przylegającego do wszystkich C. w każdej iteracji każdy wierzchołek nie przylegający do wszystkich C jest usuwany. Proces trwa do momentu, gdy nie ma więcej wierzchołków poza C. Ponieważ |C| jest dolną krawędzią maksymalnego rozmiaru kliki, wszystkie wierzchołki o stopniu mniejszym niż |c – 1| mogą być trwale usunięte z pierwotnego wykresu. Następnie wszystkie wierzchołki o stopniu n-1 są tymczasowo usuwane z grafu, ale przechowywane na liście, ponieważ muszą być częścią dowolnej maksymalnej kliki. MCF wykorzystuje nowatorską formę wstępnego przetwarzania kolorów, używaną wcześniej do kierowania rozgałęzieniami. Ta forma przetwarzania wstępnego próbuje zmniejszyć wykres w następujący sposób. Biorąc pod uwagę znaną dolną granicę k na wielkości maksymalnej kliki, dla każdego wierzchołka v stosujemy szybkie zabarwienie v i jego sąsiadów. Jeśli te wierzchołki mogą być zabarwione kolorami mniejszymi niż K, to v nie może być częścią maksymalnej kliki i jest usuwane z wykresu. Gdy wykres jest w ten sposób zredukowany, MCF używa standardowego rekurencyjnego rozgałęzienia na wierzchołkach, gdzie każda gałąź zakłada, że wierzchołek jest lub nie znajduje się w maksymalnej klice.

inteligentny backtracking

biorąc pod uwagę względną skuteczność, z jaką możemy znaleźć pojedynczą maksymalną klikę, logiczne wydaje się rozważenie, czy znajomość rozmiaru tej kliki może być pomocna w wyliczaniu wszystkich maksymalnych klik. Jak się okazuje, znajomość maksymalnego rozmiaru kliki k prowadzi do niewielkiej, prostej zmiany w podstawowym algorytmie Backtrackingu. Konkretnie, na każdym węźle w drzewie wyszukiwania sprawdzamy, czy w związku COMPSUB i CANDIDATES jest mniej niż K wierzchołków. Jeśli tak, ta gałąź nie może prowadzić do kliki o rozmiarze k, więc wracamy. Patrz Rysunek 2. Chociaż modyfikacja może wydawać się niewielka, wynikowe przycinanie drzewa wyszukiwania może prowadzić do znacznego zmniejszenia przestrzeni wyszukiwania. Oprócz tej drobnej zmiany rozgałęzień, stosujemy wstępne przetwarzanie kolorów, jak wcześniej opisano, aby zmniejszyć wykres przed przesłaniem go do ulepszonego algorytmu śledzenia wstecznego. Wstępne przetwarzanie kolorów w połączeniu z drobną zmianą rozgałęzień nazywamy inteligentnym cofaniem.

Sparamaterized enumeration

biorąc pod uwagę, że MCF stosuje strategię rozgałęzienia wierzchołków, zbadaliśmy, czy można go zmodyfikować, aby wyliczyć nie tylko jedną, ale wszystkie maksymalne kliki. Okazuje się, że MCF również nadaje się do prostej modyfikacji, która skutkuje wyliczeniem wszystkich maksymalnych klików. Modyfikacja polega po prostu na utrzymywaniu globalnej listy wszystkich klików o największym do tej pory rozmiarze. Za każdym razem, gdy zostanie znaleziona większa maksymalna klika, lista jest odświeżana i odświeżana tak, aby zawierała tylko nową maksymalną klikę. Po wyczerpaniu przestrzeni wyszukiwania wyświetlana jest lista maksymalnych klików.

musimy jednak zachować szczególną ostrożność, aby zauważyć, że niektóre zasady przetwarzania wstępnego używane podczas przeplatania nie są już ważne. Rozważ na przykład usunięcie wierzchołka liści. Klika analogowa polega na znalezieniu wierzchołka o stopniu n-2 i usunięciu jego samotnego nie-sąsiada. Ta reguła zakłada, że pożądana jest tylko jedna maksymalna klika, ponieważ ignoruje każdą klikę w zależności od odrzuconego wierzchołka. Dlatego ta szczególna zasada wstępnego przetwarzania musi zostać pominięta po rozpoczęciu rozgałęzienia.

maksymalna klika obejmuje

jeśli spojrzymy na MCF jako podprogram czarnej skrzynki, który może być wywoływany wielokrotnie, może być użyty w prostym algorytmie chciwości do obliczenia maksymalnego zestawu rozłącznych maksymalnych klików. Po prostu obliczamy maksymalną klikę, usuwamy ją z wykresu i powtarzamy, aż rozmiar maksymalnej kliki spadnie. Aby zbadać zalety obliczania takiego zbioru, Wprowadzamy następujące pojęcie:

definicja 1 Maksymalna klika okładki G = (V, E) jest zbiorem V ’ ⊆ V z właściwością, że każda maksymalna klika G zawiera jakiś wierzchołek w okładce.

połączenie wszystkich wierzchołków zawartych w maksymalnym zbiorze rozłącznych klików maksymalnych jest oczywiście maksymalnym pokryciem klików (odtąd MCC), ponieważ wszystkie maksymalne kliki muszą pokrywać się z takim zbiorem. Prowadzi to do użytecznego algorytmu redukcji. Każdy wierzchołek nie sąsiadujący z co najmniej jednym członem MCC nie może znajdować się w maksymalnej klice, a zatem może zostać usunięty.

w praktyce okazuje się, że zastosowanie MCC przed wcześniejszymi algorytmami backtrackingu daje jedynie marginalną poprawę. Koncepcja MCC prowadzi jednak do znacznie mocniejszego podejścia opartego na poszczególnych wierzchołkach. Ponieważ wszelkie ulepszenia dokonane przez MCC są objęte kolejnym podejściem, nie testujemy MCC samodzielnie.

podstawowe zestawy wierzchołków

nasze badanie algorytmu MCC ujawniło, że zwykle nie zmniejsza on rozmiaru grafu bardziej niż zasady wstępnego przetwarzania już włączone do MCF. Na przykład, MCF już szybko znajduje dolną granicę na maksymalnym rozmiarze kliki i usuwa dowolny wierzchołek o stopniu niższym niż ta granica. Po bliższym zbadaniu okazało się jednak, że dla 74 Z 75 wykresów, które początkowo testowaliśmy dla wersji konferencyjnej tego artykułu, tylko jedna klika była potrzebna w MCC. Oznacza to, że jedna maksymalna klika obejmowała wszystkie inne maksymalne kliki. A w naszym obecnym testowym zestawieniu 100 wykresów, w każdym przypadku wystarczy pojedyncza maksymalna klika dla MCC. W rzeczywistości pokrywa się to ściśle z naszym doświadczeniem, w którym zazwyczaj widzimy wysokie nakładanie się dużych klików na wykresach transkryptomicznych, z którymi spotykamy się regularnie. Opierając się na tej obserwacji, udoskonalimy teraz koncepcję MCC. Zamiast pokrywać maksymalne kliki klikami, pokrywamy maksymalne kliki pojedynczymi wierzchołkami.

definiujemy niezbędny wierzchołek jako taki, który jest zawarty w każdej maksymalnej klice. Oczywiście jest możliwe, że dany Wykres nie ma takiego wierzchołka, nawet jeśli zawiera wiele nakładających się na siebie klików maksymalnych. Jednak empiryczne badania dużych Wykresów transkryptomicznych pokazują, że przytłaczająca liczba zawiera liczne istotne wierzchołki. A dla celów zmniejszenia wykresu wystarczy nawet jeden. Niezbędny wierzchołek może być niezwykle pomocny, ponieważ pozwala nam usunąć wszystkich jego nie-sąsiadów. Stosujemy następującą obserwację: dla dowolnego grafu g, ω (g) > ω (G / v) wtedy i tylko wtedy, gdy v obejmuje wszystkie maksymalne kliki, gdzie ω(G) jest maksymalnym rozmiarem kliki G.

definiujemy zbiór zasadniczy jako zbiór wszystkich zasadniczych wierzchołków. Algorytm zbioru zasadniczego (es), opisany na rysunku 3, znajduje wszystkie istotne wierzchołki na wykresie. Następnie zmniejsza Wykres, usuwając, dla każdego niezbędnego wierzchołka, wszystkich nie-sąsiadów tego wierzchołka. Algorytm ES może być uruchamiany w połączeniu z dowolnym algorytmem backtracking MCE, lub nawet przed dowolnym algorytmem, który robi MCE dowolną metodą, ponieważ jego wynikiem jest zredukowany wykres, który nadal zawiera wszystkie maksymalne kliki z oryginalnego wykresu. Jak pokazują nasze testy, poprawa czasu pracy oferowana przez algorytm ES może być dramatyczna.

implementacja

zaimplementowaliśmy wszystkie algorytmy w C lub c++. Kod został skompilowany przy użyciu kompilatora GCC 4.4.3 na systemie operacyjnym Ubuntu Linux w wersji 10.04.2, a także kompilatora GCC 3.3.5 pod Debian Linux w wersji 3.1. Wszystkie timingi były przeprowadzane w tym drugim środowisku Debiana na dedykowanych węzłach klastra, aby nie mieć wpływu na timingi współbieżnych procesów. Każdy węzeł miał Dwurdzeniowy Procesor Intel Xeon pracujący z częstotliwością 3,20 GHz i 4 GB pamięci głównej.

testowanie

w wersji konferencyjnej tego artykułu użyliśmy trzech różnych zestawów danych o 25 progach każdy, aby uzyskać w sumie 75 wykresów, na których można przetestować nasze ulepszenia algorytmiczne. Chociaż wykresy te z pewnością wystarczyły jako wstępny dowód koncepcji, można by poruszyć dwie kwestie dotyczące tych wykresów. Po pierwsze, można argumentować, że trzy zbiory danych nie są wystarczająco duże wielkości próby, aby zapewnić prawdziwe poczucie ogólnej natury danych transkryptomicznych lub ogólnej skuteczności algorytmicznej poprawy na takich Danych, duża liczba progów niezależnie. Po drugie, ponieważ trzy zbiory danych są zastrzeżone i nie są publicznie dostępne, wyniki nie były tak łatwo powtarzalne, jak mogłyby być. Uzyskanie wersji pozbawionych identyfikacji, choć wykonalne, było niepotrzebnym osiągnięciem dla powtarzalności.

rozwiązujemy takie problemy, tworząc nowy zestaw wykresów transkryptomicznych, na których można przetestować nasze ulepszenia algorytmiczne. Zestaw składa się z Wykresów pochodzących z 25 zbiorów danych uzyskanych z Gene Expression Omnibus (GEO), publicznie dostępnego repozytorium. Dla każdego zbioru danych, wykresy zostały utworzone w czterech różnych progów, w sumie 100 wykresów. Zestawy danych zostały wybrane w celu zapewnienia stosunkowo zróżnicowanego pobierania próbek typu eksperymentalnego, gatunków i typu chipów mikromacierzowych mRNA. Obejmują one 8 różnych gatunków i wiele różnych warunków doświadczalnych, takich jak szeregi czasowe, szczep, dawka i pacjent. Ponieważ nasze wykresy pochodzą z progowania wartości korelacji, wykluczyliśmy z rozważania dowolny zbiór danych z mniej niż 12 warunkami. Progowanie korelacji obliczonych przy użyciu tak niewielu warunków może powodować niedopuszczalnie Duże wskaźniki fałszywych alarmów i fałszywych negatywów. Liczba warunków waha się od niskiego 12 do wysokiego 153. Dziewięć zbiorów danych nie zostało przekształconych przez log-transformację, w takim przypadku wykonaliśmy transformację log-transformację. Cztery z zestawów danych zawierały brakujące wartości;w tych przypadkach użyliśmy korelacji wartości p, a nie korelacji dla progu. Tabela 1 zawiera listę zestawów danych GEO używanych do testowania.

na podstawie danych ekspresji skonstruowaliśmy wykresy ważone, w których wierzchołki reprezentowały sondy, a wagi krawędzi były współczynnikami korelacji Pearsona obliczonymi w warunkach eksperymentalnych. Następnie przekonwertowaliśmy wykresy ważone na nieważone wykresy, zachowując tylko te krawędzie, których wagi były na lub powyżej wybranego progu, t. dla każdego zestawu danych wybraliśmy cztery wartości dla T. wszystkie wartości rozmiaru/gęstości mieściły się w widmie Zwykle obserwowanym w naszej pracy z biologicznymi zestawami danych. Najmniejszy Graf miał 3 828 wierzchołków i 310 380 krawędzi; największy miał 44 563 wierzchołki i 2 052 228 krawędzi.

liczba maksymalnych klików dla wykresów w naszym testbedu wahała się od 8 do 74486. Jak widać w naszej poprzedniej platformie testowej, nie było zauważalnego wzorca opartego na rozmiarze lub gęstości wykresu. Można by zapytać, dlaczego istnieje tak szeroka, nieprzewidywalna zmienność. Okazuje się, że liczba maksymalnych klików może być niezwykle wrażliwa na małe zmiany w wykresie. Nawet modyfikacja pojedynczej krawędzi może mieć ogromny efekt. Weźmy na przykład Wykres z unikalną maksymalną kliką o rozmiarze k, wraz z wieloma rozłącznymi klikami o rozmiarze k-1. Usunięcie tylko jednej krawędzi z tego, co było największą kliką, może teraz skutkować wieloma maksymalnymi klikami o rozmiarze k – 1. Dodanie krawędzi może oczywiście mieć podobne efekty. Ilustracyjny przykład znajduje się na rysunku 4.

dla każdego algorytmu na każdym wykresie przeprowadziliśmy timingi na dedykowanym węźle klastra, aby uniknąć zakłóceń ze strony innych procesów. Jeśli algorytm nie został ukończony w ciągu 24 godzin, został wstrzymany, a Wykres uznano za nierozwiązany. Wybraliśmy progi, aby rozłożyć czas pracy wykresów na pięć algorytmów, które testowaliśmy. Największy (najmniejszy w przypadku korelacji wartości p) próg został wybrany w taki sposób, że większość algorytmów, jeśli nie wszystkie, rozwiązała Wykres. Najmniejszy (największy w przypadku korelacji wartości p) próg został tak dobrany, że co najmniej jeden z algorytmów, ale nie wszystkie, rozwiązał Wykres.

na każdym wykresie zmierzyliśmy wydajność podstawowego Backtrackingu, inteligentnego Backtrackingu i Sparamaterializowanego MC. Następnie zredukowaliśmy wykresy za pomocą ES i ponownie przetestowaliśmy za pomocą inteligentnego Backtrackingu i Sparametryzowanego MC, w którym to przypadku czasy uruchomienia obejmują zarówno krok redukcji, jak i wyliczenia. Zgodnie z oczekiwaniami stwierdzono, że podstawowe Backtracking nie jest konkurencyjne. Zarówno Intelligent Backtracking, jak i Parametryzowany MC wykazały wyraźną, często dramatyczną poprawę w stosunku do podstawowego Backtrackingu. Rysunek 5 przedstawia czasy działania każdej z pięciu metod na wszystkich 100 wykresach testowych. Na niektórych łatwiejszych wykresach, tych, które zajmują mniej niż trzy minuty, narzut ES faktycznie spowodował niewielki wzrost ogólnego czasu pracy. Ale w trudniejszych przypadkach jego prawdziwa korzyść stała się widoczna, zmniejszając czas pracy o rząd wielkości lub więcej. We wszystkich przypadkach, gdy dwa lub mniej algorytmów rozwiązało Wykres, algorytm był albo ES z inteligentnym cofaniem, ES z Parametryzowanym MC, albo oba.