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

BronとKerboschをベンチマークとしたseminal maximum clique enumeration algorithmsを使用して、3つのアルゴリズムの改良を設計、実装、広範囲にテストしました。最後は、トランスクリプトミックデータによって生成されるグラフの性質についての観察に基づいています。 これらの改善を説明するとともに，固定パラメータのトレーサビリティ（ＦＰＴ）の理論に基づいて，単一の最大クリークを見つけるための既存のツールについて述べた。 このようなツールは、最初の二つは最大クリークサイズの知識に依存し、最後の二つはサブルーチンとして最大クリーク検索ツールを使用するため、三つの改善 すべてのコードはC/C++で書かれ、Linuxでコンパイルされています。 テストには、GEOで公開されている100の異なるデータセットから派生した25のグラフを使用します。 私たちは、その豊富さを考えると、転写データに集中し、合成データを避け、一方の効果的なアルゴリズムが他方にほとんど関係していないことをずっと前 （頂点カバーのために記載されている病理学的一致は、クリークに拡張することができますが、同様に、それらももちろん実際のデータとは非常に無関係です。）パフォーマンスを向上させるために、我々はトランスクリプトミックグラフの構造を精査し、最大クリークカバーと本質的な頂点セットの概念を探る。 実際、適切な前処理を行うことで、私たちが日常的に遭遇するデータの種類にアルゴリズムを調整することができ、以前は難攻不落と考えられていたイ

アルゴリズム

以下のセクションでは、実装およびテストした各MCEアルゴリズムについて説明します。 一つ目はＢｒｏｎとＫｅｒｂｏｓｃｈのアルゴリズムであり，これを基本的なバックトラッキングと呼び，ベンチマークとして使用する。 その後のすべての改善では、単一の最大クリークを見つけるアルゴリズムを使用しているため、次に、Maximum Clique Finder（MCF）と呼ばれる既存のツールについて説明します。 次に、最大クリークを見つけたいだけで、最大クリークサイズをすばやく計算できるという事実を利用するために、基本的なバックトラッキングアルゴリズムを修正します。 最大のクリークにつながらない枝から積極的に早期に戻るので、このアプローチをインテリジェントなバックトラッキングと呼びます。 次に、MCF自体を変更して、すべての最大クリークを列挙し、パラメータ化された最大クリーク、またはパラメータ化されたMCと呼ぶアプローチを列挙します。 ある意味では、これは最大の派閥しか見つけたくないという事実を悪用するためにさらに進む別のバックトラッキングアプローチです。 最後に，生物学的グラフの性質に関する観察に基づいて，最大クリーク被覆と本質的な頂点集合の概念を導入し，それらをバックトラッキングアルゴリズムの実行時間を大幅に改善するために適用した。

基本的なバックトラッキング

精液の最大クリーク出版物は、二つのアルゴリズムを説明しています。 第一の改良版である第二の詳細なプレゼンテーションが提供される。 私たちが実装してテストするのは、この2番目の、より効率的な方法です。 ここでは、基本的なバックトラッキングと呼びます。 すべての最大クリークは、深さ優先探索木トラバーサルで列挙されます。 使用される主なデータ構造は、頂点の3つのグローバルセットです：COMPSUB、CANDIDATES、NOT。 COMPSUBには、現在のクリークの頂点が含まれ、最初は空です。 候補には、現在のクリークを拡張できる未踏の頂点が含まれており、最初はグラフ内のすべての頂点が含まれています。 NOTには、現在のクリークを拡張できない探索された頂点が含まれ、最初は空です。 各再帰呼び出しは、次の3つのステップを実行します:

• 候補の頂点vを選択し、それをCOMPSUBに移動します。

• Vに隣接していないすべての頂点を両方の候補から削除し、削除しないでください。 この時点で、候補とNOTの両方が空であれば、COMPSUBは極大クリークです。 その場合は、COMPSUBを最大ciqeとして出力し、次のステップを続行します。 そうでない場合は、前のステップを再帰的に呼び出します。

• VをCOMPSUBからNOTに移動します。

NOTは、重複する最大クリークを生成しないようにするために使用されることに注意してください。 探索木は、NOTのある頂点が候補のすべての頂点に接続されている場合、早期に分岐を終了することによって剪定することができます。

頂点は、この枝刈りができるだけ早く発生するように選択されます。 アルゴリズムの変更には関係ないため、詳細は省略します。

