González-Alemán Roy, Platero-Rochart Daniel, Rodríguez-Serradet Alejandro, Hernández-Rodríguez Erix W, Caballero Julio, Leclerc Fabrice, Montero-Cabrera Luis
Laboratorio de Química Computacional y Teórica (LQCT), Facultad de Química, Universidad de La Habana, La Habana 10400, Cuba.
Institute for Integrative Biology of the Cell (I2BC), CEA, CNRS, Université Paris Saclay, Gif-sur-Yvette F-91198, France.
Bioinformatics. 2022 Nov 30;38(23):5191-5198. doi: 10.1093/bioinformatics/btac666.
The term clustering designates a comprehensive family of unsupervised learning methods allowing to group similar elements into sets called clusters. Geometrical clustering of molecular dynamics (MD) trajectories is a well-established analysis to gain insights into the conformational behavior of simulated systems. However, popular variants collapse when processing relatively long trajectories because of their quadratic memory or time complexity. From the arsenal of clustering algorithms, HDBSCAN stands out as a hierarchical density-based alternative that provides robust differentiation of intimately related elements from noise data. Although a very efficient implementation of this algorithm is available for programming-skilled users (HDBSCAN*), it cannot treat long trajectories under the de facto molecular similarity metric RMSD.
Here, we propose MDSCAN, an HDBSCAN-inspired software specifically conceived for non-programmers users to perform memory-efficient RMSD-based clustering of long MD trajectories. Methodological improvements over the original version include the encoding of trajectories as a particular class of vantage-point tree (decreasing time complexity), and a dual-heap approach to construct a quasi-minimum spanning tree (reducing memory complexity). MDSCAN was able to process a trajectory of 1 million frames using the RMSD metric in about 21 h with <8 GB of RAM, a task that would have taken a similar time but more than 32 TB of RAM with the accelerated HDBSCAN* implementation generally used.
The source code and documentation of MDSCAN are free and publicly available on GitHub (https://github.com/LQCT/MDScan.git) and as a PyPI package (https://pypi.org/project/mdscan/).
Supplementary data are available at Bioinformatics online.
聚类一词指的是一类全面的无监督学习方法，可将相似元素分组为称为簇的集合。分子动力学（MD）轨迹的几何聚类是一种成熟的分析方法，用于深入了解模拟系统的构象行为。然而，由于其二次内存或时间复杂度，流行的变体在处理相对较长的轨迹时会崩溃。在聚类算法库中，HDBSCAN作为一种基于层次密度的替代方法脱颖而出，它能从噪声数据中稳健地区分密切相关的元素。虽然该算法有一个非常高效的实现版本可供有编程技能的用户使用（HDBSCAN*），但在实际的分子相似性度量RMSD下，它无法处理长轨迹。
在此，我们提出了MDSCAN，这是一款受HDBSCAN启发的软件，专为非程序员用户设计，用于对长MD轨迹进行基于RMSD的内存高效聚类。相对于原始版本的方法改进包括将轨迹编码为一种特殊的antage-point树（降低时间复杂度），以及采用双堆方法构建准最小生成树（降低内存复杂度）。MDSCAN能够在大约21小时内使用RMSD度量处理100万帧的轨迹，所需内存小于8GB，而使用通常的加速HDBSCAN*实现执行相同任务则需要类似的时间，但所需内存超过32TB。
MDSCAN的源代码和文档可在GitHub（https://github.com/LQCT/MDScan.git）上免费公开获取，也可作为PyPI包（https://pypi.org/project/mdscan/）获取。
补充数据可在《生物信息学》在线版获取。
