Fast construction of assembly trees for molecular graphs

Svetlana Artemova 1, * Sergei Grudinin 1 Stephane Redon 1
* Corresponding author
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.
Document type :
Journal articles
Complete list of metadatas
Contributor : Nano-D Equipe <>
Submitted on : Monday, October 29, 2012 - 6:04:36 PM
Last modification on : Tuesday, May 21, 2019 - 11:48:13 AM

Links full text



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⟩



Record views