title: Fast motif matching revisited: high-order PWMs, SNPs and indels.
abstract: While the position weight matrix (PWM) is the most popular model for sequence motifs, there is growing evidence of the usefulness of more advanced models such as first-order Markov representations, and such models are also becoming available in well-known motif databases. There has been lots of research of how to learn these models from training data but the problem of predicting putative sites of the learned motifs by matching the model against new sequences has been given less attention. Moreover, motif site analysis is often concerned about how different variants in the sequence affect the sites. So far, though, the corresponding efficient software tools for motif matching have been lacking.
  
  
  
  We develop fast motif matching algorithms for the aforementioned tasks. First, we formalize a framework based on high-order position weight matrices for generic representation of motif models with dinucleotide or general q -mer dependencies, and adapt fast PWM matching algorithms to the high-order PWM framework. Second, we show how to incorporate different types of sequence variants , such as SNPs and indels, and their combined effects into efficient PWM matching workflows. Benchmark results show that our algorithms perform well in practice on genome-sized sequence sets and are for multiple motif search much faster than the basic sliding window algorithm.
  
  
  
  Implementations are available as a part of the MOODS software package under the GNU General Public License v3.0 and the Biopython license ( http://www.cs.helsinki.fi/group/pssmfind ).
  
  
  
  janne.h.korhonen@gmail.com.
authors.affiliation: School of Computer Science, Reykjavík University, Reykjavík, Iceland.|Helsinki Institute for Information Technology HIIT, Helsinki, Finland.|Department of Computer Science.
authors.forename: Janne H
authors.initials: JH
authors.lastname: Korhonen
authors.affiliation: Genome-Scale Biology Research Program, Research Programs Unit.
authors.forename: Kimmo
authors.initials: K
authors.lastname: Palin
authors.affiliation: Department of Biosciences and Nutrition, Karolinska Institutet, Genome Scale Biology Program, Faculty of Medicine, University of Helsinki, Helsinki, Finland.
authors.forename: Jussi
authors.initials: J
authors.lastname: Taipale
authors.affiliation: Helsinki Institute for Information Technology HIIT, Helsinki, Finland.|Department of Computer Science.
authors.forename: Esko
authors.initials: E
authors.lastname: Ukkonen
mesh_terms: D000465:Algorithms; D002892:Chromosomes, Human, Pair 22; D006801:Humans; D054643:INDEL Mutation; D020641:Polymorphism, Single Nucleotide; D056510:Position-Specific Scoring Matrices; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software