Les blocs protéiques (BP) constituent un alphabet structural qui permettent une bonne approximation du squelette carbonnée des protéines et la compression de l'information 3D en 1D. Leur utilisation a permis d'appréhender sous un nouvel angle la structure des protéines. Cette thèse explore de nouvelles applications des BP pour l'analyse des structures des protéines, leur prédiction et la reconnaissance de leurs repliements. Dans un premier temps, nous utilisons les BP pour une caractérisation fine des régions variables dans les alignements structuraux de protéines homologues. Ces régions peuvent néanmoins présenter des similarités importantes en terme de conformation. Leur caractérisation a permis de les distinguer des régions dont les conformations sont différentes. Nous montrons aussi que les variations intrinsèques de certaines régions comme les boucles au sein d’une protéine ne sont pas corrélées aux différences de conformation observées dans les régions équivalentes entre protéines homologues. Dans une deuxième partie, nous analysons la relation séquence-structure à l'aide de BP par le biais d'une base de données de pentapeptides issus des structures des protéines. Celle-ci a servi de base pour la mise en place d'outils pour la prédiction du squelette carbonnée des protéines (PB-kPRED) et de sa plasticité (PB-SVindex). Nous exposons comment ces prédictions permettent la reconnaissance du repliement des protéines avec un certain succès et l'identification de probables points chauds structuraux et fonctionnels. En dernière partie, nous présentons un nouvel algorithme (FoRSA) pour la reconnaissance du repliement des protéines à l'aide des BP. Cet algorithme s'appuie sur le calcul de la probabilité conditionnelle qu'une séquence adopte un repliement donné et a été testé avec succès sur des protéines tirées de CASP10. Nous montrons que FoRSA peut être utilisé pour l'annotation structurale rapide de génomes entiers. / Analysis of protein structures using structural alphabets has provided new insights into protein function and evolution. We have used a structural alphabet called proteins blocks (PBs) which efficiently approximates protein backbone and allows abstraction of 3D protein structures into 1D PB sequences. This thesis describes applications of PBs for protein structure analysis, prediction and fold recognition. First, PBs were used to provide a refined view of structurally variable regions (SVRs) in homologous proteins in terms of conformationally similar and dissimilar SVRs in which were compiled a database of structural alignments (DoSA). We also show that the inherent conformational variations in loop regions are not correlated to corresponding conformational differences in their homologues. Second, to further analyze sequence-structure relationships in terms of PBs and other structural features, we have set up a database of pentapeptides derived from protein structures. This served as a basis for the knowledge-based prediction of local protein structure in terms of PB sequences (PB-kPRED) and of local structure plasticity (PB-SVindex). We demonstrate the successful applications of PB-kPRED for fold recognition and explored possible identification of structural and functional hotspots in proteins using PB-SVindex. Finally, an algorithm for fold recognition using a structural alphabet (FoRSA) based on calculation of conditional probability of sequence-structure compatibility was developed. This new threading method has been successfully benchmarked on a test dataset from CASP10 targets. We further demonstrate the application of FoRSA for fast structural annotations of genomes.

En biologie structurale, il est couramment admit que la structure tridimensionnelle d'une protéine détermine sa fonction. Ce paradigme permet de supposer que deux protéines possédant des structures tridimensionnelles similaires peuvent partager un ancêtre commun et donc posséder des fonctions similaires. Déterminer la similarité entre deux structures de protéines est une tâche importante qui a é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” (ou CMO), principalement parce qu'elle fournit des scores de similarité pouvant être utilisés pour obtenir de bonnes classifications automatiques des structures de protéines. Dans cette thèse, la comparaison de deux structures de protéines est modélisée comme une recherche de sous-graphe dans des graphes k-partis spécifiques appelés graphes d'alignements, et nous montrons que cette tâche peut être efficacement réalisée en utilisant des techniques avancées issues de l'optimisation combinatoire. Dans la seconde partie de cette thèse, nous modélisons CMO comme une recherche de sousgraphe 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. Même si nous avons réussi à accélérer CMO, la procédure d'alignement requière encore trop de temps de calculs pour envisager des comparaisons à grande échelle. La troisième partie de cette thèse est consacrée à l'accélération de CMO en utilisant des connaissances issues de la biologie structurale. Nous proposons une approche hiérarchique pour résoudre CMO qui est basée sur les structures secondaires des protéines. 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 (root mean squared deviation, ou RMSD). Pour palier à cette faiblesse, dans la dernière partie de cette thèse, nous proposons une nouvelle méthode de comparaison de structures de protéines basée sur les distances internes que nous appelons DAST (pour Distance-based Alignment Search Tool). 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.