An Efficient Lagrangian Relaxation for the Contact Map Overlap Problem

Rumen Andonov 1, * Nicola Yanev 1, 2 Noël Malod-Dognin 1
* Auteur correspondant
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 : Among the measures for quantifying the similarity between protein 3-D structures, contact map overlap (CMO) maximization deserved sustained attention during past decade. Despite this large involvement, the known algorithms possess a modest performance and are not applicable for large scale comparison. This paper offers a clear advance in this respect. We present a new integer programming model for CMO and propose an exact B&B algorithm with bounds obtained by a novel Lagrangian relaxation. The efficiency of the approach is demonstrated on a popular small benchmark (Skolnick set, 40 domains). On this set our algorithm significantly outperforms the best existing exact algorithms. Many hard CMO instances have been solved for the first time. To assess furthermore our approach, we constructed a large scale set of 300 protein domains. Computing the similarity measure for any of the 44850 couples, we obtained a classification in excellent agreement with SCOP.
Type de document :
Communication dans un congrès
WABI 2008 (8th Workshop on Algorithms in Bioinformatics), Sep 2008, Karlsruhe, Germany. Springer-Verlag, 5251, pp.162-173, 2008, Lecture Notes in Bioinformatics. 〈10.1007/978-3-540-87361-7_14〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00327135
Contributeur : Noel Malod-Dognin <>
Soumis le : mardi 7 octobre 2008 - 14:37:54
Dernière modification le : mercredi 16 mai 2018 - 11:23:05
Document(s) archivé(s) le : vendredi 4 juin 2010 - 12:18:26

Fichier

wabi_08.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Rumen Andonov, Nicola Yanev, Noël Malod-Dognin. An Efficient Lagrangian Relaxation for the Contact Map Overlap Problem. WABI 2008 (8th Workshop on Algorithms in Bioinformatics), Sep 2008, Karlsruhe, Germany. Springer-Verlag, 5251, pp.162-173, 2008, Lecture Notes in Bioinformatics. 〈10.1007/978-3-540-87361-7_14〉. 〈inria-00327135〉

Partager

Métriques

Consultations de la notice

289

Téléchargements de fichiers

402