Discovering sequence motifs with arbitrary insertions and deletions

Abstract

BIOLOGY IS ENCODED IN MOLECULAR SEQUENCES: deciphering this encoding remains a grand scientific challenge. Functional regions of DNA, RNA, and protein sequences often exhibit characteristic but subtle motifs; thus, computational discovery of motifs in sequences is a fundamental and much-studied problem. However, most current algorithms do not allow for insertions or deletions (indels) within motifs, and the few that do have other limitations. We present a method, GLAM2 (Gapped Local Alignment of Motifs), for discovering motifs allowing indels in a fully general manner, and a companion method GLAM2SCAN for searching sequence databases using such motifs. glam2 is a generalization of the gapless Gibbs sampling algorithm. It re-discovers variable-width protein motifs from the PROSITE database significantly more accurately than the alternative methods PRATT and SAM-T2K. Furthermore, it usefully refines protein motifs from the ELM database: in some cases, the refined motifs make orders of magnitude fewer overpredictions than the original ELM regular expressions. GLAM2 performs respectably on the BAliBASE multiple alignment benchmark, and may be superior to leading multiple alignment methods for "motif-like" alignments with N- and C-terminal extensions. Finally, we demonstrate the use of GLAM2 to discover protein kinase substrate motifs and a gapped DNA motif for the LIM-only transcriptional regulatory complex: using GLAM2SCAN, we identify promising targets for the latter. GLAM2 is especially promising for short protein motifs, and it should improve our ability to identify the protein cleavage sites, interaction sites, post-translational modification attachment sites, etc., that underlie much of biology. It may be equally useful for arbitrarily gapped motifs in DNA and RNA, although fewer examples of such motifs are known at present. GLAM2 is public domain software, available for download at http://bioinformatics.org.au/glam2.

Figure 1. A typical motif alignment from glam2.

The stars indicate the key positions. The residues inserted between key positions are not considered aligned to each other: their column placement is arbitrary. The numbers on either side of the aligned segments indicate the coordinates of each segment within the sequence. The decimal numbers on the right are the marginal scores of each aligned segment.

Figure 2. Sensitivity and positive predictive value of glam2 compared to sam-t2k and pratt on 58 PROSITE motifs.

Figure 3. Non-specificity of ELM motif regular expressions.

Each point represents one of the 41 ELM motifs used in this study. The x-value of the point is the number of known sites, and y gives the number of predicted sites in Swiss-Prot sequences.

Figure 4. Sensitivity versus specificity trade-off of glam2 motifs.

(A) shows how often the glam2 motif has better specificity than the corresponding ELM RE as a function of the sensitivity level. (B) shows the specificity (FP_50) of the ELM RE and the glam2 motif for each of the 41 ELM entries studied here. Each point represents one ELM motif, with x and y giving the the FP_50 of the glam2 motif and of the ELM RE, respectively. Triangles are motifs learned from all sites; squares show cross-validated results.

Figure 5. glam2 output on 31 clones that bind the Lmo2 complex.

glam2 was run using default parameters on the clones identified in Figure 1A of . The glam2 alignment is shown on the top, and the information content “LOGO” corresponding to the alignment is shown on the bottom. The glam2 alignment was pretty-printed using PFAAT . The LOGO is corrected for small-sample size .