Complet+: a computationally scalable method to improve completeness of large-scale protein sequence clustering

Area of Science:

• Bioinformatics
• Computational Biology
• Data Mining

Background:

• Clustering algorithms face a trade-off between homogeneity and completeness.
• Existing methods often result in low completeness, failing to group remote homologs.
• This leads to clusters with high homogeneity but incomplete representation of related sequences.

Purpose of the Study:

• To introduce Complet+, a scalable post-processing method to improve clustering completeness.
• To enhance the grouping of related protein sequences without significantly compromising homogeneity.
• To create more biologically meaningful clusters from existing clustering outputs.

Main Methods:

• Complet+ is a computationally scalable post-processing technique.
• It merges closely-related clusters identified by other algorithms.
• The method leverages verified structural relationships from classification schemes like SCOPe.

Main Results:

• Complet+ significantly increases cluster completeness with minimal impact on homogeneity.
• Application to MMseqs2's clusterupdate improved V-measure by 0.09 (superfamily) and 0.05 (family) at SCOPe.
• Substantial increases in Adjusted Mutual Information (AMI) and Adjusted Rand Index (ARI) demonstrate improved biological representativeness.
• Complet+ shows linear runtime scalability on large datasets (over 3 million sequences).

Conclusions:

• Complet+ effectively addresses the homogeneity-completeness trade-off in sequence clustering.
• The method enhances the biological accuracy of clusters and is compatible with various clustering tools.
• Complet+ offers a scalable solution for improving protein sequence clustering results.