基本的なバックトラッキングのストレージ要件は比較的控えめです。 以前の最大派閥に関する情報は保持する必要はありません。 私たちがテストする改善では、速度に焦点を当てるだけでなく、メモリ使用量も改善します。 したがって、そのような制限は、いかなる場合においても、私たちの試験された方法のいずれにも法外ではありません。 それにもかかわらず、一部の環境では、メモリ使用率が極端になる可能性があります。 私たちは興味のある読者を参照してください。

私たちの基本的なバックトラッキングの実装は、私たちが今改善しようとすることができる初期のベンチマークとして機能します。

単一の最大クリークを見つける

最大クリークファインダー（MCF）という用語を使用して、最大サイズの単一クリークを見つけるために実装および改良したソフト MCFは、よく知られているFPTアプローチを頂点カバーに反映する分岐戦略とともに、一連の前処理ルールを採用しています。 まず、合理的に大きなクリークを迅速に見つけるために、単純な貪欲なヒューリスティックを呼び出します。 このcliqueは、最大cliqueサイズに下限を置くため、前処理に使用されます。 これら二つの頂点は初期クリークCを形成し、その後、すべてのCに隣接する最高次数の頂点を選択することによって反復的に拡張される。 |C|は最大クリークサイズの下限であるため、次数が|C-1|未満のすべての頂点を元のグラフから永久に削除できます。 次に、次数n-1のすべての頂点は一時的にグラフから削除されますが、最大クリークの一部でなければならないため、リストに保持されます。 MCFは、分岐を導くために以前に使用されていた色の前処理の新しい形を利用しています。 この形式の前処理は、次のようにグラフを縮小しようとします。 最大クリークのサイズに関する既知の下限kが与えられた場合、各頂点vについて、vとその近傍に高速貪欲な色付けを適用します。 これらの頂点をk色よりも少ない色で着色できる場合、vは最大クリークの一部にすることはできず、グラフから削除されます。 このようにグラフが縮小されると、MCFは頂点に対して標準的な再帰分岐を使用し、各分岐は頂点が最大クリークにあるかどうかを前提とします。

インテリジェントバックトラック

単一の最大クリークを見つけることができる相対的な有効性を考えると、そのクリークのサイズの知識がすべての最大クリークを列挙するのに役立つかどうかを考慮することは論理的であるようです。 結局のところ、最大クリークサイズkの知識は、基本的なバックトラッキングアルゴリズムの小さな、簡単な変更につながります。 具体的には、検索ツリー内の各ノードで、COMPSUBと候補の和集合にk個未満の頂点があるかどうかを確認します。 もしそうなら、その枝はサイズkのクリークにつながることができないので、私たちは戻ります。 図2を参照してください。 変更は軽微に見えるかもしれませんが、検索ツリーの結果の剪定は、検索スペースの大幅な削減につながる可能性があります。 分岐へのこのマイナーな変更に加えて、改善されたバックトラッキングアルゴリズムに送信する前に、グラフを減らすために、前述のように色の前処理を適用します。 色の前処理は、インテリジェントなバックトラッキングと呼ばれるマイナーな分岐の変更と組み合

パラメータ化された列挙

MCFが頂点分岐戦略を採用していることを考えると、1つだけでなくすべての最大クリークを列挙するように変更できるかど MCFはまた、すべての最大クリークの列挙をもたらす簡単な変更に役立つことが判明しました。 この変更は、これまでに見つかった最大サイズのすべてのクリークのグローバルリストを維持することです。 より大きな最大クリークが見つかると、リストはフラッシュされ、新しい最大クリークのみが含まれるように更新されます。 検索スペースが使い果たされると、最大クリークのリストが出力されます。

ただし、インターリーブ中に使用される特定の前処理ルールは無効であることに注意するために特別な注意を払わなければなりません。 例えば、葉の頂点の除去を考えてみましょう。 クリーク類似は、次数n-2の頂点を見つけ、その孤立した非隣接を取り除くことです。 このルールは、破棄された頂点に応じて任意のクリークを無視するため、単一の最大クリークのみが必要であることを明確に前提としています。 したがって、この特定の前処理規則は、分岐が開始されると省略する必要があります。

Maximum clique covers

MCFを繰り返し呼び出すことができるブラックボックスサブルーチンと見なすと、分離された最大クリークの最大セットを計算するための単純な欲張りアルゴリズムで使用することができます。 最大クリークを計算し、グラフから削除し、最大クリークのサイズが小さくなるまで反復します。 このような集合を計算する利点を探るために、以下の概念を導入する：

