Skip to Main content Skip to Navigation
New interface
Reports (Research report)

The Protein Threading Problem is in P?

Nicola Yanev 1 Rumen Andonov 2 
2 SYMBIOSE - Biological systems and models, bioinformatics and sequences
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
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.
Document type :
Reports (Research report)
Complete list of metadata
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 7:33:43 PM
Last modification on : Thursday, October 27, 2022 - 3:44:58 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:48:47 PM


  • HAL Id : inria-00072011, version 1


Nicola Yanev, Rumen Andonov. The Protein Threading Problem is in P?. [Research Report] RR-4577, INRIA. 2002. ⟨inria-00072011⟩



Record views


Files downloads