Structured motif extraction using affinity based cluster analysis

This paper addresses the problem of extracting DNA structured motifs, which are overrepresented gapped patterns in the promoter regions of co-regulated genes. Existing algorithms suffer from three major drawbacks: 1) They are only capable of directly extracting patterns strictly conforming to user specified parameters (templates) that require an unreasonable level of prior knowledge. 2) Some algorithms are only capable of finding limited patterns, such as dyads. 3) The computational effort required by exact algorithms increases exponentially with the number of allowed mismatches in the pattern and the number of boxes in the given template. We present SMExtract, a versatile and efficient algorithm for finding patterns ranging from simple motifs to multi-box structured motifs. The essence of this novel approach is to construct the target unknown pattern by multi-alignment of its fragments. The key benefits are reduction in the number of user specified parameters and flexibility in specifying the number of allowed mismatches regardless of the characteristics of the unknown patterns.