e134 Nucleic Acids Research, 2005, Vol. 33, No. 15 Palindromes play important roles as protein-binding sites in DNA replication processes [(12), Chapter 1]. The local 2-fold symmetry created by the palindrome provides a binding site for DNA-binding proteins which are often dimeric in structure. Such double binding markedly increases the strength and speciﬁcity of the binding interaction [(13), Chapter 8]. High concentration of palindromes around replication origins is generally attributed to the reason that the initiation of DNA replication typically requires the binding of an assembly of enzymes to these DNA sequences. Helicase is an example of these enzymes known to bind with the initiation site, locally unwind the DNA helical structure, and pull apart the two complementary strands. This explanation is consistent with the observation of AT-rich regions, believed to facilitate the unwinding, in replication origin domains of the genome (5). Leung et al. (14) describe how an evaluation criterion, based on the scan statistics (15,16), is developed for assessing pal- indrome clusters by modeling the occurrences of palindromes in the genome as points randomly sampled from the unit interval according to the uniform distribution. By identifying windows on the genome sequence containing statistically signiﬁcant clusters of palindromes, the scan statistics, in principle, provide a method to predict likely locations of rep- lication origins. This criterion, however, essentially assesses a window of the genome by only the counts of palindrome contained in it, regardless of the actual extent of the palin- drome lengths. This drawback has led to missing some rep- lication origins which contain one extremely long palindrome rather than a cluster of moderately long ones. In the present paper, we propose two new schemes for evaluating palindrome clusters and use the rankings of these evaluation criteria to predict the replication origins in the herpesviruses. By check- ing with known replication origins reported either in published literature or GenBank annotations, we assess the accuracy of the new prediction schemes. These assessments demonstrate that there is a substantial improvement over the original scan statistics criterion. In Methods section, we describe the main steps of the prediction method and three scoring schemes. The ﬁrst scor- ing scheme, called the palindrome count scheme (PCS), is essentially the scan statistics method ﬁrst described by Leung et al. (14), and further discussed in the articles of Leung and Yamashita (17), and Leung et al. (4). Two new scoring schemes, namely, the palindrome length scheme (PLS) and the base-pair weighted scheme (BWS) are introduced as measures of palindrome clusters. In Results and Discussion section, we report the results of applying these scoring schemes to predict the locations of replication origins for 39 fully sequenced herpesviruses, and compare the prediction accuracies in terms of sensitivity and positive predictive value. A few concluding remarks are given in the ﬁnal section. METHODS We propose a computational method to identify regions of a genome which harbor unusual clusters of palindromes. This, in turn, becomes the basis of our method to predict replication origins for the herpesviruses. Table 1 presents the viruses to be analyzed. The data set comprises all complete genome sequences of the herpesvirus family downloaded from GenBank at the NCBI web site in April 2005. For each virus, PAGE 2 OF 8 we list its abbreviation, accession number, sequence length and the relative frequencies of the four nucleotide bases in the genome (see Table 1). Our method for predicting replication origins consists of four basic steps: (i) locate palindromes at or above a prescribed length; (ii) choose a scoring scheme for palindromes; (iii) com- pute a score for each window of the genome according to the chosen scoring scheme; and (iv) select regions with high scores. Step (i): Locating palindromes at or above a prescribed length As very short palindromes occur frequently by chance, a para- meter, L, needs to be chosen where palindromes of length below 2L will not be considered in the analysis. Leung et al. (4) propose a procedure, which is based on bench-marking with the well-studied HCMV virus, for the choice of L. This choice takes into account the length of the sequence, as well as the base frequencies in the genome. Using this criterion, L is chosen to be 6 for the BoHV1, BoHV5, CeHV1, HSV1, HSV2 and SHV1 sequences and 5 for the other sequences. Once the minimal palindrome length has been chosen, the sequences are run through the palindrome program, which is part of EMBOSS [European Molecular Biology Open Software Suite, (18)], to extract the palindrome positions and lengths. Each of these palindromes will be assigned a score according to a scoring scheme chosen in the next step. Note that although it is possible for one palindrome to contain a shorter one in it (e.g. the length 12 palindrome ACCGTGCACGGT contains the length 10 palindrome CCGTGCACGG), EMBOSS auto- matically discards the shorter redundant palindrome and report only the longest one. Step (ii): Choosing a scoring scheme for palindromes Three schemes for scoring palindromes are described. In all of them, any palindrome of length less than 2L will always get a score 0. (i) Palindrome count score (PCS): In this scoring scheme, a palindrome is given a score 1 when its length is at or above 2L. (ii) Palindrome length score (PLS): A palindrome of length 2s > 2L is given a score s/L. For example, if we let L ¼ 5, a palindrome of length 10 will get a score of 1, while one of length 24 will get a score of 2.4. (iii) Base-pair weighted score of order m (BWSm). The idea behind BWS is that a higher score should be given to rarer palindromes, namely those which have lower pro- babilities to occur by chance. We assess the probability of occurrence of a particular palindrome based on Markov type sequence models [(19),Chapter 3]. Here m denotes the order of the Markov chain. Then, we take the negative log- arithm of the probability of a palindrome to give it a positive score which is higher when the probability is lower. We give a simple example of calculating the BWS0 score. In the Markov model with order m ¼ 0, the letters in the sequence are independent of each other. A palindrome con- taining respectively nA, nC, nG, nT of A, C, G and T occurs with probability pnAA pnCC pnG pnT where pA, pC, pG, pT are the relative G T base frequencies in the sequence. The BWS0 score of such a palindrome will be the negative logarithm of this probability,