Yanev, Nicola
- Andonov, Rumen
Rapport de recherche de l'INRIA -
Rennes ,
Equipe :
SYMBIOSE 15 pages - Octobre 2002 - Document en anglais
Titre français : Le problème de reconnaissance de repliement de protéines est-t-il dans P?
Abstract : This work is about a problem from computational biology known as protein threading problem. By finding out an appropriate linear mixed-integer programming (MIP) formulation we demonstrate that the real-live instances of this problem could be efficiently solved by using only some linear-programming (LP) solver instead of special-purpose branch&bound algorithm. This is due to the fact that within the frame of MIP model proposed, all biological instances, we were able to test, attain their optima at feasible vertices of the underlying LP polytope which is the essence of the statement in the title.
Résumé : Cet article concerne le problème de reconnaissance de repliement de protéines connu sous le nom de «protein threading problem». Nous proposons plusieurs formulations MIP (Mixed-Integer Programming) du problème et nous montrons que toutes les instances basées sur des données «réelles» (utilisées par les biologistes) peuvent être résolues par un logiciel LP (Linear Programming) au lieu d'un algorithme b&b (branch&bound) dédié. Dans le cadre de notre dernier modèle MIP, l'optimum de tous les cas que nous avons résolus, est atteint dans un sommet (0,1) du polytope sous-jacent, ce qui explique le titre de cet article.
Key-Words : PROTEIN THREADING PROBLEM / MIXED-INTEGER PROGRAMMING
Mots-clés : PROTEIN THREADING PROBLEM / MIXED-INTEGER PROGRAMMING
