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

En utilisant l’algorithme d’énumération de la clique maximale fondamental dû à Bron et Kerbosch comme référence, nous avons conçu, implémenté et testé de manière approfondie trois améliorations algorithmiques, la dernière basée sur des observations sur la nature des graphiques produits par des données transcriptomiques. En plus de décrire ces améliorations, nous décrirons notre outil existant pour trouver une clique maximale unique, basé sur la théorie de la traçabilité à paramètres fixes (FPT). Un tel outil est essentiel pour les trois améliorations, car les deux premiers reposent sur la connaissance de la taille maximale de la clique, et le dernier utilise l’outil de recherche de clique maximale comme sous-programme. Tous les codes sont écrits en C/C++ et compilés sous Linux. Pour les tests, nous utilisons 100 graphiques dérivés de 25 jeux de données différents qui sont accessibles au public sur GEO. Nous nous concentrons sur les données transcriptomiques, compte tenu de leur abondance, et nous évitons les données synthétiques, ayant appris depuis longtemps que les algorithmes efficaces pour l’un ont peu d’incidence sur l’autre. (Les correspondances pathologiques notées dans for vertex cover peuvent être étendues à la clique, mais elles sont également très peu pertinentes pour les données réelles.) Dans le but d’améliorer les performances, nous examinons la structure des graphes transcriptomiques et explorons la notion de couvertures de clique maximales et d’ensembles de sommets essentiels. En effet, nous constatons qu’avec le bon prétraitement, nous sommes en mesure d’adapter les algorithmes aux types de données que nous rencontrons régulièrement, et que nous pouvons désormais résoudre des instances auparavant considérées comme inattaquables.

Algorithmes

Dans les sections suivantes, nous décrivons chacun des algorithmes MCE que nous avons implémentés et testés. Le premier est l’algorithme de Bron et de Kerbosch, que nous appelons le retour en arrière de base et que nous utilisons comme référence. Puisque toutes nos améliorations ultérieures utilisent un algorithme qui trouve une seule clique maximale, nous décrivons ensuite notre outil existant, appelé Maximum Clique Finder (MCF), qui fait exactement cela. Nous modifions ensuite l’algorithme de retour en arrière de base pour profiter du fait que nous voulons seulement trouver le maximum de cliques et pouvons calculer rapidement la taille maximale de la clique. Nous appelons cette approche un retour en arrière intelligent, car elle revient activement tôt à partir de branches qui ne conduiront pas à une clique maximale. Nous modifions ensuite MCF lui-même pour énumérer toutes les cliques maximales, une approche que nous appelons Clique Maximale Paramétrée ou MC Paramétrée. Dans un sens, il s’agit d’une autre approche de retour en arrière qui va encore plus loin pour exploiter le fait que nous ne voulons trouver que le maximum de cliques. Enfin, sur la base d’observations sur les propriétés des graphes biologiques, nous introduisons les concepts de couvertures de clique maximales et d’ensembles de sommets essentiels, et les appliquons pour améliorer considérablement l’exécution des algorithmes de retour en arrière.

Retour en arrière de base

La publication séminale de la clique maximale décrit deux algorithmes. Une présentation détaillée de la seconde, qui est une version améliorée de la première, est fournie. C’est cette deuxième méthode, plus efficace, que nous mettons en œuvre et testons. Nous l’appellerons ici un retour en arrière de base. Toutes les cliques maximales sont énumérées avec une traversée d’arbre de recherche en profondeur d’abord. Les principales structures de données utilisées sont trois ensembles globaux de sommets : COMPSUB, CANDIDATS et NON. COMPSUB contient les sommets de la clique actuelle et est initialement vide. CANDIDATS contient des sommets inexplorés qui peuvent étendre la clique actuelle et contient initialement tous les sommets du graphe. NOT contient des sommets explorés qui ne peuvent pas étendre la clique actuelle et est initialement vide. Chaque appel récursif effectue trois étapes:

• Sélectionnez un sommet v dans les CANDIDATS et déplacez-le vers COMPSUB.

