La programmation par contraintes pondérée permet la représentation concise et la résolution de requêtes sur une fonction définie sur un grand nombre de variables discrètes, exprimée comme une combinaison de fonctions simples. Ce cadre correspond à une large palette de problèmes concrets, comme l’annotation d’images, la planification, l’allocation de ressources, etc.
Le design computationnel de protéines vise à prédire automatiquement des séquences d’acides aminés, qui se replient en de nouvelles protéines aux propriétés et fonctionnalités voulues. Ce problème s’exprime comme un problème de satisfaction de contraintes pondéré, dont le but est la minimisation d’une fonction d’énergie binaire sur la séquence pliée sur un squelette rigide donné. Ce modèle n’est qu’une approximation du problème de design réel, qui est insoluble, et la séquence optimale ne répond pas forcément aux besoins des biologistes.
La première contribution de cette thèse est la génération d’un ensemble de solutions, à la fois diverses et de bonne qualité, à la place de la seule conformation d’énergie minimale. La diversité et la qualité des prédictions sont garanties, et la probabilité de trouver une protéine qui fonctionne est améliorée. Pour cela, j’ai développé une fonction de coût qui encode la diversité, ainsi qu’une stratégie gloutonne pour la production d’un ensemble de séquences diverses de basse énergie. L’application à des instances de design montre que la qualité des séquences prédites est renforcée grâce à la diversité.
Par ailleurs, l’hypothèse de rigidité du backbone néglige la flexibilité de la protéine. Le design multi-états prend en compte plusieurs états du squelette, retrouvant ainsi de l’information de flexibilité. L’étape qui suit est la considération d’états désirés et non-désirés, ce qui permet d’améliorer la spécificité d’une protéine, sans perte de stabilité. Ce design négatif est plus complexe que le design positif, qui est déjà NP-complet: il requiert un second niveau d’optimisation. La seconde partie de mes travaux porte sur l’adaptation de la recherche en branch-and-bound et du calcul du minorant, pour l’optimisation bi-niveau. |
Weighted constraint programming concisely represents and answers queries on a function of many discrete variables, expressed as a combination of simple functions. This framework can express a wide range of real-world problems, including image labelling, scheduling, resource allocation, etc.
Computational protein design aims at automatically predicting a new sequence of amino acids that will fold into a protein with desired properties and functionalities. This problem can be expressed as a weighted constraint satisfaction problem that minimizes the sequence pairwise energy function on the target rigid backbone. This model being an approximation of the intractable real design problem, the optimum sequence might not answer the biologist needs.
This thesis first contribution is the generation of a set of diverse, good quality solutions, instead of the single minimum energy conformation. The guaranteed diversity and quality of the predictions improve the likelihood of finding a working protein. To that end, a diversity encoding cost function was developed, along with an iterative greedy strategy for the production of diverse sets of good quality sequences. Application to CPD instances showed that predicted sequence quality is improved thanks to diversity.
Besides, the rigid backbone assumption ignores protein flexibility. Multi-state design considers several backbone states simultaneously, therefore retrieving flexibility information. The next step is the inclusion of both desired and undesired states that enables the enhancement of a protein specificity, while preserving its stability. This negative design is harder than the NP-complete positive design problem. It requires a second optimization level. The second part of this work presents the adaptation of the branch-and-bound search and lower bound computation to bilevel optimization. |