Discovering sequence motifs with arbitrary insertions and deletions

Frith, Martin C., Saunders, Neil F. W., Kobe, Bostjan and Bailey, Timothy L. (2008) Discovering sequence motifs with arbitrary insertions and deletions. PLoS Computational Biology, 4 5: e1000071.1-e1000071.12. doi:10.1371/journal.pcbi.1000071

Author Frith, Martin C.
Saunders, Neil F. W.
Kobe, Bostjan
Bailey, Timothy L.
Title Discovering sequence motifs with arbitrary insertions and deletions
Journal name PLoS Computational Biology   Check publisher's open access policy
ISSN 1553-734X
Publication date 2008-05
Sub-type Article (original research)
DOI 10.1371/journal.pcbi.1000071
Open Access Status DOI
Volume 4
Issue 5
Start page e1000071.1
End page e1000071.12
Total pages 12
Editor P. E. Bourne
Place of publication San Francisco, CA, USA
Publisher Public Library of Science
Collection year 2009
Language eng
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
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ
Additional Notes Article # e1000071

Document type: Journal Article
Sub-type: Article (original research)
Collections: 2009 Higher Education Research Data Collection
School of Chemistry and Molecular Biosciences
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 101 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 116 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Fri, 06 Mar 2009, 16:27:00 EST by Jennifer Falknau on behalf of School of Chemistry & Molecular Biosciences