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 metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-01555996
Contributor : Marie-France Sagot <>
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

File

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

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

269

Files downloads

292