Élaboration d'un algorithme efficace de recherche de cliques

Résumé

Ce mémoire concerne la recherche d'un algorithme efficace pour résoudre un problème rencontré dans une méthode d'alignement de séquences de protéines. Cette méthode a été développée par l'unité de biologie quantitative des Facultés Notre-Dame de la Paix. Ce problème correspond en réalité à un problème d'optimisation combinatoire bien connu en théorie des graphes : "La recherche de toutes les cliques maximums dans un graphe G = (V,E)". Une clique dans un graphe G est un sous-graphe complet maximal. Ce problème étant NP-complet, l'existence d'un algorithme polynomial pour le résoudre semble improbable. Les algorithmes généralement trouvés dans la littérature solutionnent le problème en un temps raisonnable mais exponentiel. Ils se basent sur des méthodes de recherche avec rebroussement et des méthodes "branch-and-bound". Nous proposons, ici un algorithme, basé également sur ces techniques, mais tout à fait original de par la condition limite ("bound condition") qu'il utilise. Notre problème est en fait un cas particulier de la recherche de toutes les cliques maximums: d'une part, la taille des cliques maximums est connue et d'autre part, nous travaillons en population groupée. Il existe des groupes de sommets dans le graphe, et une clique ne peut être formée que des sommets appartenant à des groupes différents. Et les cliques recherchées doivent absolument faire intervenir un sommet de chaque groupe. Nous recherchons donc les cliques d'une taille donnée maximum, égale au nombre de groupes de sommets. Il s'avère que la comparaison des temps d'exécution des différents algorithmes montrent un avantage pour l'algorithme que nous avons conçu.

la date de réponse	1993
langue originale	Français
L'institution diplômante	Universite de Namur
Superviseur	Jean FICHEFET (Promoteur) & Eric Depiereux (Promoteur)