Grâce aux récents progrès technologiques et à l'arrivée des séquenceurs de nouvelle génération, la quantité de données génomiques croît exponentiellement, alors que l'écart avec le nombre de structures résolues se creuse. Dans l'idéal, on aimerait pouvoir prédire par informatique la structure 3D de n'importe quelle protéine à partir de l'information de séquence seule, même en l'absence d'homologie. En effet, en dessous de 30% d'identité de séquence, les mesures de similarité de séquences ne sont plus suffisantes pour détecter l'homologie. Il faut donc mettre en place d'autres méthodes afin de venir à bout de cette zone d'ombre. Pour une structure donnée (et donc une fonction biologique), on ne dispose souvent que d'une petite quantité de séquences natives y correspondant, et parfois assez peu identiques. Il est alors difficile de construire un profil de recherche d'homologues pour retrouver ces séquences dont on ne connaîtrait pas la structure. Alors comment disposer de bases de données de séquences plus conséquentes pour chaque structure ? Ainsi, le design computationnel de protéine (CPD) tente de répondre à cette problématique : si l'on connaît un repliement, est-il possible de retrouver l'ensemble des séquences qui lui correspondent ? Le principe du CPD consiste à identifier parmi toutes les séquences compatibles avec le repliement d'intérêt, celles qui vont conférer à la protéine, la fonction désirée. La procédure générale est réalisée en deux étapes. La première consiste à calculer une matrice d'énergie contenant les énergies d'interactions entre toutes les paires de résidus de la protéine en autorisant successivement tous les types d'acides aminés dans toutes leurs conformations possibles. La seconde étape, ou "phase d'optimisation", consiste à explorer simultanément l'espace des séquences et des conformations afin de déterminer la combinaison optimale d'acides aminés étant donné le repliement de départ. Une première phase d'analyse de covariances de positions d'alignements de séquences théoriques a été menée. Nous avons ainsi pu mettre au point une méthode statistique pour repérer des ensembles de positions qui muteraient ensemble pour une structure donnée. La construction d'un profil avec toutes ces séquences théoriques moyennant trop l'information en acides aminés, nous avons pu améliorer la recherche d'homologues en construisant plusieurs profils à partir de groupes de séquences classées grâce à des motifs sur ces positions considérées comme covariantes. Pour mieux appréhender la qualité de ces prédictions de séquences théoriques, il fallait mettre en place un protocole de sélection des meilleurs protéines mutantes afin de les tester in vivo. Mais comment déterminer qu'une séquence théorique est meilleure qu'une autre? Sur quels critères se baser pour les caractériser? Aussi, un ensemble de descripteurs a été choisi, permettant de trier sur plusieurs critères les séquences théoriques pour n'en choisir qu'une vingtaine. Ensuite, ces protéines mutantes ont été soumises à des simulations de dynamique moléculaire afin d'évaluer leur stabilité théorique. Pour quelques protéines mutantes plus prometteuses, nous avons réalisé des expériences de sur-expression, de purification et de détermination structurale, tentant d'obtenir une validation biologique du modèle de CPD. Ces protocoles d'analyse et de validation semblent être de bons moyens permettront à notre équipe de tester d'autres protéines mutantes dans l'avenir. Ils pourront ainsi modifier des paramètres lors de la génération par CPD et s'appuyer sur des résultats expérimentaux pour les ajuster.

Cette thèse porte sur deux sujets intrinsèquement liés : le calcul de la constante de normalisation d’un champ de Markov et l’estimation de l’affinité de liaison d’un complexe de protéines. Premièrement, afin d’aborder ce problème de comptage #P complet, nous avons développé Z*, basé sur un élagage des quantités de potentiels négligeables. Il s’est montré plus performant que des méthodes de l’état de l’art sur des instances issues d’interaction protéine-protéine. Par la suite, nous avons développé #HBFS, un algorithme avec une garantie anytime, qui s’est révélé plus performant que son prédécesseur. Enfin, nous avons développé BTDZ, un algorithme exact basé sur une décomposition arborescente qui a fait ses preuves sur des instances issues d’interaction intermoléculaire appelées “superhélices”. Ces algorithmes s’appuient sur des méthodes issuse des modèles graphiques : cohérences locales, élimination de variable et décompositions arborescentes. A l’aide de méthodes d’optimisation existantes, de Z* et des fonctions d’énergie de Rosetta, nous avons développé un logiciel open source estimant la constante d’affinité d’un complexe protéine protéine sur une librairie de mutants. Nous avons analysé nos estimations sur un jeu de données de complexes de protéines et nous les avons confronté à deux approches de l’état de l’art. Il en est ressorti que notre outil était qualitativement meilleur que ces méthodes. / This thesis is focused on two intrinsically related subjects : the computation of the normalizing constant of a Markov random field and the estimation of the binding affinity of protein-protein interactions. First, to tackle this #P-complete counting problem, we developed Z*, based on the pruning of negligible potential quantities. It has been shown to be more efficient than various state-of-the-art methods on instances derived from protein-protein interaction models. Then, we developed #HBFS, an anytime guaranteed counting algorithm which proved to be even better than its predecessor. Finally, we developed BTDZ, an exact algorithm based on tree decomposition. BTDZ has already proven its efficiency on intances from coiled coil protein interactions. These algorithms all rely on methods stemming from graphical models : local consistencies, variable elimination and tree decomposition. With the help of existing optimization algorithms, Z* and Rosetta energy functions, we developed a package that estimates the binding affinity of a set of mutants in a protein-protein interaction. We statistically analyzed our esti- mation on a database of binding affinities and confronted it with state-of-the-art methods. It appears that our software is qualitatively better than these methods.