Fast Approximate Motif Statistics, Pierre Nicodème (2001).

We present in this article a fast approximate method for computing the statistics of number of non self-overlapping matches of motifs in a random text in the non-uniform Bernoulli model. This method is well suited for protein motifs where the probability of self-overlap of motifs is small. For 96% of the Prosite motifs, the expectations of occurrences of the motifs in a 7 million amino-acids random database are computed by the approximate method with less than 1% error when compared with the exact method. Processing of the whole Prosite takes about 30 seconds with the approximate method. We apply this new method to a comparison of the C. elegans and S. cerevisiae proteoms.