Compositional searching of CpG islands in the human genome

We report on an entropic edge detector based on the local calculation of the Jensen-Shannon divergence with application to the search for CpG islands. CpG islands are pieces of the genome related to gene expression and cell differentiation, and thus to cancer formation. Searching for these CpG islands is a major task in genetics and bioinformatics. Some algorithms have been proposed in the literature, based on moving statistics in a sliding window, but its size may greatly influence the results. The local use of Jensen-Shannon divergence is a completely different strategy: the nucleotide composition inside the islands is different from that in their environment, so a statistical distance—the Jensen-Shannon divergence—between the composition of two adjacent windows may be used as a measure of their dissimilarity. Sliding this double window over the entire sequence allows us to segment it compositionally. The fusion of those segments into greater ones that satisfy certain identification criteria must be achieved in order to obtain the definitive results. We find that the local use of Jensen-Shannon divergence is very suitable in processing DNA sequences for searching for compositionally different structures such as CpG islands, as compared to other algorithms in literature.

Figure 1

The original DNA sequence is composed of adenine, guanine, cytosine, and thymine $(A,G,C,T)$, and eventually $N$ when masked or unknown. The algorithm first encodes the DNA sequence to binary, being 1 if a $CG$ pair is found and 0 otherwise. A sliding double window then runs the binary sequence and the weighted ${\delta }_{\mathit{JS}}$ is calculated at each position, as shown. As is customary, base 2 is used hereinafter for logarithms.

Figure 2

Sensibility $Q_{\mathit{sn}}$ and specificity $Q_{\mathit{sp}}$ values when the window size is varied from 100 to 2500 bp. Sampling interval is fixed at 5 bp. CPGED is the proposed method.

Figure 3

Sensibility $Q_{\mathit{sn}}$ and specificity $Q_{\mathit{sp}}$ values when the sampling interval is varied from 5 to 100 bp. Window size is fixed at 200 bp. CPGED is the proposed method.