Encoding and Decoding DNA Sequences by Integer Chaos Game Representation

Abstract

DNA sequences are fundamental for encoding genetic information. The genetic information may be understood not only from symbolic sequences but also from the hidden signals inside the sequences. The symbolic sequences need to be transformed into numerical sequences so the hidden signals can be revealed by signal processing techniques. All current transformation methods encode DNA sequences into numerical values of the same length. These representations have limitations in the applications of genomic signal compression, encryption, and steganography. We propose a novel integer chaos game representation (inter-CGR or iCGR) of DNA sequences and a lossless encoding method DNA sequences by the iCGR. In the iCGR method, a DNA sequence is represented by the iterated function of the nucleotides and their positions in the sequence. Then the DNA sequence can be uniquely encoded and recovered using three integers from iCGR. One integer is the sequence length and the other two integers represent the accumulated distributions of nucleotides in the sequence. The integer encoding scheme can compress a DNA sequence by 2 bits per nucleotide. The integer representation of DNA sequences provides a prospective tool for sequence analysis and operations.

1. Introduction

In recent years, the next-generation sequencing (NGS) techniques have resulted in massive DNA and protein sequences. There are strong demands for efficiently analyzing these genomic sequences. A DNA sequence consists of four types of nucleotides: adenine (A), guanine (G), thymine (T), and cytosine (C). DNA sequence analysis requires conversion of a symbolic sequence to a numerical sequence so that intrinsic patterns and characters can be characterized by digital signal processing approaches (Anastassiou, 2000; Mendizabal-Ruiz et al., 2017; Yin and Yau, 2008; Yin and Wang, 2016). Numerical representations of DNA sequences are also essential to genome comparison, compression, encryption, and steganography.

An effective numerical representation must be able to capture all significant properties of the biological reality without introducing any spurious effects. Currently, the most commonly used encoding method is the Voss 4D binary indicator representations (Felsenstein et al., 1982; Voss, 1992), which has been used in protein-coding prediction, similarity analysis, and periodicity detection in genomes. However, the Voss 4D method and DNA sequence mapping are not one-to-one. In 1990, Jeffrey first proposed a numerical and graphical chaos game representation (CGR) of a DNA sequence (Jeffrey, 1990). The CGR is generated in a square with the four vertices for the nucleotides A, C, G, and T, respectively. In the CGR graph, the first point is placed on the halfway position between the center of the unit square and the vertex of the unit square for the first nucleotide of the DNA sequence. The successive point is generated on the halfway position between the previous CGR point and the vertex for the current nucleotide of the sequence. An important feature of the CGR is that the value of any point in CGR contains the historical information of the preceding sequence and visually displays all subsequent frequencies of a given DNA sequence. The CGR preserves all statistical properties of DNA sequences and allows investigation of both local and global patterns in DNA sequences, visually revealing previously hidden sequence structures. The CGR was then developed for k-mer counting and referred to frequency CGR, which renders a unique two-dimensional (2D) image signature for a genome sequence.

Because CGR has a remarkable ability to differentiate between genetic sequences belonging to different species, it has thus been proposed as a genomic signature (Deschavanne et al., 1999; Almeida et al., 2001). Owing to the character of information preservation of CGR, it has been applied in different research domains, including similarity analysis of genomes (Stan et al., 2010; Kari et al., 2015; Joseph and Sasikumar, 2006; Hoang et al., 2016) and detection of hidden periodicity signal in genomes (Messaoudi et al., 2014; Yin and Yau, 2005; Yin et al., 2014). However, all existing numerical representation methods of DNA sequences produce a list of values of the same length of DNA sequences, and these types of representations cannot be directly used for storing, compressing, encrypting, and aligning DNA sequences.

