title: Efficient representation and P-value computation for high-order Markov motifs.
abstract: BACKGROUND
  Position weight matrices (PWMs) have become a standard for representing biological sequence motifs. Their relative simplicity has favoured the development of efficient algorithms for diverse tasks such as motif identification, sequence scanning and statistical significance evaluation. Markov chainbased models generalize the PWM model by allowing for interposition dependencies to be considered, at the cost of substantial computational overhead, which may limit their application.
  
  
  RESULTS
  In this article, we consider two aspects regarding the use of higher order Markov models for biological sequence motifs, namely, the representation and the computation of P-values for motifs described by a set of occurrences. We propose an efficient representation based on the use of tries, from which empirical position-specific conditional base probabilities can be computed, and extend state-of-the-art PWM-based algorithms to allow for the computation of exact P-values for high-order Markov motif models.
  
  
  BACKGROUND
  The software is available in the form of a Java objectoriented library from http://www.cin.ufpe.br/approxiamtely paguso/kmarkov.
authors.affiliation: Centro de Informática, Universidade Federal de Pernambuco, 50732-970 Recife, Brazil. paguso@cin.ufpe.br
authors.forename: Paulo G S
authors.initials: PG
authors.lastname: da Fonseca
authors.forename: Katia S
authors.initials: KS
authors.lastname: Guimarães
authors.forename: Marie-France
authors.initials: MF
authors.lastname: Sagot
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D003627:Data Interpretation, Statistical; D008390:Markov Chains; D008956:Models, Chemical; D008957:Models, Genetic; D015233:Models, Statistical; D017421:Sequence Analysis / Q000379:methods*