Finding motifs in a set of DNA sequences: A dynamic programming approach

The search for motifs in a DNA sequence set is a generic problem area that is of great interest bioinformatics. Given a set of n DNA sequence and a support-rate threshold tau, it is useful to find maximal patterns that occur in at least taun sequences in the set. This paper presents an efficient approach to find motifs for any support-rate threshold and without any miss. The idea is to prune the candidate set of maximal patterns while finding patterns satisfying the given threshold using the dynamic programming method and adding them to the candidate set. Theoretical analysis shows that this approach is efficient and preliminary experiments show that the runtime performance of this approach is satisfactory.