In this article, we propose an integer chaos game representation (iCGR) of DNA sequences, in which nucleotides of DNA sequences are represented by iterated integer functions. Using iCGR, a DNA sequence can be uniquely encoded and recovered by three integers. One of the integers is the length of the DNA sequence, and the other two integers are determined by the type and positions of nucleotides in the DNA sequence. One application of the encoding is to compress DNA sequences. The result shows that 2 bits are required for storing a nucleotide symbol in integer encoding, whereas the common character representation of a nucleotide needs 8 bits. The proposed method will have wide applications in NGS analysis.

2. Methods and Algorithms

2.1. CGR of DNA sequences

CGR is an iterative mapping and scale-independent representation for geometric representation of DNA sequences (Jeffrey, 1990). The CGR space can be viewed as a continuous reference system, where all possible sequences of any length occupy a unique position. The position is produced by the four possible nucleotides, which are treated as vertices of a unit binary square since a DNA sequence can be treated formally as a string of the four letters A, C, G, and T. In this study, we redesign the CGR corners of four nucleotides so the relationship between two nucleotides can be reflected by the distances of the CGR corners. The CGR vertices are assigned to the four nucleotides as \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A \; = \; \left( {1 , \;1} \right) , \;T = \left( { - 1 , \;1} \right) , \;C = \left( { - 1 , \; - 1} \right)$$ \end{document} , and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$G = \left( {1 , - 1} \right)$$ \end{document} (Fig. 1a). The CGR coordinates are calculated iteratively by moving a pointer to half the distance between the previous position and the current binary representation (Algorithm 1). For example, if the next nucleotide on the DNA sequence is G, then a point is plotted halfway between the previous point and the G corner. The resulting graphic is planar, thus we call it as classical CGR representation. A CGR example of a short DNA sequence, TAGCA, is illustrated in Figure 1b. The CGR representation of human mitochondrial genome is shown in Figure 2. The CGR of human mitochondrial genome reveals the fractal patterns within the genome.

FIG. 1.

(a) Numerical representation of four nucleotides A, T, C, and G in CGR. (b) The CGR graph of the DNA sequence, TAGCA. The corresponding CGR coordinates are: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${T_1} \left( { - 0.5000 , 0.5000} \right) , {A_2} \left( {0.2500 , 0.7500} \right) , {G_3} \left( {0.6250 , - 0.1250} \right) , {C_4} \left( { - 0.1875 , - 0.5625} \right) , {A_5} \left( {0.4063 , 0.2188} \right)$$ \end{document} . A, adenine; C, cytosine; CGR, chaos game representation; G, guanine; T, thymine.

FIG. 2.

The CGR graph of human mitochondrial genome (GenBank access no.: D38116).

Algorithm 1: Algorithm for Computing the CGR of a DNA Sequence
Input: A DNA sequence S of length n
Output: List of 2D coordinates of the DNA sequence,
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${p_i} \left( {x , y} \right) , i = 1 , 2 , \cdots , n$$ \end{document}
Step:
1. Create a square with four corners
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A = \left( {1 , 1} \right) , \;T = \left( { - 1 , 1} \right) , \;C = \left( { - 1 , - 1} \right)$$ \end{document} , and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$G = \left( {1 , - 1} \right)$$ \end{document} , representing the four nucleotides \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A , \;T , \;C$$ \end{document} , and G, respectively. These four points are denoted as CGR corners \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\alpha \in \left\{ {A , T , C , G} \right\} $$ \end{document} .
2. Initialize the first CGR coordinate based on the first nucleotide, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S \left( 1 \right)$$ \end{document} , of the DNA sequence.
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align} \ & { { p_ { 1 , x } } = \frac { 1 } { 2 } { \alpha _ { 1 , x } } } \\ & { { p_ { 1 , y } } = \frac { 1 } { 2 } { \alpha _ { 1 , y } } } \\ & { { \alpha _1 } = S \left( 1 \right) , { \alpha _1 } \in \left\{ { A , T , C , G } \right\}} \tag { 1 } \end{align} \end{document}
3. Compute the CGR coordinate of current nucleotide, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$S \left( i \right)$$ \end{document} , of the DNA sequence as the midpoint of previous coordinate and the CGR corner for this nucleotide.
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align} \ &{{p_ { i , x } } = \frac { 1 } { 2 } \left( { { p_ { i - 1 , x } } + { \alpha _ { i , x } } } \right) } \\ & { { p_ { i , y } } = \frac { 1 } { 2 } \left( { { p_ { i - 1 , y } } + { \alpha _ { i , y } } } \right) } \\ & { { \alpha _i } = S \left( i \right) , { \alpha _i } \in \left\{ { A , T , C , G } \right\} } \\ & { i = 2 , 3 , \ldots , n } \tag { 2 } \end{align} \end{document}

