Community detection for graph-based similarity: Application to protein binding pockets classification

• Published in: Pattern recognition letters 2015-09, Vol.62, p.49-54
• Main Authors: Mallek, Sabrine, Boukhris, Imen, Elouedi, Zied
• Format: Article
• Language: English
• Subjects: Community detection; Graph-based similarity; Maximum almost common subgraph; Protein binding sites classification
• ISSN: 0167-8655; 1872-7344
• DOI: 10.1016/j.patrec.2015.05.003

•We present a novel approach for similarity assessment between graphs.•We formulate a new similarity measure that contributes to the graph matching problem.•Our approach gives the best results in terms of accuracy and computation time. This paper addresses the problem of similarity assessment between node-labeled and edge-weighted graphs representing protein binding pockets. A novel approach is proposed for predicting the functional family of proteins on the basis of the properties of their binding pockets using graphs as models to depict their geometry and physicochemical composition without information loss. State of the art graph similarity measure based on the maximum common subgraph is relaxed by the use of an another concept: the so-called community, or in our context, the maximum densest common community “MDCC”, which is used as an almost common subgraph. The latter is more convenient since it allows to take into account the flexible nature of proteins on the 3D-level. With our approach, tolerance towards noise and structural variation is increased. Furthermore, the MDCC is detected with low computation time. The performance of our method is validated on real world data.