PAGE 5 OF 8 Table 2. High scoring windows of PLS and BWS1 Nucleic Acids Research, 2005, Vol. 33, No. 15 e134 Virus AlHV1 AtHV3 BoHV1 BoHV4 BoHV5 CalHV3 CCMV CeHV1 CeHV15 CeHV2 CeHV7 CeHV8 EBV EHV1 EHV2 EHV4 GaHV1 GaHV2 GaHV3 HCMV HCMV-M HHV6 HHV6B HHV7 HHV8 HSV1 HSV2 IcHV1 MCMV MeHV1 MMRV MUHV4 OsHV1 PSHV1 RCMV SaHV2 SHV1 THV VZV PLS rankings 1 113 701 99 001 113 401 30 251 19 201 116 201 91 201 133 001 8001 129 501 18 601 161 151 7601 116 201 6301 105 351 41 651 160 801 158 801 94 051 175 451 30 101 90 401 133 351 23 401 62 301 74551 55 501 92 951 5601 132 601 99 251 21 001 130 401 75 901 103 751 38 151 134 101 119 401 2 32 701 54 751 124 501 54 751 78 001 133 351 207 001 149 451 34 801 144 201 93 601 147 401 53 201 146 651 54 001 142 801 68 601 801 138 401 196 351 94 051 8051 69 201 9451 119 401 129 851 7351 9301 142 451 117 951 3301 26 251 144 001 151 601 110 551 112 501 93 101 10 801 110 101 3 123 301 97 001 103 801 72 251 107 401 23 101 177 001 61 601 138 801 61 601 15 601 198 001 127 601 47 601 173 251 3851 99 751 137 601 11 201 77 001 153 451 110 601 132 801 127 401 15 001 148 401 119 701 89 701 200 201 11 551 117 601 62 001 185 001 26 801 83 601 27 751 11 551 50 401 100 501 BWS1 rankings 1 113 701 99 251 113 401 54 751 18 901 116 201 91 201 133 001 8001 129 501 18 601 161 151 7601 116 201 54 001 105 351 68 601 160 801 158 801 94 051 175 451 8051 90 801 9451 23 401 62 301 74 551 55 501 92 951 5601 132 601 99 251 21 001 130 401 75 901 103 751 38 151 134 101 119 401 2 123 301 97 001 124 501 30 251 113 401 133 351 207 001 149 451 34 801 144 201 106 201 147 401 53 201 147 001 6301 143 151 41 651 801 138 401 174 901 94 051 30 101 132 801 152 251 119 701 129 851 28 001 89 701 142 451 117 951 117 601 26 251 144 001 151 601 110 551 112 501 11 551 10 801 110 101 3 32 701 54 751 87 301 72 251 129 601 23 101 177 001 61 601 138 801 61 601 121 801 198 001 127 601 47 601 173 251 109 901 99 751 137 601 11 201 196 351 153 451 110 601 8801 133 351 136 501 148 401 12 951 9301 200 201 11 551 3301 62 001 187 501 18 801 83 601 81 501 93 101 144 901 100 501 The numbers in the table indicate the middle positions of the windows. Rows that are shaded indicate that the particular viruses have known replication origins either from literature or from annotation. Underlined entries denote the middle positions of the windows which are within 2 map units (i.e. 2% of the genome length) of known replication origins. probability of occurrence than shorter ones. Moreover, the BWS takes into account the base and word frequencies which affect the probability of occurrence of the palindrome. Consider, for example, the BWS0 score ðnA log pA þ nC log pC þ nG log pG þ nT log pT Þ can be viewed as a weighted sum, with weights according to the negative logarithms of the base frequencies. If the base probabilities are all equal, the BWS0 will reduce to (log 4)(nA + nC + nG + nT) which is equal to (log 4) · Length of palindrome and hence is equivalent to the PLS. In essence, the BWS includes more information about the sequence in its prediction and so we expect it to give better prediction accuracy. Our results show that this is indeed true. When we choose to use 3 or more top ranking windows, the BWS performs better than the PLS in terms of (higher) sens- itivity and positive predictive value. Suspecting that the probability of occurrence of palin- dromes might not be well estimated on the basis of a global base and word frequencies, we also try calculating palindrome probabilities using the base and word frequencies of those at the local window rather than those of the entire genome. Figure 4 shows the sensitivity and positive predictive values of the local BWS of order 0, 1 and 2. We use BWSm(Local) to represent the local version of BWS of order m. According to these results, the local version still does not perform any better than BWS1. Further improvement of the algorithm While our results show that using PLS and BWS with the ranking approach clearly outperforms the PCS, we have to note that the PCS is the only scheme where a rigorous statistical signiﬁcance criterion, based on the probability distribution of the scan statistics, is currently available. The probability distributions of the maximal window scores with PLS and BWS have yet to be established. We have some preliminary results on approximating the distributions of the window score under PLS by compound Poisson distribution.