Protein structure comparison: from contact map overlap maximisation to distance-based alignment search tool

In molecular biology, a fruitful assumption is that proteins sharing close three dimensional structures may share a common function and in most cases derive from a same ancestor. Computing the similarity between two protein structures is therefore a crucial task and has been extensively investigated. Among all the proposed methods, we focus on the similarity measure called Contact Map Overlap maximisation (CMO), mainly because it provides scores which can be used for obtaining good automatic classifications of the protein structures. In this thesis, comparing two protein structures is modelled as finding specific sub-graphs in specific k-partite graphs called alignment graphs. Then, we model CMO as a kind of maximum edge induced sub-graph problem in alignment graphs, for which we conceive an exact solver which outperforms the other CMO algorithms from the literature. Even though we succeeded to accelerate CMO, the procedure still stays too much time consuming for large database comparisons. To further accelerate CMO, we propose a hierarchical approach for CMO which is based on the secondary structure of the proteins. Finally, although CMO is a very good scoring scheme, the alignments it provides frequently posses big root mean square deviation values. To overcome this weakness, we propose a new comparison method based on internal distances which we call DAST (for Distance-based Alignment Search Tool). It is modelled as a maximum clique problem in alignment graphs, for which we design a dedicated solver with very good performances.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