Fast algorithm for population-based protein structural model analysis.

Area of Science:

• Computational Biology
• Structural Bioinformatics
• Biophysics

Background:

• De novo protein structure prediction generates numerous candidate models.
• Clustering is used to identify near-native models from these candidates.
• Current clustering methods are computationally intensive due to pairwise distance calculations.

Purpose of the Study:

• To develop a fast and accurate method for clustering protein structure models.
• To reduce the computational time required for selecting near-native models.
• To enhance the quality of cluster representatives and enable efficient data visualization.

Main Methods:

• Proposed novel distance measures, Dscore1 and Dscore2, based on protein distance matrix comparisons.
• Developed a Dscore1-based clustering algorithm with linear time complexity.
• Utilized Dscore2 for selecting high-quality cluster representatives.
• Implemented fast data visualization for large model sets.

Main Results:

• Dscore1 and Dscore2 show high correlation with root mean square deviation (RMSD) and TM-score, respectively.
• Dscore1-based clustering achieves linear time complexity, significantly faster than quadratic methods.
• Clustering accuracy for near-native model selection is comparable to existing methods.
• Dscore2 improves representative quality with minimal computational overhead.
• Fast data visualization of Dscore distribution is achieved in seconds to minutes for large datasets.

Conclusions:

• The proposed Dscore-based method offers a computationally efficient and accurate alternative for protein structure model clustering.
• This approach accelerates the identification of near-native protein structures.
• The MUFOLD-CL package provides a practical implementation of this novel clustering technique.