Lagrangian Approaches for a class of Matching Problems in Computational Biology - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Reports (Research Report) Year : 2006

Lagrangian Approaches for a class of Matching Problems in Computational Biology

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.
Fichier principal
Vignette du fichier
RR-5973.pdf (536.85 Ko) Télécharger le fichier
Loading...

Dates and versions

inria-00090635 , version 1 (01-09-2006)
inria-00090635 , version 2 (07-09-2006)

Identifiers

Cite

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⟩
200 View
115 Download

Altmetric

Share

Gmail Facebook X LinkedIn More