MOTIVATION: Short tandem repeats (STRs) are abundant in protein sequences and play important role in determining their structures and functions. Strikingly, the unusual compositional characteristics of tandem repeats break classical sequence analysis tools. RESULTS: Here, we establish the first algorithm to effectively identify and cluster STRs: Graph-Based Sequence Clustering (GBSC) features linear time complexity, and clusters protein sequence fragments based on their STRs, while allowing for insertions and mutations and supporting the analysis of imperfect or cryptic repeats. Due to its computational efficacy, our algorithm can be used to systematically scan for patterns in large datasets. We compare our method both to state-of-the-art methods for identifying STRs in proteins and alternative clustering approaches. Unlike existing STR analysis methods, GBSC clusters repeat patterns rather than raw sequences, operating at the level of structural repeat identity, while tolerating biological variations and preventing erroneous merging of structurally and functionally distinct motifs. Whereas functional annotation is typically only available at the protein level, the functions of individual STRs and sequences of adjacent STRs remain largely unknown. On a challenging use case we here demonstrate and discuss how our method can be used to associate previously unannotated repetitive protein fragments with similar ones, allowing the transfer of annotation by similarity. For the first time, GBSC offers a tool that systematically extends this fundamental bioinformatics principle to low-complexity regions across large datasets. AVAILABILITY AND IMPLEMENTATION: GBSC is available at GitHub https://github.com/patryk-jarnot/GBSC and https://doi.org/10.5281/zenodo.18965247. The data and scripts to reproduce the analysis are available at https://doi.org/10.5281/zenodo.16906653.

BACKGROUND: Methods for analyzing protein sequence similarity focus mainly on identifying the homologies of proteins with standard amino acid compositions. For motifs with biased compositions, they have already been shown to be suboptimal; thus, we lack dedicated tools to support their analyses. However, motifs with compositional biases also play key roles in protein functions. These domains can be found in transmembrane proteins, bind to RNA through RGG boxes, and may form prions. Nevertheless, many domains remain unknown, as for a long time they were considered nonfunctional and most of the methods mask them to improve homology searches. Therefore, we need better solutions to infer their functions more efficiently. RESULTS: In this research, we developed a new method incorporating three alignment strategies, an algorithm for identifying motifs with similar compositions, 2-mer based filtering, and a new metric for evaluating alignments. These solutions focus mainly on comparing the physicochemical properties of protein sequences rather than their evolutionary relationships. To validate our approach, we compared BLAST with our method in three variants that use local, global-local, and global alignment with the algorithm for identifying compositionally similarities. We used these methods to search for similar transmembrane domains and RGG boxes. We observed that our solutions significantly increased the number of true positives. The greatest increase occurred after we applied our similarity score measure. Compositionally biased motifs frequently consist of two adjacent functionally important motifs; therefore, we also searched for similarities to the K-DE motif of DNA-directed RNA polymerase subunit delta. We found that compared with the other alignment strategies, global-local and global alignment with identifying similar regions included all the submotifs of the query sequence more often. CONCLUSION: Our method introduces novel strategies that enhance the search for compositionally biased motifs, thereby improving annotation retrieval via sequence matching.

Low complexity regions are fragments of protein sequences composed of only a few types of amino acids. These regions frequently occur in proteins and can play an important role in their functions. However, scientists are mainly focused on regions characterized by high diversity of amino acid composition. Similarity between regions of protein sequences frequently reflect functional similarity between them. In this article, we discuss strengths and weaknesses of the similarity analysis of low complexity regions using BLAST, HHblits and CD-HIT. These methods are considered to be the gold standard in protein similarity analysis and were designed for comparison of high complexity regions. However, we lack specialized methods that could be used to compare the similarity of low complexity regions. Therefore, we investigated the existing methods in order to understand how they can be applied to compare such regions. Our results are supported by exploratory study, discussion of amino acid composition and biological roles of selected examples. We show that existing methods need improvements to efficiently search for similar low complexity regions. We suggest features that have to be re-designed specifically for comparing low complexity regions: scoring matrix, multiple sequence alignment, e-value, local alignment and clustering based on a set of representative sequences. Results of this analysis can either be used to improve existing methods or to create new methods for the similarity analysis of low complexity regions.

BACKGROUND: The rapid spread of the COVID-19 demands immediate response from the scientific communities. Appropriate countermeasures mean thoughtful and educated choice of viral targets (epitopes). There are several articles that discuss such choices in the SARS-CoV-2 proteome, other focus on phylogenetic traits and history of the Coronaviridae genome/proteome. However none consider viral protein low complexity regions (LCRs). Recently we created the first methods that are able to compare such fragments. RESULTS: We show that five low complexity regions (LCRs) in three proteins (nsp3, S and N) encoded by the SARS-CoV-2 genome are highly similar to regions from human proteome. As many as 21 predicted T-cell epitopes and 27 predicted B-cell epitopes overlap with the five SARS-CoV-2 LCRs similar to human proteins. Interestingly, replication proteins encoded in the central part of viral RNA are devoid of LCRs. CONCLUSIONS: Similarity of SARS-CoV-2 LCRs to human proteins may have implications on the ability of the virus to counteract immune defenses. The vaccine targeted LCRs may potentially be ineffective or alternatively lead to autoimmune diseases development. These findings are crucial to the process of selection of new epitopes for drugs or vaccines which should omit such regions.