Pattern recognition in DNA sequences and its application to consensus foot-printing.

We consider the problem of comparing several nucleic acid sequences to identify words occurring imperfectly (patterns with no gap) with unusual frequency. Methods for computing, representing, and inspecting interactively the structure of such repeating motifs in nucleic acids and more generally any text are described. Multiple sequences are treated as one large concatenate. In a preprocessing step, a lexical index is created to provide rapid string matching for the enumeration of the words matching a pattern. For given word features (word length, minimal frequency), a sequence profile is displayed. The profile can be inspected interactively with on-line algorithms. Applications to the identification of regulatory elements in DNA regions involved in the control of gene expression are presented. Our program ('DNA-Lexemics') runs on the Macintosh.