GBSC: graph-based sequence clustering method for similar short tandem repeats in protein sequences

Area of Science:

• Bioinformatics
• Computational Biology
• Structural Biology

Background:

• Short tandem repeats (STRs) are prevalent in protein sequences, influencing structure and function.
• Classical sequence analysis tools struggle with the unique composition of STRs.

Purpose of the Study:

• To introduce the first algorithm, Graph-Based Sequence Clustering (GBSC), for effective identification and clustering of STRs in protein sequences.
• To enable analysis of imperfect or cryptic repeats and facilitate pattern discovery in large datasets.

Main Methods:

• GBSC utilizes linear time complexity for efficient processing.
• The algorithm clusters protein sequence fragments based on STRs, accommodating insertions and mutations.
• GBSC operates on repeat patterns, not raw sequences, preserving structural repeat identity.

Main Results:

• GBSC demonstrates computational efficacy for large-scale pattern scanning.
• The method outperforms existing STR identification and clustering approaches.
• GBSC successfully clusters previously unannotated repetitive protein fragments, enabling annotation transfer by similarity.

Conclusions:

• GBSC provides a novel tool for systematic analysis of low-complexity regions in proteins.
• The algorithm extends bioinformatics principles to repetitive protein elements.
• GBSC facilitates the understanding of functions for individual STRs and adjacent repeat sequences.