Nucleic Acids Research, 2005, Vol. 33, No. 15 e134 doi:10.1093/nar/gni135 Scoring schemes of palindrome clusters for more sensitive prediction of replication origins in herpesviruses David S. H. Chew1,*, Kwok Pui Choi1,2 and Ming-Ying Leung3,4 1Department of Mathematics and 2Department of Statistics and Applied Probability, National University of Singapore, Singapore, 3Bioinformatics Program and 4Department of Mathematical Sciences, University of Texas at El Paso, El Paso, Texas 79968, USA Received May 30, 2005; Revised June 27, 2005; Accepted August 15, 2005 ABSTRACT Many empirical studies show that there are unusual clusters of palindromes, closely spaced direct and inverted repeats around the replication origins of herpesviruses. In this paper, we introduce two new scoring schemes to quantify the spatial abundance of palindromes in a genomic sequence. Based on these scoring schemes, a computational method to predict the locations of replication origins is developed. When our predictions are compared with 39 known or annotated replication origins in 19 herpesviruses, close to 80% of the replication origins are located within 2% of the genome length. A list of predicted locations of replication origins in all the known herpesviruses with complete genome sequences is reported. INTRODUCTION Early studies (1,2) have reported that the nucleotide sequences around replication origins of certain herpesviruses have com- plex repetitive structures of closely spaced direct and inverted repeats. A palindrome is a special case of inverted repeats where a segment of nucleotide bases is immediately followed by its reverse complement. A high concentration of palin- dromes around replication origins has been found in these herpesviruses. Herpesviruses utilize two different types of replication ori- gins during lytic and latent infections. For each type of origins, the count and locations in the genome vary from one kind of herpesvirus to another. Most herpesviruses have one to two copies of latent and lytic origins. Presence of palindromes around replication origins is prevalent in both latent and lytic types (1–5). As the central step in the reproduction of herpesviruses, viral DNA replication has been the target for a number of anti-herpesvirus drugs (e.g. acyclovir). Understanding the molecular mechanisms involved in DNA replication is of great importance in further developing strategies to control the growth and spread of viruses (6–8). Since replication origins are regarded as major sites for regulating genome replication, labor-intensive laboratory procedures have been used to search for replication origins (9–11). With the increasing availability of genomic DNA sequence data, one way that may save time and resources would be to scan the viral genome sequence for the expected sequence features by a computer program before an experimental search for replication origins is launched. Masse et al. (3) ﬁrst used this computational approach to predict the replication origin oriLyt on the human cytomegalovirus (HCMV) and then con- ﬁrmed it by experimentation. In that computational analysis, one of the sequence features being scanned for in the genome sequence is the presence of a high concentration of palin- dromes of length 10 or above clustering within a window of 1000 bases. A palindrome reads exactly the same from the 50 end to the 30 end on both strands of DNA (see Figure 1 for example). More precisely, we can deﬁne a palindrome to be a word pattern of the form b1. . .bLbL0. . .b10, where b0 is the complement of base b and L is the half-length of the palindrome. We call the letter bL the left-center and bL0 the right-center of the palindrome. The length of the palindrome in Figure 1 is 10 and L ¼ 5. Figure 1. A palindrome of length 10. *To whom correspondence should be addressed. Tel: +65 6847 1653; Fax: +65 6779 5452; Email: matchewd@nus.edu.sg The Author 2005. Published by Oxford University Press. All rights reserved. The online version of this article has been published under an open access model. Users are entitled to use, reproduce, disseminate, or display the open access version of this article for non-commercial purposes provided that: the original authorship is properly and fully attributed; the Journal and Oxford University Press are attributed as the original place of publication with the correct citation details given; if an article is subsequently reproduced or disseminated not in its entirety but only in part or as a derivative work this must be clearly indicated. For commercial re-use, please contact journals.permissions@oupjournals.org