Skip to Main content Skip to Navigation
Conference papers

A Fast Algorithm for Large Common Connected Induced Subgraphs

Abstract : We present a fast algorithm for finding large common sub-graphs, which can be exploited for detecting structural and functional relationships between biological macromolecules. Many fast algorithms exist for finding a single maximum common subgraph. We show with an example that this gives limited information, motivating the less studied problem of finding many large common subgraphs covering different areas. As the latter is also hard, we give heuristics that improve performance by several orders of magnitude. As a case study, we validate our findings experimentally on protein graphs with thousands of atoms.
Document type :
Conference papers
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download
Contributor : Marie-France Sagot Connect in order to contact the contributor
Submitted on : Tuesday, July 4, 2017 - 3:47:50 PM
Last modification on : Tuesday, February 26, 2019 - 10:54:02 AM
Long-term archiving on: : Friday, December 15, 2017 - 2:35:52 AM


A Fast Algorithm for Large Com...
Files produced by the author(s)




Alessio Conte, Roberto Grossi, Andrea Marino, Lorenzo Tattini, Luca Versari. A Fast Algorithm for Large Common Connected Induced Subgraphs. AlCoB 2017: 4th International Conference on Algorithms for Computational Biology, Jun 2017, Aveiro, Portugal. pp.828 - 74, ⟨10.1021/ci9601675⟩. ⟨hal-01555996⟩



Record views


Files downloads