Nos tutelles

CNRS

Nos partenaires


Accueil > Publications > Thèses > Archives Thèses > Thèses 2013 - 2014

DHIFLI Wajdi


Fouille de Sous-graphes Basée sur la Topologie et la Connaissance du Domaine : Application sur les Structures 3D de Protéines

Mercredi 11 décembre 2013 - 14 h 30 - Salle A102 - ISIMA

Cette thèse est à l’intersection de deux domaines de recherche en plein expansion, à savoir la fouille de données et la bio-informatique. Avec l’émergence des bases de graphes au cours des dernières années, de nombreux efforts ont été consacrés à la fouille des sous-graphes fréquents. Mais le nombre de sous-graphes fréquents découverts est exponentiel, cela est due principalement à la nature combinatoire des graphes. Beaucoup de sous-graphes fréquents ne sont pas pertinents parce qu’ils sont redondants ou tout simplement inutiles pour l’utilisateur. En outre, leur nombre élevé peut nuire ou même rendre parfois irréalisable toute utilisation ultérieure. La redondance dans les sous-graphes fréquents est principalement due à la similarité structurelle et / ou sémantique, puisque la plupart des sous-graphes découverts diffèrent légèrement dans leur structures et peuvent exprimer des significations similaires ou même identiques.

Dans cette thèse, nous proposons deux approches de sélection des sous-graphes représentatifs parmi les fréquents afin d’éliminer la redondance. Chacune des approches proposées s’intéresse à un type spécifique de redondance. La première approche s’adresse à la redondance sémantique où la similarité entre les sous-graphes est mesurée en fonction de la similarité entre les étiquettes de leurs nœuds, en utilisant les connaissances de domaine. La deuxième approche s’adresse à la redondance structurelle où les sous-graphes sont représentés par des descripteurs topologiques définis par l’utilisateur, et la similarité entre les sous-graphes est mesurée en fonction de la distance entre leurs descriptions topologiques respectives.

Les principales données d’application de cette thèse sont les structures 3D des protéines. Ce choix repose sur des raisons biologiques et informatiques. D’un point de vue biologique, les protéines jouent un rôle crucial dans presque tous les processus biologiques. Ils sont responsables d’une variété de fonctions physiologiques. D’un point de vue informatique, nous sommes intéressés à la fouille de données complexes. Les protéines sont un exemple parfait de ces données car elles sont faites de structures complexes composées d’acides aminés interconnectés qui sont eux-mêmes composées d’atomes interconnectés. Des grandes quantités de structures protéiques sont actuellement disponibles dans les bases de données en ligne. Les structures 3D des protéines peuvent être transformées en graphes où les acides aminés représentent les nœuds du graphe et leurs connexions représentent les arêtes. Cela permet d’utiliser des techniques de fouille de graphes pour les étudier. L’importance biologique des protéines et leur complexité ont fait d’elles des données d’application appropriées pour cette thèse.

Jury :
Prof. Mohammed Javeed Zaki (Rensselaer Polytechnic Institute, USA) - Rapporteur
Prof. Abdoulaye Baniré Diallo (Université du Québec à Montréal, Canada) - Rapporteur
Prof. Jan Ramon (Katholieke Universiteit Leuven, Belgium) - Rapporteur
DR. David W. Ritchie (INRIA, Nancy, France) - Examinateur
DR. Jean Sallantin (LIRMM, Montpellier, France) - Examinateur
DR. Jean-François Gibrat (INRA, Jouy-en-Josas, France) - Examinateur
Dr. Annegret Wagler (LIMOS, Clermont-Ferrand, France) - Examinateur
Prof. MEPHU NGUIFO Engelbert (LIMOS, Clermont-Ferrand, France) - Examinateur