Using affinity propagation combined post-processing to cluster protein sequences.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Protein databases are rapidly expanding, necessitating efficient sequence clustering methods.
• Existing clustering algorithms, like Affinity Propagation (AP), have limitations with random datasets.
• Accurate protein clustering is crucial for understanding protein function and evolution.

Purpose of the Study:

• To address the limitations of the Affinity Propagation (AP) algorithm in protein sequence clustering.
• To propose and evaluate a novel post-processing method to enhance AP's performance.
• To improve the accuracy and efficiency of clustering large protein sequence datasets.

Main Methods:

• Analyzed limitations of the standard Affinity Propagation (AP) algorithm.
• Developed a post-processing technique using the median similarity for preference value.
• Implemented a combined mergence and reassignment strategy for AP results.
• Validated the enhanced AP method on COG, SCOP, and G-protein family datasets.

Main Results:

• The proposed method approximates the correct number of protein clusters.
• Clustering quality, measured by F-measure, showed significant improvements over existing methods.
• Achieved average improvements of 9% over BlastClust, 33% over TribeMCL, 34% over CLUSS, 59% over Spectral clustering, and 41% over standard AP.
• Demonstrated superior performance compared to five other clustering approaches.

Conclusions:

• The enhanced Affinity Propagation (AP) algorithm provides a more accurate and efficient solution for protein sequence clustering.
• The post-processing method effectively overcomes AP's limitations, leading to better cluster identification.
• This approach is valuable for analyzing the growing volume of protein sequence data in bioinformatics.