定義1G=(V,E)の最大クリーク被覆は、Gの各最大クリークが被覆にいくつかの頂点を含むという性質を持つ集合V’∈Vである。

互いに素な最大クリークの最大集合に含まれるすべての頂点の和集合は、すべての最大クリークがそのような集合と重複しなければならないので、もちろん最大クリーク被覆（以後MCC）である。 これは有用な還元アルゴリズムにつながる。 MCCの少なくとも一つのメンバーに隣接していない任意の頂点は、最大クリークにすることはできませんので、削除することができます。

実際には、以前のバックトラッキングアルゴリズムの前にMCCを適用すると、わずかな改善しか得られないことがわかります。 しかし、MCCの概念は、個々の頂点に基づいてはるかに強力なアプローチにつながります。 MCCによる改善は次のアプローチに包含されるため、MCC自体をテストすることはありません。

Essential vertex sets

Mccアルゴリズムの調査では、通常、MCFに既に組み込まれている前処理ルールよりもグラフのサイズを小さくしないことが明らかになりました。 たとえば、MCFはすでに最大クリークサイズの下限を迅速に検出し、この上限よりも次数が低い頂点を削除します。 しかし、詳細に検討すると、この論文の会議バージョンで最初にテストした74の75のグラフでは、MCCで必要なのは1つのクリークだけであることがわかりま つまり、一つの最大派閥は、他のすべての最大派閥をカバーしていました。 そして、100グラフの私たちの現在のテストベッドでは、すべての場合に単一の最大クリークは、MCCのために十分です。 実際、これは私たちの経験と密接に一致しており、通常、私たちが定期的に遭遇するトランスクリプトミックグラフの大きな派閥の間で高い重複を見 この観察に基づいて、私たちは今、MCCの概念を洗練します。 最大クリークをクリークでカバーするのではなく、個々の頂点で最大クリークをカバーします。

我々は、すべての最大クリークに含まれているものとして本質的な頂点を定義します。 もちろん、多くの重複する最大クリークが含まれている場合でも、与えられたグラフにそのような頂点がない可能性があります。 しかし、大規模なトランスクリプトミックグラフの経験的テストは、圧倒的な数が多数の本質的な頂点を含むことを示しています。 そして、グラフを減らす目的のために、1つでも十分です。 本質的な頂点は、その非近傍をすべて削除できるため、非常に役立つ可能性があります。 任意のグラフGについて、ω(G)>ω(G/v)はvがすべての最大クリークをカバーすることと、ω(G)はgの最大クリークサイズであることが必要である。

は、すべての必須頂点の集合であると定義する。 図3に示すように、Essential Set(ES)アルゴリズムは、グラフ内のすべての必須頂点を検索します。 次に、各本質的な頂点について、その頂点のすべての非近傍を削除することによってグラフを縮小します。 ESアルゴリズムは、バックトラッキングMCEアルゴリズムのいずれかと組み合わせて実行することも、実際には、元のグラフからのすべての最大クリークを含む縮小されたグラフであるため、任意の方法でMCEを実行するアルゴリズムの前に実行することもできます。 私たちのテストが示すように、ESアルゴリズムによって提供されるランタイムの改善は劇的になります。

実装

すべてのアルゴリズムをCまたはC++で実装しました。 このコードは、Ubuntu Linuxバージョン10.04.2オペレーティングシステム上のGCC4.4.3コンパイラと、Debian Linuxバージョン3.1下のGCC3.3.5コンパイラを使用してコ すべてのタイミングは、並行プロセスからのタイミングに影響を与えないように、クラスタの専用ノード上の後者のDebian環境で行われました。 各ノードには3.20GHzで動作するデュアルコアIntel Xeonプロセッサと4GBのメインメモリが搭載されていた。

テスト

このホワイトペーパーの会議バージョンでは、アルゴリズムの改善をテストするために、それぞれ25のしきい値で三つの異なるデータセットを使用して合計75のグラフを導出しました。 これらのグラフは確かに概念の最初の証明として十分でしたが、それらに関して二つの懸念が提起される可能性があります。 第一に、三つのデータセットは、トランスクリプトミックデータの全体的な性質や、そのようなデータに対するアルゴリズム的改善の一般的な有効性の真の感覚を提供するのに十分な大きさのサンプルサイズではないと主張するかもしれません。 そして第二に、3つのデータセットは独自のものであり、一般に公開されていないため、結果はそうでなければ再現可能ではありませんでした。 識別されていないバージョンを取得することは、実行可能ではあるが、再現性のための不必要な難点であった。

