title: Inferring intra-motif dependencies of DNA binding sites from ChIP-seq data.
abstract: BACKGROUND
  Statistical modeling of transcription factor binding sites is one of the classical fields in bioinformatics. The position weight matrix (PWM) model, which assumes statistical independence among all nucleotides in a binding site, used to be the standard model for this task for more than three decades but its simple assumptions are increasingly put into question. Recent high-throughput sequencing methods have provided data sets of sufficient size and quality for studying the benefits of more complex models. However, learning more complex models typically entails the danger of overfitting, and while model classes that dynamically adapt the model complexity to data have been developed, effective model selection is to date only possible for fully observable data, but not, e.g., within de novo motif discovery.
  
  
  RESULTS
  To address this issue, we propose a stochastic algorithm for performing robust model selection in a latent variable setting. This algorithm yields a solution without relying on hyperparameter-tuning via massive cross-validation or other computationally expensive resampling techniques. Using this algorithm for learning inhomogeneous parsimonious Markov models, we study the degree of putative higher-order intra-motif dependencies for transcription factor binding sites inferred via de novo motif discovery from ChIP-seq data. We find that intra-motif dependencies are prevalent and not limited to first-order dependencies among directly adjacent nucleotides, but that second-order models appear to be the significantly better choice.
  
  
  CONCLUSIONS
  The traditional PWM model appears to be indeed insufficient to infer realistic sequence motifs, as it is on average outperformed by more complex models that take into account intra-motif dependencies. Moreover, using such models together with an appropriate model selection procedure does not lead to a significant performance loss in comparison with the PWM model for any of the studied transcription factors. Hence, we find it worthwhile to recommend that any modern motif discovery algorithm should attempt to take into account intra-motif dependencies.
authors.affiliation: Institute of Computer Science, Martin Luther University Halle-Wittenberg, Halle, Germany. eggeling@cs.helsinki.fi.|Department of Computer Science, Helsinki Institute for Information Technology HIIT, University of Helsinki, Helsinki, Finland. eggeling@cs.helsinki.fi.
authors.forename: Ralf
authors.initials: R
authors.lastname: Eggeling
authors.affiliation: Department of Computer Science, Helsinki Institute for Information Technology HIIT, University of Helsinki, Helsinki, Finland. teemu.roos@cs.helsinki.fi.
authors.forename: Teemu
authors.initials: T
authors.lastname: Roos
authors.affiliation: Department of Computer Science, Helsinki Institute for Information Technology HIIT, University of Helsinki, Helsinki, Finland. petri.myllymaki@cs.helsinki.fi.
authors.forename: Petri
authors.initials: P
authors.lastname: Myllymäki
authors.affiliation: Institute of Computer Science, Martin Luther University Halle-Wittenberg, Halle, Germany. grosse@informatik.uni-halle.de.|German Center for Integrative Biodiversity Research (iDiv) Halle-Jena-Leipzig, Leipzig, Germany. grosse@informatik.uni-halle.de.
authors.forename: Ivo
authors.initials: I
authors.lastname: Grosse
mesh_terms: D000465:Algorithms; D001665:Binding Sites; D047369:Chromatin Immunoprecipitation / Q000379:methods*; D019295:Computational Biology / Q000379:methods*; D004247:DNA / Q000737:chemistry / Q000235:genetics / Q000378:metabolism*; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D006801:Humans; D008962:Models, Theoretical; D059372:Nucleotide Motifs / Q000235:genetics*; D056510:Position-Specific Scoring Matrices; D011485:Protein Binding; D014157:Transcription Factors / Q000378:metabolism*
chemical_list: D014157:Transcription Factors; D004247:DNA