• Supprimez tous les sommets non adjacents à v des deux CANDIDATS et NON. À ce stade, si les deux CANDIDATS et NON sont vides, alors COMPSUB est une clique maximale. Si c’est le cas, affichez COMPSUB en tant que cique maximale et continuez l’étape suivante. Sinon, appelez récursivement l’étape précédente.

• Déplacer v de COMPSUB à NOT.

Notez que NOT est utilisé pour éviter de générer des cliques maximales en double. L’arbre de recherche peut être élagué en terminant une branche tôt si un sommet de NOT est connecté à tous les sommets des CANDIDATS.Les sommets

sont sélectionnés de manière à ce que cet élagage se produise le plus tôt possible. Nous omettons les détails car ils ne sont pas pertinents pour nos modifications de l’algorithme.

Les exigences de stockage du retour en arrière de base sont relativement modestes. Aucune information sur les cliques maximales précédentes ne doit être conservée. Dans les améliorations que nous allons tester, nous nous concentrons sur la vitesse mais améliorons également l’utilisation de la mémoire. Ainsi, de telles limitations ne sont en aucun cas prohibitives pour l’une de nos méthodes testées. Néanmoins, dans certains environnements, l’utilisation de la mémoire peut être extrême. Nous renvoyons le lecteur intéressé à.

Notre implémentation de Backtracking de base sert de référence initiale sur laquelle nous pouvons maintenant essayer de nous améliorer.

Trouver une seule clique maximale

Nous utilisons le terme de Recherche de Clique maximale (MCF) pour désigner le logiciel que nous avons implémenté et affiné pour trouver une seule clique de plus grande taille. MCF utilise une suite de règles de prétraitement ainsi qu’une stratégie de ramification qui reflète l’approche FPT bien connue de la couverture des sommets. Il invoque d’abord une simple heuristique gourmande pour trouver rapidement une clique raisonnablement grande. Cette clique est ensuite utilisée pour le prétraitement, car elle met une limite inférieure sur la taille maximale de la clique. L’heuristique fonctionne en choisissant le sommet de degré le plus élevé, v, puis en choisissant le voisin de degré le plus élevé de v. Ces deux sommets forment une clique initiale C, qui est ensuite étendue de manière itérative en choisissant le sommet de degré le plus élevé adjacent à tout C. À chaque itération, tout sommet non adjacent à tout C est supprimé. Le processus continue jusqu’à ce qu’il n’y ait plus de sommets en dehors de C. Puisque |C| est une borne inférieure sur la taille maximale de la clique, tous les sommets de degré inférieur à |C-1| peuvent être définitivement supprimés du graphe d’origine. Ensuite, tous les sommets de degré n-1 sont temporairement supprimés du graphe, mais conservés dans une liste car ils doivent faire partie de toute clique maximale. MCF exploite une nouvelle forme de prétraitement des couleurs, utilisée précédemment pour guider la ramification. Cette forme de prétraitement tente de réduire le graphique comme suit. Étant donné une borne inférieure k connue sur la taille de la clique maximale, pour chaque sommet v, nous appliquons une coloration gourmande rapide à v et à ses voisins. Si ces sommets peuvent être colorés avec moins de k couleurs, alors v ne peut pas faire partie d’une clique maximale et est supprimé du graphe. Une fois que le graphe est ainsi réduit, MCF utilise une ramification récursive standard sur les sommets, où chaque branche suppose que le sommet est ou n’est pas dans la clique maximale.

Retour en arrière intelligent

Compte tenu de l’efficacité relative avec laquelle nous pouvons trouver une seule clique maximale, il semble logique de considérer si la connaissance de la taille de cette clique peut être utile pour énumérer toutes les cliques maximales. Il s’avère que la connaissance de la taille maximale de la clique k entraîne un petit changement simple dans l’algorithme de retour en arrière de base. Plus précisément, à chaque nœud de l’arborescence de recherche, nous vérifions s’il y a moins de k sommets dans l’union de COMPSUB et de CANDIDATS. Si c’est le cas, cette branche ne peut pas conduire à une clique de taille k, et nous revenons donc. Voir Figure 2. Bien que la modification puisse sembler mineure, l’élagage de l’arbre de recherche qui en résulte peut entraîner une réduction substantielle de l’espace de recherche. En plus de cette modification mineure de la ramification, nous appliquons le prétraitement des couleurs comme décrit précédemment pour réduire le graphique avant de le soumettre à l’algorithme de retour en arrière amélioré. Le prétraitement des couleurs combiné au changement mineur de ramification que nous appelons le retour en arrière intelligent.