2.2. Encoding DNA sequences by iCGR

From the definition of CGR, we notice that the CGR coordinates of current nucleotide is determined by the CGR coordinates of the preceding nucleotide and the fixed CGR corner coordinates of the current nucleotide. According to this recursive relationship, we may get the final CGR coordinates of a DNA sequence. The CGR theorem suggests that the final coordinates contain the full DNA sequence information (Jeffrey, 1990). However, due to the floating-point errors in the computation of CGR, DNA sequences cannot be fully recovered by the final CGR coordinates. We hereto solve this lossless encoding and decoding problems that occur in the classical CGR representation.

To address the floating-point errors when encoding DNA sequences in the original CGR scheme, here we redefine a new CGR coordinate relationship as in Equations (3) and (4). Instead of taking the midpoint of the preceding position and the current CGR corner as in original CGR (Jeffrey, 1990), the current position of the new CGR schema is the sum of the preceding coordinate and exponential of two of the CGR corner [Eq. (4)]. As an example, the iCGR of a short DNA sequence, TAGCA, is illustrated in Figure 3. It should be noted that the proposed CGR mapping of DNA sequences is different from the original CGR. In the proposed CGR mapping, the coordinates of DNA sequences are integers and can extend all the 2D space, whereas regular CGR coordinates are float numbers and are limited to the unit square. Thus, we may consider that the proposed iCGR is an open mapping, and the original CGR is a closed mapping. Although the original CGR coordinates are determined by the DNA sequences from theoretical analysis, due to floating-point errors, the original CGR cannot recover a DNA sequence when the length of the sequence is longer than 32 bp. Our proposed CGR mapping results in integer coordinates without the floating-point errors; therefore, the iCGR can recover a full DNA sequence when the length of the sequence is <1024 bp. This is the significant advantage of our proposed iCGR mapping.

FIG. 3.

iCGR encoding the DNA sequence, TAGCA. The corresponding iCGR coordinates are: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${T_1} \left( { - 1 , 1} \right) , {A_2} \left( {1 , 3} \right) , {G_3} \left( {5 , - 1} \right) , {C_4} \left( { - 3 , - 9} \right) , {A_5} \left( {13 , 7} \right)$$ \end{document} . iCGR, integer chaos game representation.

We propose here an iCGR encoding algorithm for a DNA sequence. Using this algorithm, a DNA sequence can be uniquely represented by three numbers: the length of the sequence and the two integers of the final CGR coordinate of the DNA sequence. These integers contain all the DNA sequence information and can recover the sequence reversely. Encoding a DNA sequence into three integers by iCGR is as follows [Eq. (3)] and (Algorithm 2). We first initialize the CGR coordinate at the first position of a DNA sequence using the CGR corner coordinate, and then the following CGR coordinate is computed based on the preceding coordinate and the nucleotide at this position. \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \begin{matrix} {{p_{1 , x}} = { \alpha _{1 , x}}} \hfill \\ {{p_{1 , y}} = { \alpha _{1 , y}}} \hfill \\ {{ \alpha _1} = S \left( 1 \right) , { \alpha _1} \in \left\{ {A , T , C , G} \right\} } \hfill \\ {} \hfill \\ \end{matrix}. \tag{3} \end{align*} \end{document}

