e134 Nucleic Acids Research, 2005, Vol. 33, No. 15 Table 3. Regions with significant clusters of palindromes as found by the PCS PAGE 6 OF 8 Virus AlHV1 AtHV3 BoHV1 CalHv3 CCMV CeHV1 CeHV8 CeHV15 EBV EHV1 EHV2 GaHV3 HCMV HCMV-M HHV6b HHV7 HHV8 MCMV MeHV1 MMRV MuHV4 PsHV1 RCMV SHV1 THV A B Region 113 456–113 759 95 350–100 098 77 155–77 168, 102 895–106 948, 113 462–113 636, 124 582–124 756, 131 268–135 221 21 899–23 918, 115 406–117 660, 133 180–133 587 88 376–93 659, 206 555–207 582 112 833–113 219 147 015–147 280, 158 953–164 225 5182–10 840, 32 483–36 810, 137 852–139 781, 150 277–152 289 6772–11 675, 49 460–54 858 115 125–119 096, 144 064–148 035 4911–9106, 147 228–147 250, 171 785–175 980 10 409–11 952, 104 965–105 067, 121 153–123 174, 138 321–138 935, 158 536–159 150 90 515–95 115, 195 962–196 203 90 881–96 835, 175 177–176 003, 201 246–201 487 88 469–94 716 124 985–128 653 21 913–23 705 92 621–93 412, 142 118–142 186 116 644–116 667 3464–3517, 130 148–132 723 96 755–105 094 128 677–131 155, 151 017–153 495 74 134–76 485, 118 126–118 854 36 683–41 606 10 089–11 213 For example, for the virus EBV, the region 6772–11 675 bp (and 49 460–54 858 bp) is deemed to contain a high concentration of palindromes. BoHV4, BoHV5, CeHV2, CeHV7, EHV4, GaHV1, GaHV2, HHV6, HSV1, HSV2, IcHV1, OsHV1, SaHV2 and VZV have no significant clusters of palindromes. Figure 3. Sensitivity and positive predictive values of the PLS and BWS. 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 per- centage of identified regions that are close to the known origins. The sensitivity and positive predictive values of the PCS are 15 and 25, respectively. A B Figure 4. Sensitivity and positive predictive values of l ocal BWS. The compound Poisson distribution is motivated from a marked Poisson process point of view. The occurrence of a palindrome of length 2L and above is modeled by a Poisson process (4), and the actual length of this palindrome is modeled by a geometric distribution. On closer examination of the known replication origins in this set of genome sequences, we notice that some of the origins missed by this prediction algorithm are actually rather long approximate palindromes. They are missed because we choose to consider only the perfect palindromes. For example, in HSV2, allowing just one error would have let us pick up a 136 base long approximate palindrome centered at 62 930, which is where the reported replication origin is located. If we include these approximate palindromes in our considera- tion, the sensitivity can be further increased. CONCLUDING REMARKS It is mentioned in the introduction that palindromes are merely one type of sequence features known to be associated with replication origins. Other frequently observed characteristics around replication origins include clustering of closely spaced direct and inverted repeats, as well as high AT content. We have actually examined each of these other types of sequence features and found that none of them, when used alone on our data set, reaches the same level of prediction accuracy offered by the BWS. However, it is likely that the prediction accuracy can be further improved by appropriately incorporating them in the prediction scheme. In fact, several replication origins in BoHV4, EHV4 and HSV2 which are not identiﬁed by any of PCS, PLS or BWS can be easily detected by the high local AT content around them. Exactly in what way all the different