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
Complete list of metadatas

https://hal.inria.fr/inria-00072011
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 7:33:43 PM
Last modification on : Friday, March 15, 2019 - 5:06:23 PM
Long-term archiving on : Sunday, April 4, 2010 - 10:48:47 PM

Identifiers

  • HAL Id : inria-00072011, version 1

Citation

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

Share

Metrics

Record views

359

Files downloads

208