ProClust: improved clustering of protein sequences with an extended graph-based approach

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Identifying remote protein homologues is challenging due to increasing database sizes and noise.
• Traditional alignment methods struggle with distinguishing true homologues from random similarities.
• Protein families and transitivity of homology offer potential solutions but have limitations, especially with multi-domain proteins.

Purpose of the Study:

• To develop an improved algorithm for detecting remote protein homologues.
• To enhance the accuracy and sensitivity of homology detection in large biological databases.
• To address limitations of existing methods, particularly concerning multi-domain proteins and noise.

Main Methods:

• An extended graph-based clustering algorithm utilizing an asymmetric distance measure.
• Scaling similarity values by sequence length and incorporating alignment score significance for filtering.
• Post-processing with profile hidden Markov models (HMMs) for cluster merging.
• Utilizing transitivity with multiple intermediate sequences.

Main Results:

• The proposed method demonstrates high specificity and favorably compares with PSI-Blast for remote homologue detection.
• The algorithm effectively uses transitivity, with up to twelve intermediate sequences, crucial for performance.
• Analysis of false positives indicates effective bounding of transitivity degree and provides parameter guidance.
• The approach offers substantial improvement over existing methods, despite theoretical limitations with multi-domain proteins.

Conclusions:

• The developed algorithm significantly improves remote protein homology detection.
• The method effectively leverages transitivity and addresses challenges posed by large datasets and noise.
• While not a complete solution for multi-domain proteins, the heuristics provide a substantial advancement in the field.