Algorithm 2: Encoding a DNA Sequence by Tri-Integers \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n , X , Y} \right)$$ \end{document}
Input: A DNA sequence S of length n
Output: Tri-integers \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n , X , Y} \right)$$ \end{document} representing the DNA sequence
Step:
1. Get the nucleotide coordinates \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \alpha _{1 , x}} , { \alpha _{1 , y}}$$ \end{document} at position 1 based on Equation (3).
2. Compute the x-coordinate at position i from that at position \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$i - 1$$ \end{document} : \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${p_{i , x}} = {p_{i - 1 , x}} + {2^{i - 1}}{ \alpha _{i , x}}$$ \end{document} .
3. Compute the x-coordinate at position i from that at position \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$i - 1$$ \end{document} : \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${p_{i , y}} = {p_{i - 1 , y}} + {2^{i - 1}}{ \alpha _{i , y}}$$ \end{document} .
4. Repeat steps 2 and 3 until \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$i = n$$ \end{document} .
5. When \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$i = n$$ \end{document} , return \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$X = {p_{n , x}}$$ \end{document} , \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Y = {p_{n , y}}$$ \end{document} .

Then we can get all the current iCGR coordinates at position i based on the preceding coordinate at position \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$i - 1$$ \end{document} and the nucleotide at position i. \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \begin{matrix} {{p_{i , x}} = {p_{i - 1 , x}} + {2^{i - 1}}{ \alpha _{i , x}}} \hfill \\ {{p_{i , y}} = {p_{i - 1 , y}} + {2^{i - 1}}{ \alpha _{i , y}}} \hfill \\ {{a_i} = S \left( i \right) , {a_i} \in \left\{ {A , T , C , G} \right\} } \hfill \\ {i = 2 , \ldots , n} \hfill \\ {} \hfill \\ \end{matrix}. \tag{4} \end{align*} \end{document}

From the recursive relation [Eq. (4)], we may prove that the iCGR coordinates are the sum of the product of position exponents and nucleotide types [Eq. (5)]. When a DNA sequence of length n is finally encoded by the three integer numbers \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n , {p_{n , x}} , {p_{n , x}}} \right)$$ \end{document} (tri-integers) through the iCGR, these three integers reflect the accumulative distribution of nucleotides along the sequence. Because the final encoding tri-integers hold all the sequence information, we propose to use the encoding tri-integers as the signature of a DNA sequence. \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \begin{matrix} {{p_{n , x}} = \mathop \sum \limits_{i = 1}^n { \rm{ }}{2^{i - 1}}{ \alpha _{i , x}}} \hfill \\ {{p_{n , y}} = \mathop \sum \limits_{i = 1}^n { \rm{ }}{2^{i - 1}}{ \alpha _{i , y}}} \hfill \\ {{ \alpha _i} = S \left( i \right) } \hfill \\ {i = 1 , 2 , \cdots , n} \hfill \\ {} \hfill \\ \end{matrix}. \tag{5} \end{align*} \end{document}

2.3. Integer decoding DNA sequences

We can prove that the sign of p_i is the same as that of nucleotide \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \alpha _i}$$ \end{document} . Therefore, the iCGR coordinates can be used to determine the corresponding nucleotide types. The nucleotide at position i can be determined based on the iCGR coordinate at this position \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$p \left( {{x_i} , {y_i}} \right)$$ \end{document} using the properties as in Equations (6) and (7). This can lead to the full recovery of original sequence from the final tri-integers \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n , \;X , \;Y} \right)$$ \end{document} .

We have the following theorem on integer encoding DNA sequences.

Theorem 2.1. When a DNA sequence of length n is encoded by the CGR coordinates \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {X , \;Y} \right)$$ \end{document} , the sequence information can be fully recovered from tri-integers \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n , \;X , \;Y} \right)$$ \end{document} .

