We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
ALGORITHMS FOR CHALLENGING MOTIF PROBLEMS.
- Authors
LEUNG, HENRY C. M.; CHIN, FRANCIS Y. L.
- Abstract
Pevzner and Sze19 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).
- Subjects
COMPUTATIONAL biology; ALGORITHMS; ALGEBRA; GENES; GENETICS
- Publication
Journal of Bioinformatics & Computational Biology, 2006, Vol 4, Issue 1, p43
- ISSN
0219-7200
- Publication type
Article
- DOI
10.1142/S0219720006001692