VOTING ALGORITHMS FOR DISCOVERING LONG MOTIFS∗

Pevzner and Sze [14] have introduced the Planted (l,d)-Motif Problem to find the similar patterns (motif) in sequences which represent the promoter region of co-regulated genes. l is the length of the motif and d is the maximum Hamming distance around the similar patterns. Many algorithms have been developed to solve this motif problem. However, these algorithms have the problems that the running times are too long or do not guarantee the motif can be found. In this paper, we introduce new algorithms to solve the motif problem. Our algorithms can find motif in reasonable time not only for the challenging (9,2), (11,3), (15,5)-motif problems but even for longer motifs, say (20,7), (30,11) and (40,15), which has never been seriously attempted by other researchers because of the high time and space complexities.