e134 Nucleic Acids Research, 2005, Vol. 33, No. 15 PAGE 4 OF 8 Figure 2. Sliding window plots of HCMV and HSV1 using PCS, PLS and BWS0. The first window spans the first through the wth bases, the second the ( w 2 þ 1)th to ( 32w)th bases, and so on. The score of a window is the total of the scores of all the palindromes occurring in this window according to PCS, PLS or BWS0. the windows are plotted against the position of the window. For HCMV, the highest scoring window is the same for all three schemes. This window corresponds to the oriLyt of the HCMV identiﬁed by Masse et al. (3). For HSV1, however, the plot of the PCS look rather different from those of the PLS and BWS. The highest scoring window in each of PLS and BWS corresponds to the oriL, and the two next highest peaks are close to the two oriS. In contrast, the PCS fails to locate any signiﬁcant clusters of palindromes. Table 2 shows the top 3 scoring windows for each of the 39 viruses under both the PLS and BWS schemes. The numbers in the table indicate the middle positions of the windows. In cases where two or more high scoring windows are close to one another, only one of them is picked to represent the region that gave the high scores. We adopt the practice that when a certain high scoring window is chosen, the neighboring 8 windows both to the left and to the right of it will not be considered subsequently. Rows that are shaded indicate that the particular viruses have known replication origins either from literature or from annotation. Underlined entries denote the middle posi- tions of the windows which are within 2 map units (a map unit, abbreviated mu, is 1% of the genome length) of known rep- lication origins. Shaded rows without any underlined entries show that the computational method fails to predict the known origins of replication. Finally, rows that are not shaded denote those viruses whose origins of replication are not known, as far as we know. Table 3 lists the regions with signiﬁcant clusters of palindromes as found by the PCS scheme. Prediction accuracy We next examine the correspondence between the locations of these high scoring windows and those of the known replication origins. From Genbank sequence entries, annotations and literature, we are able to compile a list of 39 known replication origins for some of the viruses in our dataset. Table 4 shows the distance between each known origin from the nearest signiﬁcant palindrome cluster for PCS, or the nearest high scoring window for PLS and BWS1 if the center of the cluster or window is within 2 mu of the origin. Otherwise a ‘—’ is entered. The distance is calculated from the mid-point of the window to the mid-point of the closest replication origin. Clearly, Table 4 shows that both PLS and BWS present a substantial improvement in the prediction accuracy of replica- tion origins. For the PLS and BWS, we have used the top 3 scoring windows for each virus to construct this table. Prediction accuracy of the different schemes can be quan- tiﬁed by two commonly accepted measures: sensitivity and positive predictive value (PPV). In our context, sensitivity is the percentage of known origins that are close to the regions suggested by the prediction; and positive predictive value is the percentage of identiﬁed regions that are close to the known origins. Figure 3 shows the performance of the various schemes. For the PLS and BWS1, the sensitivity and positive predictive value using 1–10 top scoring windows are given in percentages. Results from BWS0 and BWS2 are also obtained (data not shown). Their prediction accuracies are close to but slightly less than that of BWS1. Note that as the number of windows increases, we gain in sensitivity but at the same time lose in positive predictive value. The highest sensitivities attained by PLS and BWS1 are 67 and 79%, respectively. The highest positive predictive values for both schemes are 47%. Difference between PLS and BWS Note that both PLS and BWS take the length of the palindromes into account, as longer palindromes have lower