Bioinformatics Advance Access published online on October 9, 2008
Bioinformatics, doi:10.1093/bioinformatics/btn525
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Faster exact Markovian probability functions for motif occurrences: a DFA-only approach
1Bioinformatics and Genomics Unit Center for Genomic Regulation, C/ Dr.Aiguader 88, E08003 Barcelona, Spain
*To whom correspondence should be addressed. Dr. Paolo Ribeca, E-mail: paolo.ribeca{at}gmail.com
 |
Abstract |
|---|
Background: The computation of the statistical properties of motif occurrences has an obviously relevant application: patterns that are significantly over- or under-represented in genomes or proteins are interesting candidates for biological roles. However, the problem is computationally hard; as a result, virtually all the existing motif finders (for instance Bailey and Elkan, 1994 or Ettwiller et al., 2007) use fast but approximate scoring functions, in spite of the fact that they have been shown to produce systematically incorrect results (Nuel, 2006a,b). A few interesting exact approaches are known (Nuel, 2006a; Zhang et al., 2007), but they are very slow and hence not practical in the case of realistic sequences.
Results: We give an exact solution, solely based on deterministic finite-state automata (DFAs), to the problem of finding the whole relevant part of the probability distribution function of a simple-word motif in a homogeneous (biological) sequence. Out of that, the z-value can always be computed, while the p-value can be obtained either when it is not too extreme with respect to the number of floating-point digits available in the implementation, or when the number of pattern occurrences is moderately low. In particular, the time complexity of the algorithms for Markov models of moderate order (0 
m 2) is far better than that of Nuel (2006a), which was the fastest similar exact algorithm known to date; in many cases, even approximate methods are outperformed.
Conclusions: DFAs are a standard tool of computer science for the study of patterns; previous works in biology (Nicodème et al., 2002; Nuel, 2006a) propose algorithms involving automata, but there they are used respectively as a first step to write a generating function, or to build a Finite Markov Chain Imbedding (FMCI). In contrast, we direclty rely on DFAs to perform the calculations; thus we manage to obtain an algorithm which is both easily interpretable and effi-cient. This approach can be used for exact statistical studies of very long genomes and protein sequences, as we illustrate with some examples on the scale of the human genome.
Contact: paolo.ribeca{at}gmail.com
Associate Editor: Dr. Limsoon wong
Received on January 30, 2008; revised on September 30, 2008; accepted on October 7, 2008
CiteULike 
Connotea 
Del.icio.us What's this?