Optimisation combinatoire et comparaison de structures protéiques

Rumen Andonov (IRISA, équipe Symbiose)

Les fonctions d’une protéine sont étroitement liées avec sa forme/structure tridimensionnelle (3D) et on considère généralement que des protéines avec des formes 3D similaires possèdent aussi des fonctions qui se ressemblent, ce qui donne un grand intérêt aux méthodes de comparaison de structures. A l’heure actuelle il existe de nombreuses approches pour découvrir la similarité entre les structures des protéines.
Dans cet exposé nous nous intéresserons plus en détails à deux de ces approches : plus précisément les approches « contact map overlap (CMO) » et « Vector Alignement Search Tool » (VAST).
Dans l’approche CMO la proximité entre les atomes de carbone alpha de deux résidus est exprimée par une relation binaire « oui-non ». La structure 3D est présentée comme un graphe linéaire où les acides aminés sont des sommets et les arcs représentent les relations binaires entre eux. Le nombre maximum d’arcs communs peut être défini comme une mesure de similarité entre deux structures.Dans l’approche VAST la structure d’une protéine est considérée comme une suite ordonnée de structures secondaires modélisées par des vecteurs dans l’espace. On met cette fois en relation des couples de structures secondaires. On peut associer une valeur RMSD aux arcs de cette relation. La similarité entre deux structures repose sur les valeurs maximales des ensembles d’arcs qui sont tous reliés entre eux.
Nous allons montrer comment ces deux approches peuvent être formalisées et unifiées dans un même modèle mathématique et se ramènent à des problèmes d’optimisation combinatoire très similaires. Nous verrons également pourquoi ces problèmes sont difficiles à résoudre et comment l’avancée dans leur résolution peut aider le biologiste dans son analyse.