After a DNA sequence of length n is encoded recursively by the iCGR method, then the sequence can be represented by the encoding integers \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n , \;X , \;Y} \right)$$ \end{document} of the last step of iCGR encoding. In the tri-integers \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n , X , Y} \right)$$ \end{document} that a DNA sequence of length n is encoded by the iCGR method, X is the x coordinate of iCGR at position n and Y is the y coordinate of iCGR at position n. Thus we can decode and recover the original DNA sequence from these tri-integers \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n , X , Y} \right)$$ \end{document} . The first step in the decoding process is to determine the nucleotide \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \alpha _n}$$ \end{document} at the last position n. From Equation (6), we may determine the nucleotide \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \alpha _n}$$ \end{document} . For example, if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$X = - 19 , \;Y = - 25$$ \end{document} , then the nucleotide at n is A. Then we can recover the second last coordinate \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {{p_{n - 1 , x}} , {p_{n - 1 , y}}} \right)$$ \end{document} from the last coordinate \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {{x_n} , {y_n}} \right)$$ \end{document} and the vertex coordinate of last nucleotide \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \alpha _n}$$ \end{document} [Eq. (7)]. After we get \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {{p_{n - 1 , x}} , {p_{n - 1 , y}}} \right)$$ \end{document} , we may determine the nucleotide \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \alpha _{n - 1}}$$ \end{document} at position \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n - 1$$ \end{document} from \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {{p_{n - 1 , x}} , {p_{n - 1 , y}}} \right)$$ \end{document} by Equation (6). Using this method, all the nucleotides at positions \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$i = n - 1 , \;n - 2 , \ldots , 1$$ \end{document} can be recursively determined.

By this encoding method, we can see that any DNA sequences that end with nucleotide A are encoded by two large integers in Quadrant I, those end with nucleotide T are in Quadrant II, those end with nucleotide C are in Quadrant III, and those end with nucleotide G are in Quadrant IV. From the locations of the sequences, we can determine the type of the last nucleotide of the sequences.

After a DNA sequence is encoded into tri-integers by the iCGR scheme, the sequence can be fully recovered from the tri-integers. To recover the DNA sequence from encoded tri-integers \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n , \;X , \;Y} \right)$$ \end{document} , we can first determine the last nucleotide according to Equation (6). Since the CGR corner coordinate \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \alpha _n}$$ \end{document} is known, we can use the following induction to obtain the CGR coordinate of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n - 1$$ \end{document} position, and then determine the nucleotide by Equation (7). Using the iteration process, all the nucleotides at all the positions, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n - 1 , n - 2 , \ldots .1$$ \end{document} , can be determined (Algorithm 3).

Algorithm 3: Decoding a DNA Sequence from Tri-Integers \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n , X , Y} \right)$$ \end{document}
Input: Tri-integers \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n , X , Y} \right)$$ \end{document}
Output: The DNA sequence that is encoded by tri-integers \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n , X , Y} \right)$$ \end{document}
Step:
1. Get the nucleotide \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \alpha _n}$$ \end{document} at position n from \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n , X , Y} \right)$$ \end{document} based on Equation (3).
2. Compute the x-coordinate at position \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$i - 1$$ \end{document} from that at position i: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${p_{i - 1 , x}} = {p_{i , x}} - {2^{i - 1}}{ \alpha _{i , x}}$$ \end{document} .
3. Compute the y-coordinate at position \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$i - 1$$ \end{document} from that at position i: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${p_{i - 1 , y}} = {p_{i , y}} - {2^{i - 1}}{ \alpha _{i , y}}$$ \end{document} .
4. Get the nucleotide \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \alpha _{i - 1}}$$ \end{document} at position \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$i - 1$$ \end{document} from \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${p_{i - 1 , x}} , {p_{i - 1 , y}}$$ \end{document} based on Equation (3).
5. Repeat steps 2, 3, and 4 until \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$i = 1$$ \end{document} .
6. Return the decoded nucleotide sequence of length n.

