Cette thèse s'intéresse à deux sujets intrinsèquement liés : le calcul de la constante de normalisation d'un champs de Markov et l'estimation de l'affinité de liaison entre deux protéine.
Nous avons développé plusieurs algorithmes attaquant un problème de comptage #P-complet en se basant sur l'idée d'obtenir une approximation de la fonction de partition avec garantie déterministe. Ces algorithmes sont couplés avec des méthodes issues des modèles graphiques comme les cohérences locales, HBFS, l'élimination de variable ou encore la décomposition arborescente. En particulier, le principal algorithme de cette thèse, nommé Z*, basé sur un élagage de sous-arbre négligeables, s'est montré plus performant que les méthodes de l'état de l'art sur des instances issues d'interaction protéine-protéine. De plus, les deux autres algorithmes ont prouvé qu'ils pouvaient être une avancée dans le domaine des problèmes de comptage.
Une application concrète et directe du calcul de la fonction de partition est l'estimation de l'affinité entre deux systèmes de protéines. A l'aide de Z* et d'une fonction d'énergie originaire de Rosetta, nous avons développé un package permettant d'estimer la constante d'affinité sur une large librairie de mutant d'un complexe protéines-protéines. Nous avons analysé statistiquement notre estimation sur une base de données expérimentales de constantes d'affinité et nous l'avons confronté à des méthodes de l'état de l'art. Il en est ressortis que notre package était qualitativement meilleur que les méthodes existantes. |
This thesis is focused on two intrinsically connected subjects: computation of the normalization constant of a Markov random field and estimation of the binding affinity between two proteins.
We developed several algorithms which tackled counting #P-complete problems based on the idea to obtain an approximation of partition function with deterministic guarantee. These algorithms are strengthened by methods stemming from graphical models as local consistencies, HBFS, variable elimination or tree decomposition. In particular, the main algorithm of this thesis, named Z*, based on the pruning of negligible subtree, proved to be more efficient than some state of the art's methods on instances from protein-protein interactions. Furthermore, the two other algorithms proved to be a breakthrough for the #P-complete counting problem.
A concrete and direct application of the computation of the partition function is the binding affinity estimation of two proteic systems. By means of Z* along with a Rosetta energy function, we developed a package allowing to estimate the binding constant on a large library of mutants for a protein-protein interaction. We statistically analyzed our estimation on a experimental database of binding affinities and we confronted it with methods of the state of the art. It stood out from it that the package was qualitatively better than the existing methods. |