Motif discovery without alignment or enumeration

Abstract

In this paper, we outline a novel combinatorial algorithm for the discovery of rigid motifs contained in a set of input sequences. This is achieved without pair-wise alignment of the input sequences or enumeration of the entire motif space (solution space). Additionally, the reported motifs are guaranteed to be maximal in both length and composition. Internal repeats and patterns that repeat across sequences are treated uniformly by the algorithm. Results on real datasets are briefly discussed.