Methods for pattern discovery in unaligned biological sequences

Pattern discovery in biological sequences is the problem of finding patterns that are overrepresented in a set of unaligned DNA or protein sequences of related biological function. Such patterns could correspond to regions of the sequences responsible for the function itself, and could be used later for the functional annotation of newly determined sequences. Despite many studies, this problem can be considered far from being solved. The main dif®culty lies in the fact that significant patterns can appear within each sequence with mutations, insertions or deletions of nucleotides or amino acids, without losing their biological function. This paper provides a survey of a number of existing pattern discovery algorithms, focusing both on the methods underlying them and their availability for the scientific community.