Many simple motif extraction algorithms have been proposed primarily for extracting the transcription factor binding sites, where each motif consists of a unique binding site [4-10] or two binding sites separated by a fixed number of gaps [11-13]. A pattern with a single component is also called a monad pattern. Structured motif extraction problems, in which variable number of gaps are allowed, have attracted much attention recently, where the structured motifs can be extracted either from multiple sequences [14-21] or from a single sequence [22,23]. In many cases, more than one transcription factor may cooperatively regulate a gene. Such patterns are called composite regulatory patterns. To detect the composite regulatory patterns, one may apply single binding site identification algorithms to detect each component separately. However, this solution may fail when some components are not very strong (significant). Thus it is necessary to detect the whole composite regulatory patterns (even with weak components) directly, whose gaps and other possibly strong components can increase its significance.