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 : Cet article propose des algorithmes efficaces pour déterminer l'alignement optimal entre une structure et une séquence protéique, problème connu sous le nom de protein threading. Nous posons ce problème comme un cas particulier d'appariement. Nous présentons un modèle formel du problème sous la forme d'une famille de graphes, et des programmes en nombre entiers correspondants. Nous étudions dans un premier temps les propriétés de ces modèles, pour ensuite proposer deux approches de relaxation lagrangienne pour la résolution. Enfin, nous montrons, à l'aide de données expérimentales sur des instances réelles, l'efficacité de ces approches. \\ 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.
Type de document :
Rapport
[Research Report] PI 1814, 2006, pp.18
Liste complète des métadonnées

https://hal.inria.fr/inria-00091944
Contributeur : Anne Jaigu <>
Soumis le : jeudi 7 septembre 2006 - 16:22:04
Dernière modification le : mardi 5 juin 2018 - 10:14:24
Document(s) archivé(s) le : lundi 5 avril 2010 - 23:34:52

Fichiers

Identifiants

  • HAL Id : inria-00091944, version 1

Citation

Nicola Yanev, Rumen Andonov, Philippe Veber, Stefan Balev. Lagrangian Approaches for a class of Matching Problems in Computational Biology. [Research Report] PI 1814, 2006, pp.18. 〈inria-00091944〉

Partager

Métriques

Consultations de la notice

209

Téléchargements de fichiers

152