Énumération paramatérialisée

Étant donné que MCF utilise une stratégie de ramification des sommets, nous avons cherché à savoir si elle pouvait être modifiée pour énumérer non seulement une, mais toutes les cliques maximales. Il s’avère que MCF se prête également à une modification simple qui entraîne l’énumération de toutes les cliques maximales. La modification consiste simplement à maintenir une liste globale de toutes les cliques de la plus grande taille trouvée jusqu’à présent. Chaque fois qu’une clique maximale plus grande est trouvée, la liste est vidée et actualisée pour ne contenir que la nouvelle clique maximale. Lorsque l’espace de recherche est épuisé, la liste des cliques maximales est affichée.

Il faut cependant prendre un soin particulier à noter que certaines règles de prétraitement utilisées lors de l’entrelacement ne sont plus valides. Considérons, par exemple, la suppression d’un sommet de feuille. L’analogue de la clique consiste à trouver un sommet de degré n-2 et à supprimer son seul non-voisin. Cette règle suppose clairement qu’une seule clique maximale est souhaitée, car elle ignore toute clique en fonction du sommet rejeté. Par conséquent, cette règle de prétraitement particulière doit être omise une fois que la ramification a commencé.

Couvre la clique maximale

Si nous considérons MCF comme un sous-programme de boîte noire pouvant être appelé à plusieurs reprises, il peut être utilisé dans un algorithme simple et gourmand pour calculer un ensemble maximal de cliques maximales disjointes. Nous calculons simplement une clique maximale, la supprimons du graphique et itérons jusqu’à ce que la taille d’une clique maximale diminue. Pour explorer les avantages du calcul d’un tel ensemble, nous introduisons la notion suivante :

Définition 1 Une couverture de clique maximale de G =(V, E) est un ensemble V’ ⊆ V avec la propriété que chaque clique maximale de G contient un sommet dans la couverture.

L’union de tous les sommets contenus dans un ensemble maximal de cliques maximales disjointes est bien sûr une couverture de clique maximale (désormais MCC), car toutes les cliques maximales doivent se chevaucher avec un tel ensemble. Cela conduit à un algorithme de réduction utile. Tout sommet non adjacent à au moins un membre d’un MCC ne peut pas être dans une clique maximale, et peut donc être supprimé.

En pratique, nous constatons que l’application de MCC avant les algorithmes de retour en arrière antérieurs ne donne qu’une amélioration marginale. Le concept de MCC conduit cependant à une approche beaucoup plus puissante basée sur des sommets individuels. Puisque toute amélioration apportée par MCC est subsumée par l’approche suivante, nous ne testons pas MCC par lui-même.

Ensembles de sommets essentiels

Notre étude de l’algorithme MCC a révélé qu’il ne réduit généralement pas plus la taille du graphe que les règles de prétraitement déjà incorporées dans MCF. Par exemple, MCF trouve déjà rapidement une borne inférieure sur la taille maximale de la clique et supprime tout sommet de degré inférieur à cette borne. Après un examen plus approfondi, cependant, nous avons constaté que pour 74 des 75 graphiques que nous avons initialement testés pour la version conférence de cet article, une seule clique était nécessaire dans un MCC. C’est-à-dire qu’une clique maximale couvrait toutes les autres cliques maximales. Et dans notre banc d’essai actuel de 100 graphiques, une seule clique maximale suffit dans tous les cas pour un MCC. En fait, cela coïncide étroitement avec notre expérience, dans laquelle nous voyons généralement un chevauchement élevé entre les grandes cliques dans les graphes transcriptomiques que nous rencontrons régulièrement. Sur la base de cette observation, nous allons maintenant affiner le concept de MCC. Plutôt que de couvrir les cliques maximales avec des cliques, nous couvrons les cliques maximales avec des sommets individuels.