ここでは、アルゴリズムの改善をテストするための新しい一連のトランスクリプトミックグラフを作成することで、このような懸念に対処します。 このスイートは、公開されているリポジトリであるGene Expression Omnibus(GEO)から得られた25のデータセットから派生したグラフで構成されています。 データセットごとに、合計100個のグラフに対して、四つの異なるしきい値でグラフが作成されました。 データセットは、実験型、種、およびmRNAマイクロアレイチップ型の合理的に多様なサンプリングを提供するために選択されました。 それらは、8つの異なる種と、時系列、ひずみ、用量、および患者などの多数の異なる実験条件をカバーする。 私たちのグラフはしきい値相関値から導出されるので、12未満の条件を持つデータセットを考慮から除外しました。 非常に少ない条件を使用して計算されたしきい値相関は、許容できないほど大きな率の偽陽性および偽陰性を生成する可能性があります。 条件の数は、12の低値から153の高値までの範囲です。 データセットのうち9つは対数変換されておらず、その場合は対数変換を実行しました。 これらのケースでは、しきい値の相関ではなく相関p値を使用しました。 テストに使用されるGEOデータセットの一覧については、表1を参照してください。

式データから，まず，プローブを表す頂点とエッジ重みを実験条件にわたって計算したＰｅａｒｓｏｎ相関係数とする重み付きグラフを構築した。 次に、選択したしきい値t以上の重みを持つエッジのみを保持することにより、重み付きグラフを重み付けされていないグラフに変換しました。 最小のグラフは3,828個の頂点と310,380個の辺を持ち、最大のグラフは44,563個の頂点と2,052,228個の辺を持っていた。

私たちのテストベッドのグラフの最大クリークの数は8から74486の範囲でした。 以前のテストベッドで見たように、グラフのサイズや密度に基づいて識別可能なパターンはありませんでした。 なぜそのような広範で予測不可能な変動があるのかを尋ねるかもしれません。 最大クリークの数は、グラフの小さな変化に非常に敏感であることが判明しました。 単一のエッジの変更でさえ、大きな効果をもたらす可能性があります。 たとえば、サイズkの一意の最大クリークと、サイズk-1の互いに素なクリークのホストを持つグラフを考えてみましょう。 最大のクリークであったものから一つのエッジだけを削除すると、現在、サイズk-1の多くの最大のクリークが生じる可能性があります。 エッジの追加はもちろん同様の効果を持つことができます。 実例については、図4を参照してください。

各グラフ上の各アルゴリズムについて，他のプロセスからの干渉を避けるためにクラスタの専用ノード上でタイミングを行った。 アルゴリズムが24時間以内に完了しなかった場合、それは停止され、グラフは解決されていないとみなされました。 私たちは、テストしていた五つのアルゴリズムの上にグラフのランタイムを広げるためにしきい値を選択しました。 すべてではないにしても、アルゴリズムの大部分がグラフを解くように、最大の（相関p値の場合は最小の）しきい値を選択しました。 最小（相関p値の場合には最大）しきい値を選択し、アルゴリズムの少なくとも1つが、すべてではないが、グラフを解くようにした。

各グラフで、基本的なバックトラッキング、インテリジェントなバックトラッキング、およびパラメータ化されたMCの性能を計時しました。 次に、ESを使用してグラフを縮小し、インテリジェントなバックトラッキングとパラメータ化されたMCで再テストしました。 予想されるように、基本的なバックトラッキングは非競争的であることが判明しました。 インテリジェントバックトラッキングとパラメータ化されたＭＣは，基本的なバックトラッキングよりも明確で劇的な改善を示した。 図5は、すべての100のテストグラフ上の5つのメソッドのそれぞれのランタイムを示しています。 いくつかの簡単なグラフでは、解決するのに3分もかからないグラフでは、ESのオーバーヘッドが実際には全体的なランタイムのわずかな増加を引き起こ しかし、より困難な場合には、その真の利点が明らかになり、実行時間を一桁以上短縮しました。 そして、二つ以下のアルゴリズムがグラフを解決するすべての場合において、アルゴリズムはインテリジェントなバックトラッキングを持つES、パラメータ化されたMCを持つES、またはその両方であった。