{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T12:45:02Z","timestamp":1779281102225,"version":"3.51.4"},"reference-count":16,"publisher":"Oxford University Press (OUP)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,4,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: 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.<\/jats:p><jats:p>Results: We present an implementation of this algorithm, named SPACER (Separated Pattern-based Algorithm for cis-Element Recognition) and demonstrate its effectiveness in identifying \u2018gapped\u2019 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 \u2018gapped\u2019 motifs.<\/jats:p><jats:p>Availability: A Java 1.4 implementation is freely available on the Web at http:\/\/genie.Dartmouth.edu\/SPACER\/<\/jats:p><jats:p>Contact: \u00a0robert.h.gross@dartmouth.edu<\/jats:p><jats:p>Supplementary information: Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btm041","type":"journal-article","created":{"date-parts":[[2007,4,30]],"date-time":"2007-04-30T12:32:51Z","timestamp":1177936371000},"page":"1029-1031","source":"Crossref","is-referenced-by-count":17,"title":["SPACER: identification of<i>cis<\/i>-regulatory elements with non-contiguous critical residues"],"prefix":"10.1093","volume":"23","author":[{"given":"Arijit","family":"Chakravarty","sequence":"first","affiliation":[{"name":"1 Department of Cancer Pharmacology, Millennium Pharmaceuticals Inc., Cambridge, MA, 2Department of Computer Science and Engineering, University of Washington, Seattle, WA and 3Department of Biology, Dartmouth College, Hanover, NH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan M.","family":"Carlson","sequence":"additional","affiliation":[{"name":"1 Department of Cancer Pharmacology, Millennium Pharmaceuticals Inc., Cambridge, MA, 2Department of Computer Science and Engineering, University of Washington, Seattle, WA and 3Department of Biology, Dartmouth College, Hanover, NH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Radhika S.","family":"Khetani","sequence":"additional","affiliation":[{"name":"1 Department of Cancer Pharmacology, Millennium Pharmaceuticals Inc., Cambridge, MA, 2Department of Computer Science and Engineering, University of Washington, Seattle, WA and 3Department of Biology, Dartmouth College, Hanover, NH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charles E.","family":"DeZiel","sequence":"additional","affiliation":[{"name":"1 Department of Cancer Pharmacology, Millennium Pharmaceuticals Inc., Cambridge, MA, 2Department of Computer Science and Engineering, University of Washington, Seattle, WA and 3Department of Biology, Dartmouth College, Hanover, NH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert H.","family":"Gross","sequence":"additional","affiliation":[{"name":"1 Department of Cancer Pharmacology, Millennium Pharmaceuticals Inc., Cambridge, MA, 2Department of Computer Science and Engineering, University of Washington, Seattle, WA and 3Department of Biology, Dartmouth College, Hanover, NH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2007,4,15]]},"reference":[{"key":"2023041107545412900_","doi-asserted-by":"crossref","first-page":"4979","DOI":"10.1093\/nar\/gkh825","article-title":"Bipartite pattern discovery by entropy minimization-based multiple local alignments","volume":"32","author":"Bi","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023041107545412900_","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1186\/gb-2003-5-1-201","article-title":"Computational prediction of transcription-factor binding site locations","volume":"5","author":"Bulyk","year":"2003","journal-title":"Genome Biol."},{"key":"2023041107545412900_","doi-asserted-by":"crossref","first-page":"686","DOI":"10.1089\/cmb.2006.13.686","article-title":"BEAM: A beam search algorithm for the identification of cis-regulatory elements in groups of genes","volume":"13","author":"Carlson","year":"2006","journal-title":"J. Comput. Biol."},{"key":"2023041107545412900_","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1186\/1471-2105-7-254","article-title":"Bounded search for de novo identification of degenerate cis-regulatory elements","volume":"7","author":"Carlson","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023041107545412900_","doi-asserted-by":"crossref","first-page":"S354","DOI":"10.1093\/bioinformatics\/18.suppl_1.S354","article-title":"Finding composite regulatory patterns in DNA sequences","volume":"18","author":"Eskin","year":"2002","journal-title":"Bioinformatics"},{"key":"2023041107545412900_","doi-asserted-by":"crossref","first-page":"2240","DOI":"10.1093\/bioinformatics\/bti336","article-title":"A Gibbs sampler for identification of symmetrically structured, spaced DNA motifs with improved estimation of the signal length","volume":"21","author":"Favorov","year":"2005","journal-title":"Bioinformatics"},{"key":"2023041107545412900_","doi-asserted-by":"crossref","first-page":"901","DOI":"10.1093\/molbev\/msg096","article-title":"The effects of selection against spurious transcription factor binding sites","volume":"20","author":"Hahn","year":"2003","journal-title":"Mol. Biol. Evol."},{"key":"2023041107545412900_","first-page":"127","article-title":"BioProspector: discovering conserved DNA motifs in upstream regulatory regions of co-expressed genes","volume":"6","author":"Liu","year":"2001","journal-title":"Pac. Symp. Biocomput."},{"key":"2023041107545412900_","doi-asserted-by":"crossref","first-page":"e36","DOI":"10.1371\/journal.pcbi.0020036","article-title":"Practical strategies for discovering regulatory DNA sequence motifs","volume":"2","author":"MacIsaac","year":"2006","journal-title":"PLoS Comput. Biol."},{"key":"2023041107545412900_","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1186\/1471-2148-3-19","article-title":"Position specific variation in the rate of evolution in transcription factor binding sites","volume":"3","author":"Moses","year":"2003","journal-title":"BMC Evol. Biol."},{"key":"2023041107545412900_","doi-asserted-by":"crossref","first-page":"3145","DOI":"10.1073\/pnas.86.9.3145","article-title":"Structure and function of the Zn(II) binding site within the DNA-binding domain of the GAL4 transcription factor","volume":"86","author":"Pan","year":"1989","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023041107545412900_","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1006\/jmbi.1998.2160","article-title":"A comprehensive library of DNA-binding site matrices for 55 proteins applied to the complete Escherichia coli K-12 genome","volume":"284","author":"Robison","year":"1998","journal-title":"J. Mol. Biol."},{"key":"2023041107545412900_","first-page":"94","volume-title":"Artificial Intelligence: A Modern Approach.","author":"Russell","year":"1995"},{"key":"2023041107545412900_","doi-asserted-by":"crossref","first-page":"5549","DOI":"10.1093\/nar\/gkf669","article-title":"Discovery of novel transcription factor binding sites by statistical overrepresentation","volume":"30","author":"Sinha","year":"2002","journal-title":"Nucleic Acids Res."},{"key":"2023041107545412900_","doi-asserted-by":"crossref","first-page":"1808","DOI":"10.1093\/nar\/28.8.1808","article-title":"Discovering regulatory elements in non-coding sequences by analysis of spaced dyads","volume":"28","author":"van Helden","year":"2000","journal-title":"Nucleic Acids Res."},{"key":"2023041107545412900_","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1038\/nrg1315","article-title":"Applied bioinformatics for the identification of regulatory elements","volume":"5","author":"Wasserman","year":"2004","journal-title":"Nat. Rev. Genet."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/8\/1029\/49822217\/bioinformatics_23_8_1029.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/8\/1029\/49822217\/bioinformatics_23_8_1029.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T17:01:09Z","timestamp":1683824469000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/8\/1029\/198138"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,4,15]]},"references-count":16,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2007,4,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btm041","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2007,4,15]]},"published":{"date-parts":[[2007,4,15]]}}}