Lagrangian approaches for a class of matching problems in computational biology

Nicola Yanev; Rumen Andonov; Philippe Veber; Stefan Balev

doi:10.1016/j.camwa.2006.12.103

Journal articles

Lagrangian approaches for a class of matching problems in computational biology

Nicola Yanev ^{1, 2} Rumen Andonov ³ Philippe Veber ³ Stefan Balev ⁴

1 Department Probability, Operations Research and Statistics

2 Institute of Mathematics and Computer Science

3 SYMBIOSE - Biological systems and models, bioinformatics and sequences

IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique

4 LIH - Laboratoire d'informatique du Havre

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.

Keywords : Lagrangian relaxation Sequence-structure alignment complexity integer programming

Document type :

Journal articles

Complete list of metadata

https://hal.inria.fr/inria-00335126
Contributor : Rumen Andonov <>
Submitted on : Tuesday, October 28, 2008 - 3:16:59 PM
Last modification on : Tuesday, June 15, 2021 - 4:28:09 PM

Lagrangian approaches for a class of matching problems in computational biology

Links full text

Identifiers

Collections

Citation

Export

Metrics

433

Contact Legal Notice Personal Data

Lagrangian approaches for a class of matching problems in computational biology

Links full text

Identifiers

Collections

Citation

Export

Share

Metrics

433

Contact Legal Notice Personal Data