Lagrangian Approaches for a class of Matching Problems in Computational Biology

Nicola Yanev 1 Rumen Andonov 1 Philippe Veber 1 Stefan Balev 2
1 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 paper presents efficient algorithms for solving the problem of aligning a protein structure template to a query amino-acid sequence, known as protein threading problem. We consider the problem as a special case of graph matching problem. We give formal graph and integer programming models of the problem. After studying the properties of these models, we propose two kinds of Lagrangian relaxation for solving them. We present experimental results on real life instances showing the efficiency of our approaches.
Complete list of metadatas

Cited literature [2 references]  Display  Hide  Download

https://hal.inria.fr/inria-00090635
Contributor : Rapport de Recherche Inria <>
Submitted on : Thursday, September 7, 2006 - 3:00:35 PM
Last modification on : Monday, October 28, 2019 - 2:48:06 PM
Long-term archiving on : Monday, September 20, 2010 - 4:17:31 PM

Identifiers

Citation

Nicola Yanev, Rumen Andonov, Philippe Veber, Stefan Balev. Lagrangian Approaches for a class of Matching Problems in Computational Biology. [Research Report] RR-5973, INRIA. 2006. ⟨inria-00090635v2⟩

Share

Metrics

Record views

328

Files downloads

341