Algorithms for Strings and Sequences: Searching Motifs

Strings, sequences and, ultimately, motifs play a key role in bioinformatics. Here, a motif is a biologically relevant pattern occurring in one or more input sequences. In this chapter, first we provide a formal definition of strings, sequences, matches, repetitions and motifs. Then, we present a detailed description of approaches to motif search, based on three possible taxonomies, namely: {\em (i)} the underlying algorithms; {\em (ii)} the kinds of derived motif; {\em (iii)} the kinds of considered match. After this, we illustrate the problem of assessing motif relevance, along with the current solutions. Finally, we draw some closing remarks.