title: A Monte Carlo-based framework enhances the discovery and interpretation of regulatory sequence motifs.
abstract: BACKGROUND
  Discovery of functionally significant short, statistically overrepresented subsequence patterns (motifs) in a set of sequences is a challenging problem in bioinformatics. Oftentimes, not all sequences in the set contain a motif. These non-motif-containing sequences complicate the algorithmic discovery of motifs. Filtering the non-motif-containing sequences from the larger set of sequences while simultaneously determining the identity of the motif is, therefore, desirable and a non-trivial problem in motif discovery research.
  
  
  RESULTS
  We describe MotifCatcher, a framework that extends the sensitivity of existing motif-finding tools by employing random sampling to effectively remove non-motif-containing sequences from the motif search. We developed two implementations of our algorithm; each built around a commonly used motif-finding tool, and applied our algorithm to three diverse chromatin immunoprecipitation (ChIP) data sets. In each case, the motif finder with the MotifCatcher extension demonstrated improved sensitivity over the motif finder alone. Our approach organizes candidate functionally significant discovered motifs into a tree, which allowed us to make additional insights. In all cases, we were able to support our findings with experimental work from the literature.
  
  
  CONCLUSIONS
  Our framework demonstrates that additional processing at the sequence entry level can significantly improve the performance of existing motif-finding tools. For each biological data set tested, we were able to propose novel biological hypotheses supported by experimental work from the literature. Specifically, in Escherichia coli, we suggested binding site motifs for 6 non-traditional LexA protein binding sites; in Saccharomyces cerevisiae, we hypothesize 2 disparate mechanisms for novel binding sites of the Cse4p protein; and in Halobacterium sp. NRC-1, we discoverd subtle differences in a general transcription factor (GTF) binding site motif across several data sets. We suggest that small differences in our discovered motif could confer specificity for one or more homologous GTF proteins. We offer a free implementation of the MotifCatcher software package at http://www.bme.ucdavis.edu/facciotti/resources_data/software/.
authors.affiliation: Department of Biomedical Engineering, One Shields Ave, University of California, Davis, CA 95616, USA.
authors.forename: Phillip
authors.initials: P
authors.lastname: Seitzer
authors.forename: Elizabeth G
authors.initials: EG
authors.lastname: Wilbanks
authors.forename: David J
authors.initials: DJ
authors.lastname: Larsen
authors.forename: Marc T
authors.initials: MT
authors.lastname: Facciotti
mesh_terms: D000465:Algorithms; D020816:Amino Acid Motifs; D001426:Bacterial Proteins / Q000378:metabolism; D047369:Chromatin Immunoprecipitation; D002868:Chromosomal Proteins, Non-Histone / Q000378:metabolism; D019295:Computational Biology / Q000379:methods; D004247:DNA / Q000737:chemistry*; D004268:DNA-Binding Proteins / Q000378:metabolism; D004926:Escherichia coli / Q000378:metabolism; D006217:Halobacterium / Q000378:metabolism; D009010:Monte Carlo Method; D059372:Nucleotide Motifs; D011506:Proteins / Q000737:chemistry*; D012441:Saccharomyces cerevisiae / Q000378:metabolism; D029701:Saccharomyces cerevisiae Proteins / Q000378:metabolism; D012697:Serine Endopeptidases / Q000378:metabolism; D012984:Software; D014157:Transcription Factors / Q000378:metabolism; D000099160:LexA Repressor Protein
chemical_list: D001426:Bacterial Proteins; D002868:Chromosomal Proteins, Non-Histone; D004247:DNA; D004268:DNA-Binding Proteins; D011506:Proteins; D029701:Saccharomyces cerevisiae Proteins; D012697:Serine Endopeptidases; D014157:Transcription Factors; D000099160:LexA Repressor Protein; C092746:CSE4 protein, S cerevisiae