Fast construction of assembly trees for molecular graphs

Area of Science:

• Computational Chemistry
• Molecular Modeling
• Graph Theory

Background:

• Hierarchical representations are crucial for internal coordinate modeling and simulation algorithms.
• Generating these hierarchical structures for complex molecular topologies can be challenging.
• Existing methods may struggle with the automatic decomposition of intricate molecular systems.

Purpose of the Study:

• To present a fast and general algorithm for constructing hierarchical representations of molecular systems.
• To address the difficulties in automatically generating hierarchical decompositions for complex molecular topologies.
• To enable efficient modeling and simulation of molecular systems.

Main Methods:

• The algorithm treats molecular systems as graphs, with atoms/pseudo-atoms as vertices and covalent bonds as edges.
• It employs a two-step process: contracting cycles in the graph and building an assembly tree from the reduced graph.
• Complexity analysis shows linear time complexity with respect to the number of edges for the first step.

Main Results:

• The algorithm successfully generates complete hierarchical representations for molecular systems.
• Experimental results on challenging cases and Protein Data Bank subsets demonstrate linear time behavior.
• Both steps of the algorithm exhibit linear performance concerning the input graph's edges.

Conclusions:

• The developed algorithm provides an efficient and general solution for constructing molecular hierarchies.
• It has practical applications, including adaptive torsion-angle molecular mechanics.
• The linear time complexity makes it suitable for large-scale molecular modeling and simulation.