A novel Euclidean quality threshold ARTMAP network and its application to pattern classification

BitQT: a graph-based approach to the quality threshold clustering of molecular dynamics

MOTIVATION

Classical Molecular Dynamics (MD) is a standard computational approach to model time-dependent processes at the atomic level. The inherent sparsity of increasingly huge generated trajectories demands clustering algorithms to reduce other post-simulation analysis complexity. The Quality Threshold (QT) variant is an appealing one from the vast number of available clustering methods. It guarantees that all members of a particular cluster will maintain a collective similarity established by a user-defined threshold. Unfortunately, its high computational cost for processing big data limits its application in the molecular simulation field.

RESULTS

In this work, we propose a methodological parallel between QT clustering and another well-known algorithm in the field of Graph Theory, the Maximum Clique Problem. Molecular trajectories are represented as graphs whose nodes designate conformations, while unweighted edges indicate mutual similarity between nodes. The use of a binary-encoded RMSD matrix coupled to the exploitation of bitwise operations to extract clusters significantly contributes to reaching a very affordable algorithm compared to the few implementations of QT for MD available in the literature. Our alternative provides results in good agreement with the exact one while strictly preserving the collective similarity of clusters.

AVAILABILITY AND IMPLEMENTATION

The source code and documentation of BitQT are free and publicly available on GitHub (https://github.com/LQCT/BitQT.git) and ReadTheDocs (https://bitqt.readthedocs.io/en/latest/), respectively.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Quality Threshold Clustering of Molecular Dynamics: A Word of Caution

Clustering Molecular Dynamics trajectories is a common analysis that allows grouping together similar conformations. Several algorithms have been designed and optimized to perform this routine task, and among them, Quality Threshold stands as a very attractive option. This algorithm guarantees that in retrieved clusters no pair of frames will have a similarity value greater than a specified threshold, and hence, a set of strongly correlated frames are obtained for each cluster. In this work, it is shown that various commonly used software implementations are flawed by confusing Quality Threshold with another simplistic well-known clustering algorithm published by Daura et al. (Daura, X.; van Gunsteren, W. F.; Jaun, B.; Mark, A. E.; Gademann, K.; Seebach, D. Peptide Folding: When Simulation Meets Experiment. Angew. Chemie Int. Ed. 1999, 38 (1/2), 236-240). Daura's algorithm does not impose any quality threshold for the frames contained in retrieved clusters, bringing unrelated structural configurations altogether. The advantages of using Quality Threshold whenever possible to explore Molecular Dynamic trajectories is exemplified. An in-house implementation of the original Quality Threshold algorithm has been developed in order to illustrate our comments, and its code is freely available for further use by the scientific community.