title: Stochastic EM-based TFBS motif discovery with MITSU.
abstract: BACKGROUND
  The Expectation-Maximization (EM) algorithm has been successfully applied to the problem of transcription factor binding site (TFBS) motif discovery and underlies the most widely used motif discovery algorithms. In the wider field of probabilistic modelling, the stochastic EM (sEM) algorithm has been used to overcome some of the limitations of the EM algorithm; however, the application of sEM to motif discovery has not been fully explored.
  
  
  RESULTS
  We present MITSU (Motif discovery by ITerative Sampling and Updating), a novel algorithm for motif discovery, which combines sEM with an improved approximation to the likelihood function, which is unconstrained with regard to the distribution of motif occurrences within the input dataset. The algorithm is evaluated quantitatively on realistic synthetic data and several collections of characterized prokaryotic TFBS motifs and shown to outperform EM and an alternative sEM-based algorithm, particularly in terms of site-level positive predictive value.
  
  
  METHODS
  Java executable available for download at http://www.sourceforge.net/p/mitsu-motif/, supported on Linux/OS X.
authors.affiliation: School of Informatics, University of Edinburgh, Informatics Forum, Edinburgh EH8 9AB, School of Biological Sciences, University of Edinburgh, Edinburgh EH9 3JR and MRC Human Genetics Unit, IGMM, University of Edinburgh, Western General Hospital, Edinburgh EH4 2XU, UK.
authors.forename: Alastair M
authors.initials: AM
authors.lastname: Kilpatrick
authors.affiliation: School of Informatics, University of Edinburgh, Informatics Forum, Edinburgh EH8 9AB, School of Biological Sciences, University of Edinburgh, Edinburgh EH9 3JR and MRC Human Genetics Unit, IGMM, University of Edinburgh, Western General Hospital, Edinburgh EH4 2XU, UK.
authors.forename: Bruce
authors.initials: B
authors.lastname: Ward
authors.affiliation: School of Informatics, University of Edinburgh, Informatics Forum, Edinburgh EH8 9AB, School of Biological Sciences, University of Edinburgh, Edinburgh EH9 3JR and MRC Human Genetics Unit, IGMM, University of Edinburgh, Western General Hospital, Edinburgh EH4 2XU, UK.
authors.forename: Stuart
authors.initials: S
authors.lastname: Aitken
mesh_terms: D000465:Algorithms; D001665:Binding Sites; D004926:Escherichia coli / Q000235:genetics; D006801:Humans; D015233:Models, Statistical; D059372:Nucleotide Motifs; D050436:Regulatory Elements, Transcriptional; D017422:Sequence Analysis, DNA / Q000379:methods*; D013269:Stochastic Processes; D014157:Transcription Factors / Q000378:metabolism*
chemical_list: D014157:Transcription Factors