The tri-integers can also detect single nucleotide mutation in a DNA sequence. For example, the mutation from A to T in a DNA sequence, of which the wild-type sequence is represented by tri-integer \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n , X , Y} \right)$$ \end{document} , the mutation generates new tri-integers \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n , \;{X_m} , \;{Y_m}} \right)$$ \end{document} . The difference of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n , X , Y} \right)$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n , {X_m} , {Y_m}} \right)$$ \end{document} can determine the single nucleotide mutation.

It is noted that the encoding scheme can detect an error if the given tri-integers are not for a DNA sequence. In each step of decoding, the value of each nucleotide can be recovered. If the values are not 1/-1 pairs, then the given tri-integers are not for a DNA sequence. Therefore, when DNA sequences are encoded by the proposed iCGR, if there is an error during data storage and transfer, the iCGR encoding and decoding method can detect this error at the location. \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \begin{matrix} {{p_{i - 1 , x}} = {p_{i , x}} - {2^i}{ \alpha _{i , x}}} \hfill \\ {{p_{i - 1 , y}} = {p_{i , y}} - {2^i}{ \alpha _{i , y}}} \hfill \\ {i = 2 , \ldots , n} \hfill \\ {} \hfill \\ \end{matrix}. \tag{7} \end{align*} \end{document}

3. Results

In the encoding and decoding algorithms, we consider two classes of four different bases in DNA, the pyrimidines [cytosine (C) and thymine (T)], and the purines [adenine (A) and guanine (G)], and design new CGR corners. The algorithms use integer iteration so the relationship between nucleotide positions and encoding integers are one-to-one. We perform case studies for evaluating the effectiveness of the integer encoding and decoding algorithms in sequence representation and compression.

An example of encoding a short DNA sequence of length 10 bp is illustrated in Table 1. Table 1 shows the encoded \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${p_{i , x}}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${p_{i , y}}$$ \end{document} at each position i. The two large integers in the final step for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n = 10$$ \end{document} are −203 and 441. The DNA sequence can be encoded and stored by these integers, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n = 10 , X = - 203 , Y = 441} \right)$$ \end{document} .

Table 1.

Encoding a DNA Sequence of Length 10 by Tri-Integers \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n , X , Y} \right)$$ \end{document}

DNA	C	G	T	A	A	C	T	A	G	T
i	1	2	3	4	5	6	7	8	9	10
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \alpha _{i , x}}$$ \end{document}	−1	1	−1	1	1	−1	−1	1	1	−1
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \alpha _{i , y}}$$ \end{document}	−1	−1	1	1	1	−1	1	1	−1	1
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${p_{i , x}}$$ \end{document}	−1	1	−3	5	21	−11	−75	53	309	−203
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${p_{i , y}}$$ \end{document}	−1	−3	1	9	25	−7	57	185	−71	441

A, adenine; C, cytosine; G, guanine; T, thymine.

An example of decoding a DNA sequence is illustrated in Table 2. Table 2 shows the encoded integers \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${p_{i , x}}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${p_{i , y}}$$ \end{document} and decoded nucleotide at each position i. The tri-integers \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n = 10 , X = 659 , Y = 783} \right)$$ \end{document} are used for recovering the full sequence. The DNA sequence recovered by the tri-integers is “ATTGCCGTAA.”

Table 2.

Decoding a DNA Sequence from Tri-Integers \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {n = 10 , X = 659 , Y = 783} \right)$$ \end{document}

i	10	9	8	7	6	5	4	3	2	1
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${p_{i , x}}$$ \end{document}	659	147	−109	19	−45	−13	3	−5	−1	1
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${p_{i , y}}$$ \end{document}	783	271	15	−113	−49	−17	−1	7	3	1
Nucleotide	A	A	T	G	C	C	G	T	T	A

Another example of encoding is for encoding Homo sapiens globin gene (GenBank access no.: HF583935). For each position of the sequence, we generate the encoding iCGR coordinates as shown in Figure 4. The final encoding tri-integers for this gene are (171, 2050339409081302816541928568690764733194931295596027, 1119453162673286728512143679440023858905057236646823).

