Lagrangian approaches for a class of matching problems in computational biology

Nicola Yanev 1, 2 Rumen Andonov 3 Philippe Veber 3 Stefan Balev 4
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
Type de document :
Article dans une revue
Computers and Mathematics with Applications, Elsevier, 2008, 55 (Issue 5 (March 2008)), pp.1054-1067. 〈10.1016/j.camwa.2006.12.103〉
Liste complète des métadonnées
https://hal.inria.fr/inria-00335126
Contributeur : Rumen Andonov <>
Soumis le : mardi 28 octobre 2008 - 15:16:59
Dernière modification le : mardi 5 juin 2018 - 10:14:24

Lien texte intégral

openaccess

Identifiants

Collections

INRIA | IRISA | IRISA-D7 | COMUE-NORMANDIE | UR1-UFR-ISTIC | UNIV-RENNES

Citation

Nicola Yanev, Rumen Andonov, Philippe Veber, Stefan Balev. Lagrangian approaches for a class of matching problems in computational biology. Computers and Mathematics with Applications, Elsevier, 2008, 55 (Issue 5 (March 2008)), pp.1054-1067. 〈10.1016/j.camwa.2006.12.103〉. 〈inria-00335126〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

247

Contact


archive-ouverte@inria.fr