Fast construction of assembly trees for molecular graphs

Svetlana Artemova 1, * Sergei Grudinin 1 Stephane Redon 1
* Auteur correspondant
1 NANO-D - Algorithms for Modeling and Simulation of Nanosystems
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
Abstract : A number of modeling and simulation algorithms using internal coordinates rely on hierarchical representations of molecular systems. Given the potentially complex topologies of molecular systems, though, automatically generating such hierarchical decompositions may be difficult. In this article, we present a fast general algorithm for the complete construction of a hierarchical representation of a molecular system. This two-step algorithm treats the input molecular system as a graph in which vertices represent atoms or pseudo-atoms, and edges represent covalent bonds. The first step contracts all cycles in the input graph. The second step builds an assembly tree from the reduced graph. We analyze the complexity of this algorithm and show that the first step is linear in the number of edges in the input graph, whereas the second one is linear in the number of edges in the graph without cycles, but dependent on the branching factor of the molecular graph. We demonstrate the performance of our algorithm on a set of specifically tailored difficult cases as well as on a large subset of molecular graphs extracted from the protein data bank. In particular, we experimentally show that both steps behave linearly in the number of edges in the input graph (the branching factor is fixed for the second step). Finally, we demonstrate an application of our hierarchy construction algorithm to adaptive torsion-angle molecular mechanics.
Type de document :
Article dans une revue
Journal of Computational Chemistry, Wiley, 2011, 32 (8), pp.1589-1598. 〈10.1002/jcc.21738〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00746836
Contributeur : Nano-D Equipe <>
Soumis le : lundi 29 octobre 2012 - 18:04:36
Dernière modification le : mercredi 14 décembre 2016 - 01:07:16

Identifiants

Citation

Svetlana Artemova, Sergei Grudinin, Stephane Redon. Fast construction of assembly trees for molecular graphs. Journal of Computational Chemistry, Wiley, 2011, 32 (8), pp.1589-1598. 〈10.1002/jcc.21738〉. 〈hal-00746836〉

Partager

Métriques

Consultations de la notice

261