SPACER: identification of cis-regulatory elements with non-contiguous critical residues.
BACKGROUND
Many transcription factors bind to sites that are long and loosely related to each other. De novo identification of such motifs is computationally challenging. In this article, we propose a novel semi-greedy algorithm over the space of all IUPAC degenerate strings to identify the most over-represented highly degenerate motifs.


RESULTS
We present an implementation of this algorithm, named SPACER (Separated Pattern-based Algorithm for cis-Element Recognition) and demonstrate its effectiveness in identifying 'gapped' and highly degenerate motifs. We compare SPACER's performance against ten motif finders on 42 experimentally defined regulons from Bacillus subtilis, Escherichia coli and Saccharomyces cerevisiae. These motif finders cover a wide range of both enumerative and statistical approaches, including programs specifically designed for prokaryotic and 'gapped' motifs.


BACKGROUND
A Java 1.4 implementation is freely available on the Web at http://genie.Dartmouth.edu/SPACER/
Chakravarty
Arijit
A
Department of Cancer Pharmacology, Millennium Pharmaceuticals Inc., Cambridge, MA, USA.
Carlson
Jonathan M
JM
Khetani
Radhika S
RS
DeZiel
Charles E
CE
Gross
Robert H
RH
D000465:Algorithms; D020816:Amino Acid Motifs; D001483:Base Sequence; D001665:Binding Sites; D008969:Molecular Sequence Data; D011485:Protein Binding; D050436:Regulatory Elements, Transcriptional / Q000235:genetics*; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software; D014157:Transcription Factors / Q000737:chemistry* / Q000235:genetics*
D014157:Transcription Factors