cWINNOWER algorithm for finding fuzzy dna motifs.
The cWINNOWER algorithm detects fuzzy motifs in DNA sequences rich in protein-binding signals. A signal is defined as any short nucleotide pattern having up to d mutations differing from a motif of length l. The algorithm finds such motifs if a clique consisting of a sufficiently large number of mutated copies of the motif (i.e., the signals) is present in the DNA sequence. The cWINNOWER algorithm substantially improves the sensitivity of the winnower method of Pevzner and Sze by imposing a consensus constraint, enabling it to detect much weaker signals. We studied the minimum detectable clique size qc as a function of sequence length N for random sequences. We found that qc increases linearly with N for a fast version of the algorithm based on counting three-member sub-cliques. Imposing consensus constraints reduces qc by a factor of three in this case, which makes the algorithm dramatically more sensitive. Our most sensitive algorithm, which counts four-member sub-cliques, needs a minimum of only 13 signals to detect motifs in a sequence of length N = 12,000 for (l, d) = (15, 4).
NASA Ames Research Center, NASA Advanced Supercomputing Division, Moffett Field, CA 94035, USA. Shoudan.Liang@nasa.gov
S
S
Liang
M P
MP
Samanta
B A
BA
Biegel
D000465:Algorithms; D020816:Amino Acid Motifs / Q000235:genetics*; D001483:Base Sequence; D001665:Binding Sites / Q000235:genetics; D004247:DNA / Q000737:chemistry* / Q000235:genetics*; D017143:Fuzzy Logic; D020869:Gene Expression Profiling / Q000379:methods*; D008969:Molecular Sequence Data; D011485:Protein Binding / Q000235:genetics; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid; D013269:Stochastic Processes
D004247:DNA