Nous définissons un sommet essentiel comme un sommet contenu dans chaque clique maximale. Bien sûr, il est possible qu’un graphe donné n’ait pas un tel sommet, même s’il contient de nombreuses cliques maximales qui se chevauchent. Mais les tests empiriques de grands graphes transcriptomiques montrent qu’un nombre écrasant contient de nombreux sommets essentiels. Et pour réduire le graphique, même un seul suffira. Un sommet essentiel a le potentiel d’être extrêmement utile, car il nous permet de supprimer tous ses non-voisins. Nous utilisons l’observation suivante : pour tout graphe G, ω(G) > ω(G/v) si et seulement si v couvre toutes les cliques maximales, où ω(G) est la taille maximale de la clique de G.

Nous définissons un ensemble essentiel pour être l’ensemble de tous les sommets essentiels. L’algorithme des Ensembles essentiels, tel que décrit à la figure 3, trouve tous les sommets essentiels d’un graphe. Il réduit ensuite le graphe en supprimant, pour chaque sommet essentiel, tous les non-voisins de ce sommet. L’algorithme ES peut être exécuté conjointement avec l’un des algorithmes MCE de retour en arrière, ou même avant tout algorithme qui effectue MCE par n’importe quelle méthode, car sa sortie est un graphe réduit qui contient toujours toutes les cliques maximales du graphe d’origine. Comme le montrent nos tests, l’amélioration de l’exécution offerte par l’algorithme ES peut être spectaculaire.

Implémentation

Nous avons implémenté tous les algorithmes en C ou C++. Le code a été compilé en utilisant le compilateur GCC 4.4.3 sur le système d’exploitation Ubuntu Linux version 10.04.2 ainsi que le compilateur GCC 3.3.5 sous Debian Linux version 3.1. Tous les timings ont été effectués dans ce dernier environnement Debian sur des nœuds dédiés d’un cluster pour s’assurer qu’ils n’affectent pas les timings des processus concurrents. Chaque nœud avait un processeur Intel Xeon dual-core fonctionnant à 3,20 GHz et 4 Go de mémoire principale.

Test

Dans la version conférence de cet article, nous avons utilisé trois ensembles de données différents à 25 seuils chacun pour dériver un total de 75 graphiques sur lesquels tester nos améliorations algorithmiques. Bien que ces graphiques aient certainement suffi comme preuve de concept initiale, deux préoccupations pourraient être soulevées à leur sujet. Premièrement, on pourrait soutenir que trois ensembles de données ne constituent pas une taille d’échantillon suffisamment grande pour donner une idée réelle de la nature globale des données transcriptomiques ou de l’efficacité générale d’une amélioration algorithmique sur ces données, malgré le grand nombre de seuils. Deuxièmement, comme les trois ensembles de données sont propriétaires et ne sont pas accessibles au public, les résultats n’étaient pas aussi facilement reproductibles qu’ils auraient pu l’être autrement. L’obtention de versions anonymisées, bien que possible, était un obstacle inutile à la reproductibilité.

Nous répondons à ces préoccupations ici en créant une nouvelle suite de graphiques transcriptomiques sur lesquels tester nos améliorations algorithmiques. La suite se compose de graphiques dérivés de 25 ensembles de données obtenus à partir du Gene Expression Omnibus (GEO), un référentiel accessible au public. Pour chaque ensemble de données, des graphiques ont été créés à quatre seuils différents, pour un total de 100 graphiques. Les ensembles de données ont été sélectionnés pour fournir un échantillonnage raisonnablement diversifié de type expérimental, d’espèces et de type de puce à puce à ARNm. Ils couvrent 8 espèces différentes et un certain nombre de conditions expérimentales différentes telles que les séries chronologiques, la souche, la dose et le patient. Étant donné que nos graphiques sont dérivés de valeurs de corrélation de seuillage, nous avons exclu de la prise en compte tout ensemble de données comportant moins de 12 conditions. Les corrélations de seuillage calculées en utilisant si peu de conditions peuvent produire des taux de faux positifs et de faux négatifs inacceptables. Le nombre de conditions varie d’un minimum de 12 à un maximum de 153. Neuf des ensembles de données n’avaient pas été transformés en log, auquel cas nous avons effectué une transformation en log. Quatre des ensembles de données contenaient des valeurs manquantes; dans ces cas, nous avons utilisé des valeurs de corrélation p plutôt que des corrélations pour le seuil. Voir le tableau 1 pour une liste des ensembles de données GÉOGRAPHIQUES utilisés pour les tests.

