inria-00171780, version 2
A Novel Algorithm for Finding Maximum Common Ordered Subgraph
Nicola Yanev
1, 2Rumen Andonov a, 1
N° RR-6287 (2007)
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.
- a – Université Rennes I
- 1: SYMBIOSE (INRIA - IRISA)
- CNRS : UMR6074 – INRIA – INSA Rennes – Université de Rennes 1
- 2: Department Probability, Operations Research and Statistics
- Sofia University
- Domain : Computer Science/Bioinformatics
Life Sciences/Quantitative MethodsComputer Science/Distributed, Parallel, and Cluster ComputingComputer Science/Operations Research - Keywords : Combinatorial optimization – graph algorithms – proteins structures comparison
- Internal note : RR-6287
- Available versions : v1 (2007-09-13) v2 (2007-09-14)
- inria-00171780, version 2
- http://hal.inria.fr/inria-00171780
- oai:hal.inria.fr:inria-00171780
- From: Rapport De Recherche Inria
- Submitted on: Friday, 14 September 2007 10:37:27
- Updated on: Friday, 14 September 2007 10:46:50
Associated documents
Export