title: cWINNOWER algorithm for finding fuzzy DNA motifs.
abstract: 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 multiple mutated copies of the motif (i.e., the signals) are present in the DNA sequence in sufficient abundance. 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 number of detectable motifs qc as a function of sequence length N for random sequences. We found that q(c) increases linearly with N for a fast version of the algorithm based on counting three-member sub-cliques. Imposing consensus constraints reduces q(c) 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).
authors.affiliation: NASA Ames Research Center, NASA Advanced Supercomputing Division, Moffett Field, CA 94035, USA. Shoudan.Liang@nasa.gov
authors.forename: Shoudan
authors.initials: S
authors.lastname: Liang
mesh_terms: D000465:Algorithms; D020816:Amino Acid Motifs; D001483:Base Sequence; D001665:Binding Sites; D016384:Consensus Sequence; D004247:DNA / Q000235:genetics*; D004268:DNA-Binding Proteins / Q000235:genetics*; D017143:Fuzzy Logic; D008969:Molecular Sequence Data; D011485:Protein Binding; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software; D014157:Transcription Factors / Q000235:genetics*
chemical_list: D004268:DNA-Binding Proteins; D014157:Transcription Factors; D004247:DNA