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.
Type de document :
Communication dans un congrès
AlCoB 2017: 4th International Conference on Algorithms for Computational Biology, Jun 2017, Aveiro, Portugal. 37, pp.828 - 74, 2017, 〈10.1021/ci9601675〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01555996
Contributeur : Marie-France Sagot <>
Soumis le : mardi 4 juillet 2017 - 15:47:50
Dernière modification le : mercredi 11 avril 2018 - 01:51:42
Document(s) archivé(s) le : vendredi 15 décembre 2017 - 02:35:52

Fichier

A Fast Algorithm for Large Com...
Fichiers produits par l'(les) auteur(s)

Identifiants

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. 37, pp.828 - 74, 2017, 〈10.1021/ci9601675〉. 〈hal-01555996〉

Partager

Métriques

Consultations de la notice

125

Téléchargements de fichiers

64