Efficient representation and P-value computation for high-order Markov motifs.
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.
da Fonseca
Paulo G S
PG
Centro de Informática, Universidade Federal de Pernambuco, 50732-970 Recife, Brazil. paguso@cin.ufpe.br
Guimarães
Katia S
KS
Sagot
Marie-France
MF
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*