title: EXTREME: an online EM algorithm for motif discovery.
abstract: BACKGROUND
  Identifying regulatory elements is a fundamental problem in the field of gene transcription. Motif discovery-the task of identifying the sequence preference of transcription factor proteins, which bind to these elements-is an important step in this challenge. MEME is a popular motif discovery algorithm. Unfortunately, MEME's running time scales poorly with the size of the dataset. Experiments such as ChIP-Seq and DNase-Seq are providing a rich amount of information on the binding preference of transcription factors. MEME cannot discover motifs in data from these experiments in a practical amount of time without a compromising strategy such as discarding a majority of the sequences.
  
  
  RESULTS
  We present EXTREME, a motif discovery algorithm designed to find DNA-binding motifs in ChIP-Seq and DNase-Seq data. Unlike MEME, which uses the expectation-maximization algorithm for motif discovery, EXTREME uses the online expectation-maximization algorithm to discover motifs. EXTREME can discover motifs in large datasets in a practical amount of time without discarding any sequences. Using EXTREME on ChIP-Seq and DNase-Seq data, we discover many motifs, including some novel and infrequent motifs that can only be discovered by using the entire dataset. Conservation analysis of one of these novel infrequent motifs confirms that it is evolutionarily conserved and possibly functional.
  
  
  METHODS
  All source code is available at the Github repository http://github.com/uci-cbcl/EXTREME.
authors.affiliation: Department of Computer Science, University of California, Irvine, CA 92697, USA and Center for Complex Biological Systems, University of California, Irvine, CA 92697, USADepartment of Computer Science, University of California, Irvine, CA 92697, USA and Center for Complex Biological Systems, University of California, Irvine, CA 92697, USA.
authors.forename: Daniel
authors.initials: D
authors.lastname: Quang
authors.affiliation: Department of Computer Science, University of California, Irvine, CA 92697, USA and Center for Complex Biological Systems, University of California, Irvine, CA 92697, USADepartment of Computer Science, University of California, Irvine, CA 92697, USA and Center for Complex Biological Systems, University of California, Irvine, CA 92697, USA.
authors.forename: Xiaohui
authors.initials: X
authors.lastname: Xie
mesh_terms: D000465:Algorithms; D047369:Chromatin Immunoprecipitation; D059372:Nucleotide Motifs; D050436:Regulatory Elements, Transcriptional; D017422:Sequence Analysis, DNA / Q000379:methods*; D014157:Transcription Factors / Q000378:metabolism*
chemical_list: D014157:Transcription Factors