À partir des données d’expression, nous avons d’abord construit des graphes pondérés dans lesquels les sommets représentaient des sondes et les poids des arêtes étaient des coefficients de corrélation de Pearson calculés dans des conditions expérimentales. Nous avons ensuite converti les graphiques pondérés en graphiques non pondérés en ne conservant que les bords dont les poids étaient au-dessus ou au-dessus d’un seuil choisi, t. Pour chaque ensemble de données, nous avons choisi quatre valeurs pour t. Toutes les valeurs de taille / densité se trouvaient dans le spectre généralement observé dans notre travail avec des ensembles de données biologiques. Le plus petit graphe avait 3 828 sommets et 310 380 arêtes ; le plus grand avait 44 563 sommets et 2 052 228 arêtes.

Le nombre de cliques maximales pour les graphiques de notre banc d’essai variait de 8 à 74486. Comme on l’a vu avec notre banc d’essai précédent, il n’y avait pas de motif discernable en fonction de la taille ou de la densité du graphique. On pourrait se demander pourquoi il existe une variabilité aussi large et imprévisible. Il s’avère que le nombre de cliques maximales peut être extrêmement sensible aux petits changements dans le graphique. Même la modification d’un seul bord peut avoir un effet énorme. Considérons, par exemple, un graphique avec une clique maximale unique de taille k, ainsi qu’une multitude de cliques disjointes de taille k-1. La suppression d’un seul bord de ce qui était la plus grande clique peut maintenant entraîner de nombreuses cliques maximales de taille k-1. L’ajout de bord peut bien sûr avoir des effets similaires. Voir la figure 4 pour un exemple illustratif.

Pour chaque algorithme sur chaque graphique, nous avons effectué des timings sur un nœud dédié d’un cluster pour éviter les interférences d’autres processus. Si l’algorithme ne s’est pas terminé dans les 24 heures, il a été arrêté et le graphique a été réputé n’avoir pas été résolu. Nous avons choisi des seuils pour répartir les temps d’exécution des graphiques sur les cinq algorithmes que nous testions. Le seuil le plus grand (le plus petit dans le cas de la valeur p de corrélation) a été sélectionné de sorte qu’une majorité des algorithmes, sinon tous, résolvent le graphique. Le seuil le plus petit (le plus grand dans le cas de la valeur p de corrélation) a été sélectionné de sorte qu’au moins un des algorithmes, mais pas tous, résolve le graphique.

Sur chaque graphique, nous avons chronométré les performances du Retour en arrière de base, du Retour en Arrière Intelligent et du MC Paramétré. Nous avons ensuite réduit les graphiques en utilisant ES et retesté avec un retour en arrière intelligent et un MC paramétré, auquel cas les temps d’exécution incluent à la fois l’étape de réduction et l’étape d’énumération. Comme prévu, le retour en arrière de base s’est avéré non compétitif. Le retour en arrière intelligent et le MC paramétré ont montré une amélioration distincte, souvent spectaculaire, par rapport au retour en arrière de base. La figure 5 montre les temps d’exécution de chacune des cinq méthodes sur les 100 graphiques de test. Sur certains des graphiques les plus faciles, ceux qui prennent moins de trois minutes à résoudre, la surcharge d’ES a en fait provoqué une légère augmentation de l’exécution globale. Mais dans les cas les plus difficiles, son véritable avantage est devenu évident, réduisant l’exécution d’un ordre de grandeur ou plus. Et dans tous les cas où deux algorithmes ou moins résolvaient le graphique, l’algorithme était soit ES avec un retour en arrière intelligent, soit ES avec un MC paramétré, ou les deux.