Algorithms for challenging motif problems.
Pevzner and Sze(19) have introduced the Planted (l,d)-Motif Problem to find similar patterns (motifs) in sequences which represent the promoter regions of co-regulated genes, where 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 either have long running times or do not guarantee the motif can be found. In this paper, we introduce new algorithms to solve this motif problem. Our algorithms can find motifs in reasonable time for not only the challenging (9, 2), (11, 3), (15, 5)-motif problems but for even longer motifs, say (20, 7), (30, 11) and (40, 15), which have never been seriously attempted by other researchers because of the large time and space required. Besides, our algorithms can be extended to find more complicated motifs structure called cis-regulatory modules (CRM).
Department of Computer Science, The University of Hong Kong, Pokfulam, Hong Kong, China. cmleung2@cs.hku.hk
Henry C M
HC
Leung
Francis Y L
FY
Chin
D000465:Algorithms; D001665:Binding Sites / Q000235:genetics; D019295:Computational Biology; D004247:DNA / Q000235:genetics* / Q000378:metabolism*; D011401:Promoter Regions, Genetic; D014157:Transcription Factors / Q000378:metabolism
D014157:Transcription Factors; D004247:DNA