A Novel Algorithm for Finding Maximum Common Ordered Subgraph

Nicola Yanev 1, 2 Rumen Andonov 1
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 : In this paper, we study the following problem: given are adjacency matrices of two simple graphs. Find two principal matrices (though they are vectors) having the maximum inner product. When used for computing the similarity of two protein structures this problem is called contact map overlap and for the later, we give an exact B&B algorithm with bounds computed by solving Lagrangian relaxation of the problem. The efficiency of the approach is demonstrated on a popular benchmark set of instances together with a comparison with the best existing algorithm.
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00171780
Contributeur : Rapport de Recherche Inria <>
Soumis le : vendredi 14 septembre 2007 - 10:37:27
Dernière modification le : mercredi 16 mai 2018 - 11:23:05
Document(s) archivé(s) le : mardi 21 septembre 2010 - 13:28:33

Fichiers

RR-6287.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00171780, version 2

Citation

Nicola Yanev, Rumen Andonov. A Novel Algorithm for Finding Maximum Common Ordered Subgraph. [Research Report] RR-6287, INRIA. 2007, pp.18. 〈inria-00171780v2〉

Partager

Métriques

Consultations de la notice

371

Téléchargements de fichiers

111