Subtle motifs: defining the limits of motif finding algorithms.
BACKGROUND
What constitutes a subtle motif? Intuitively, it is a motif that is almost indistinguishable, in the statistical sense, from random motifs. This question has important practical consequences: consider, for example, a biologist that is generating a sample of upstream regulatory sequences with the goal of finding a regulatory pattern that is shared by these sequences. If the sequences are too short then one risks losing some of the regulatory patterns that are located further upstream. Conversely, if the sequences are too long, the motif becomes too subtle and one is then likely to encounter random motifs which are at least as significant statistically as the regulatory pattern itself. In practical terms one would like to recognize the sequence length threshold, or the twilight zone, beyond which the motifs are in some sense too subtle.


RESULTS
The paper defines the motif twilight zone where every motif finding algorithm would be exposed to random motifs which are as significant as the one which is sought. We also propose an objective tool for evaluating the performance of subtle motif finding algorithms. Finally we apply these tools to evaluate the success of our MULTIPROFILER algorithm to detect subtle motifs.
Keich
U
U
Department of Computer Science and Engineering, University of California San Diego, La Jolla, CA 92093, USA. keich@cs.ucsd.edu
Pevzner
P A
PA
D000465:Algorithms; D020816:Amino Acid Motifs / Q000235:genetics*; D001483:Base Sequence; D019985:Benchmarking; D016384:Consensus Sequence / Q000235:genetics; D004247:DNA / Q000235:genetics; D004252:DNA Mutational Analysis / Q000379:methods; D008957:Models, Genetic; D015233:Models, Statistical; D008969:Molecular Sequence Data; D011786:Quality Control; D012045:Regulatory Sequences, Nucleic Acid / Q000235:genetics*; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software; D013269:Stochastic Processes
D004247:DNA