SLiMFinder: a probabilistic method for identifying over-represented, convergently evolved, short linear motifs in proteins

Abstract

Background: Short linear motifs (SLiMs) in proteins are functional microdomains of fundamental importance in many biological systems. SLiMs typically consist of a 3 to 10 amino acid stretch of the primary protein sequence, of which as few as two sites may be important for activity, making identification of novel SLiMs extremely difficult. In particular, it can be very difficult to distinguish a randomly recurring "motif" from a truly over-represented one. Incorporating ambiguous amino acid positions and/or variable-length wildcard spacers between defined residues further complicates the matter.

Methodology/principal findings: In this paper we present two algorithms. SLiMBuild identifies convergently evolved, short motifs in a dataset of proteins. Motifs are built by combining dimers into longer patterns, retaining only those motifs occurring in a sufficient number of unrelated proteins. Motifs with fixed amino acid positions are identified and then combined to incorporate amino acid ambiguity and variable-length wildcard spacers. The algorithm is computationally efficient compared to alternatives, particularly when datasets include homologous proteins, and provides great flexibility in the nature of motifs returned. The SLiMChance algorithm estimates the probability of returned motifs arising by chance, correcting for the size and composition of the dataset, and assigns a significance value to each motif. These algorithms are implemented in a software package, SLiMFinder. SLiMFinder default settings identify known SLiMs with 100% specificity, and have a low false discovery rate on random test data.

Conclusions/significance: The efficiency of SLiMBuild and low false discovery rate of SLiMChance make SLiMFinder highly suited to high throughput motif discovery and individual high quality analyses alike. Examples of such analyses on real biological data, and how SLiMFinder results can help direct future discoveries, are provided. SLiMFinder is freely available for download under a GNU license from http://bioinformatics.ucd.ie/shields/software/slimfinder/.

Figure 1. Overview of SLiMFinder.

An input dataset is first clustered into unrelated protein clusters (UPC) using a treatment of BLAST results to identify evolutionary relationships. The dataset is also masked according to user choices, masking out predicted ordered regions, selected UniProt features, low complexity regions and/or N-terminal methionines. This (masked) dataset is then processed by the SLiMBuild algorithm to identify motifs that are shared by unrelated proteins. A TEIRESIAS-style output of all motifs can be produced at this point. Amino acid frequencies are calculated for each cluster of unrelated proteins, either before or after masking, and may be retained as cluster-specific frequencies or averaged over all clusters. Alternatively, amino acid frequencies may be given from an external source. These frequencies are combined with data from SLiMBuild on the motif composition of the dataset and processed by the SLiMChance algorithm, which identifies significantly over-represented motifs. These motifs and additional dataset information are then output into results files.

Figure 2. SLiMBuild construction of motifs.

A. Dimer construction. For each position in a sequence, each possible wildcard length x is used to find possible “i-x-j” dimers. Dimers containing masked (“X”) residues are ignored (greyed dimers). Note that the n-terminal “^” marker is treated as any other amino acid. B. Motif extension. Longer SLiMs are constructed during the SLiMBuild process by matching the occurrences of shorter SLiMs with the relevant i-x-j dimers. At each stage, only SLiMs with sufficient unrelated protein support are retained, making the algorithm very efficient.

Figure 3. SLiMBuild Ambiguity.

A. Wildcard ambiguity. Ambiguity is added in a multi-stage process. First, the motif is broken up into its component parts, consisting of alternate defined and wildcard positions. These are then replaced by the appropriate equivalency group, which in the case of wildcards is the full range of wildcard lengths from 0 up to the maximum length allowed. These equivalencies are then expanded to all possible variants. Any variants that do not themselves meet the minimum support requirement used previously for motif extension are not considered (shown in grey). Variants are only combined when the UPC support for the ambiguous motif is greater than for the individual variants. Variants that would not increase the UPC support of the original motif are therefore also removed (shown in red). The remaining variants are ranked (see text) and the best variant combined with the original motif (blue). The remaining variants are re-assessed for increasing UPC support and any failing to do so are again removed. If any remain, the ranking and combining cycle repeats. If not, the finished degenerate motif is returned. B. Amino acid ambiguities. These are handled in the same way as wildcard ambiguities, except that this time equivalencies are defined by the given equivalency list. If a given amino acid belongs to multiple equivalency groups, such as serine ([AGS] and [ST]) then all possible combinations of these equivalency groups (four in this case) are considered separately, thus multiple ambiguous SLiMs can potentially be produced. (Expansion of these combinations has been truncated in the figure.)

Figure 4. SLiMFinder results on random datasets.

A. Cumulative frequency of the most significant motifs returned by SLiMFinder for random datasets. Very little difference is observed between datasets produced using human amino acid frequencies and datasets of actual human protein sequences, implying that there is little or no bias introduced by regional compositional biases within real protein sequences. B. Box plots of most significant results returned by all random datasets for different dataset sizes (UPC). Although there is a slight trend for larger datasets to return smaller p-values, the difference is primarily restricted to the non-significant motifs. Variation between datasets of the same size is considerably greater than variation between different sized datasets.