Abstract EN:

Une hypothèse féconde de la biologie structurale est que les protéines partageant des structures tri-dimensionnelles similaires sont susceptibles de partager des fonctions similaires et de provenir d'un ancêtre commun. Déterminer la similarité entre deux structures protéiques est une tâche importante qui à été largement étudiée. Parmi toutes les méthodes proposées, nous nous intéressons à la mesure de similarité appelée Maximisation du Recouvrement de Cartes de Contacts (CMO). Dans cette thèse, nous proposons un cadre général pour modéliser la comparaison de deux structures protéiques dans des graphes k-partis spécifiques appelés graphes d'alignements. Puis, nous modélisons CMO comme une recherche de sous-graphe maximum induit par les arêtes dans des graphes d'alignements, problème pour lequel nous proposons un solveur exact qui surpasse les autres algorithmes de la littérature. Cependant, la procédure d'alignement requière encore trop de temps de calculs pour envisager des comparaisons à grande échelle. Afin d'accélérer davantage CMO, nous proposons une approche hiérarchique basée sur les structures secondaires. Enfin, bien que CMO soit une très bonne mesure de similarité, les alignements qu'elle fournit possèdent souvent de fortes valeurs de déviation (RMSD). Pour palier à cette faiblesse, nous proposons une nouvelle méthode de comparaison basée sur les distances internes que nous appelons DAST. Elle est modélisée comme une recherche de clique maximum dans des graphes d'alignements, pour laquelle nous présentons un solveur dédié montrant de très bonnes performances.