Your browser version may not work well with NCBI's Web applications. More information here...
1: Algorithms Mol Biol. 2006 Nov 16;1:21.Click here to read Click here to read Links

EXMOTIF: efficient structured motif extraction.

Zhang Y, Zaki MJ.

Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York 12180, USA. zhangy0@cs.rpi.edu

BACKGROUND: Extracting motifs from sequences is a mainstay of bioinformatics. We look at the problem of mining structured motifs, which allow variable length gaps between simple motif components. We propose an efficient algorithm, called EXMOTIF, that given some sequence(s), and a structured motif template, extracts all frequent structured motifs that have quorum q. Potential applications of our method include the extraction of single/composite regulatory binding sites in DNA sequences. RESULTS: EXMOTIF is efficient in terms of both time and space and is shown empirically to outperform RISO, a state-of-the-art algorithm. It is also successful in finding potential single/composite transcription factor binding sites. CONCLUSION: EXMOTIF is a useful and efficient tool in discovering structured motifs, especially in DNA sequences. The algorithm is available as open-source at: http://www.cs.rpi.edu/~zaki/software/exMotif/.

PMID: 17109757 [PubMed]

PMCID: PMC1698483