e20 Nucleic Acids Research, 2007, Vol. 35, No. 3 PAGE 4 OF 9 Figure 2. The robustness to decoy sequences (DSs) of Gibbs sampling with and without positional clustering. Fifty-one increasingly noisy STE12- binding site enriched datasets were analyzed using Gibbs sampling with positional clustering (red solid line) and without (black solid line). The dotted lines represent controls, e.g. identification of STE12-like motifs by Gibbs sampling (black dotted line) and positional clustering (red dotted line) given random upstream regions. x-axis counts over the addition of DSs. Each set of DSs was chosen independently from all upstream regions in the S.cerevisiae genome. We evaluated the positive predictive value of each technique on each dataset, and found positional clustering significantly improved the PPV through addition of 45 DSs. segments in repeated runs using the same input data. Identi- fying stably recurring motifs requires clustering of related results which, in turn, requires deﬁnition of ‘related’. Sequence similarity based clustering is impaired by the com- bination of sequence variation within motifs, the short length of TF-binding sites, and aligning motifs of different lengths. Instead of using sequence based clustering, we chose to clus- ter results by position, counting the number of times Gibbs sampling identiﬁes each nucleotide in the promoter (Figure 1). We ﬁnd that Gibbs sampling predictions, gener- ated using BioProspector (8) are power-law distributed over nucleotide position (Supplementary Figure S2). Gibbs sam- pling converges on the majority of nucleotides very infre- quently, and a small number of nucleotides very frequently. Thus, the most frequently recurring nucleotides appear in as few as 10% of results. Moreover, we ﬁnd the power-law dis- tribution of results is robust to Gibbs sampling algorithm and scoring scheme (data not shown). We can hypothesize that the most frequently occurring positions are the most biologi- cally signiﬁcant. Thus, discarding the least frequent Gibbs sampling results may yield higher accuracy and robust iden- tiﬁcation of biologically insigniﬁcant positions. As a preliminary test of the above hypothesis, we applied repeated runs of Gibbs sampling to a set of 51 S.cerevisiae promoters enriched in STE12 binding as identiﬁed by whole- genome ChIP-chip experiments (10). We used positional clus- tering of 1200 results to identify the most frequently recurring positions (see Methods). Incorporation of additional results did not signiﬁcantly alter the distribution of results (data not shown). We chose STE12 because it is one of the best studied TFs, with a well known, highly conserved and experimentally well-deﬁned binding motif (10,43). The most frequently recurring positions were compared with the known STE12- binding motif (40). We classiﬁed predictions into two cate- gories: true positive (TP) if they resemble the experimentally identiﬁed STE12-binding motif, and false positive (FP) other- wise (see Methods). Finally, we calculated the positive predic- tive value PPV as PPV ¼ TP/(TP + FP). We ﬁnd that positional clustering and subsequent selection of frequently recurring nucleotides improved the PPV of the STE12 binding site by at least 37% over Gibbs sampling alone (Figure 2). To validate that the above results were not speciﬁc to the number of input promoters, the STE12-binding motif, or the particular Gibbs sampling implementation, we repeated the above prediction process for promoters predicted to bind to YAP1, TEC1, HAP4 and YDR026C. We also repeated the analysis replacing the original Gibbs sampling procedure with our own implementation and MotifSampler (44). In all cases, we found positional clustering signiﬁcantly improves on results over local optimization procedures alone (Figure 3). Computational discovery of TFBS can have two types of FP predictions. One type is the identiﬁcation of an incorrect motif from a set of upstream regions known to bind to a TF of interest as described above (see Methods). The second type of FP error is the background discovery rate of the correct motif using upstream regions that do not bind to the TF. To simulate this rate for STE12-like binding site recovery we repeated the analysis as described above starting with 51 ran- domly chosen yeast promoters. We ﬁnd that positional clus- tering identiﬁes STE12-like sites in <5% of results, compared with 10–15% for Gibbs sampling alone. Thus, using posi- tional clustering, the performance of computational motif discovery is enhanced not only by improving the positive pre- dictive value in promoters of genes co-regulated by STE12, but also by decreasing the false discovery of STE12-like sites by 10%. Robustness to DSs Next, we evaluated the effect of adding DSs on the perfor- mance of Gibbs sampling with and without positional cluster- ing. Addition of DSs dilutes enrichment of the TF-binding site in the input set, making motif detection more challenging (17,22). Modeling DSs, we repeated our estimate of PPV of TFBS detection with the addition of 1–50 random yeast pro- moters (DSs) to the original set of 51 STE12-bound promot- ers. We found that positional clustering improves the PPV of Gibbs sampling by >20% through the addition of up to 80% noise or 40 DSs (Figure 2, Supplementary Figure S3). Addi- tionally, results of Gibbs sampling both with and without positional clustering decay linearly with the addition of decoys [R2 ¼ 0.81 and 0.95, respectively (Supplementary Figure S4)]. Extrapolating, we predict positional clustering will maintain an improved PPV through the addition of >100% noise or 70 DSs. To address issues of generality, we repeated the procedure on additional sets of S.cerevisiae promoters (YAP1, TEC1, HAP4 and YDR026C). An added beneﬁt is that we can evalu- ate the effect of information content of the binding motif and number of promoters on the improvement from positional clustering (22). Repeating the analysis, we again ﬁnd that independently of the set or sampling procedure, positional