FIG. 4.

Integer encoding Homo sapiens globin gene (GenBank access no.: HF583935).

Using the encoding method, the average bits of the tri-integers per nucleotide is 2.0, whereas symbolic DNA sequences need 8 bits per nucleotide. For example, the total bits of the tri-integers for the Homo sapiens globin gene are 349 bits, each nucleotide needs 2.041 bits. Therefore, encoding DNA sequences as the tri-integers may save storage space.

4. Conclusions

We present a novel method for encoding a DNA sequence into three integers. Encoding a DNA sequence by iCGR produces unique tri-integers that contain all sequence information. Therefore, the tri-integers from encoding a DNA sequence can be considered as the mathematical descriptor of the sequence. The encoding method can be a promising tool for DNA sequence compressions, encryption, and steganography.

Footnotes

Acknowledgment

We are grateful to Professor Jiasong Wang at the Department of Mathematics, Nanjing University for helpful discussion.

Author Disclosure Statement

The author declares that no competing financial interests exist.

References

Almeida

J.S.

, Carrico

J.A.

, Maretzek

, et al. 2001. Analysis of genomic sequences by chaos game representation. Bioinformatics. 17, 429–437.

Anastassiou

2000. Frequency-domain analysis of biomolecular sequences. Bioinformatics. 16, 1073–1081.

Deschavanne

P.J.

, Giron

, Vilain

, et al. 1999. Genomic signature: Characterization and classification of species assessed by chaos game representation of sequences. Mol. Biol. Evol. 16, 1391–1399.

Felsenstein

, Sawyer

, and Kochin

1982. An efficient method for matching nucleic acid sequences. Nucleic Acids Res. 10, 133–139.

Hoang

, Yin

, and Yau

S.S.T.

2016. Numerical encoding of DNA sequences by chaos game representation with application in similarity comparison. Genomics. 108, 134–142.

Jeffrey

H.J.

1990. Chaos game representation of gene structure. Nucleic Acids Res. 18, 2163–2170.

Joseph

, and Sasikumar

2006. Chaos game representation for comparison of whole genomes. BMC Bioinformatics. 7, 243.

Kari

, Hill

K.A.

, Sayem

A.S.

, et al. 2015. Mapping the space of genomic signatures. PLoS One. 10, e0119815.

Mendizabal-Ruiz

, Román-Godínez

, Torres-Ramos

, et al. 2017. On DNA numerical representations for genomic similarity computation. PLoS One. 12, e0173288.

10.

Messaoudi

, Elloumi-Oueslati

, and Lachiri

2014. Building specific signals from frequency chaos game and revealing periodicities using a smoothed Fourier analysis. IEEE/ACM Trans. Comput. Biol. Bioinform. 11, 863–877.

11.

Stan

, Cristescu

C.P.

, et al. 2010. Similarity analysis for DNA sequences based on chaos game representation. case study: The albumin. J. Theor. Biol. 267, 513–518.

12.

Voss

R.F.

1992. Evolution of long-range fractal correlations and 1/f noise in DNA base sequences. Phys. Rev. Lett. 68, 3805–3808.

13.

Yin

, and Wang

2016. Periodic power spectrum with applications in detection of latent periodicities in DNA sequences. J. Math. Biol. 73, 1053–1079.

14.

Yin

, and Yau

S.S.T.

2005. A Fourier characteristic of coding sequences: Origins and a non-Fourier approximation. J. Comput. Biol. 12, 1153–1165.

15.

Yin

, and Yau

S.S.T.

2008. Numerical representation of DNA sequences based on genetic code context and its applications in periodicity analysis of genomes. In: 2008 IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, Sun Valley, ID, 2008. CIBCB'08. pp. 223–227.

16.

Yin

, Yin

X.E.

, and Wang

2014. A novel method for comparative analysis of DNA sequences by Ramanujan-Fourier transform. J. Comput. Biol. 21, 867–879.