A Fast and Effective Heuristic Algorithm for Finding Quorum Planted (l, d, q)-Motifs

In this paper, we propose a fast and effective heuristic algorithm for de novo discovery of quorum planted (l, d, q)-motifs in sequences. Theoretically, the algorithm has a worst-case time complexity of O(n 2m2 l)), where n is the number of sequences, m is the maximum length of sequences, and l is the size of the motif to be discovered. Most notably, in practice, the algorithm can produce bestquality motifs in just a matter of seconds for any size of motifs. We evidence the effectiveness and the speed of our algorithm with some empirical results.