Reversible DNA codes over a family of non-chain rings

arXiv:1711.02385v1 [math.CO] 7 Nov 2017

Fatmanur Gursoy1 , Elif Segah Oztas2 , Ayten Ozkan1
1
2

Department of Mathematics, Yildiz Technical University, Turkey

Department of Mathematics, Karamanoglu Mehmetbey University, Turkey

(fatmanur@yildiz.edu.tr, elifsegahoztas@gmail.com, uayten@yildiz.edu.tr )

November 8, 2017
Abstract
In this work we extend results introduced in [15]. Especially, we solve the reversibility problem
for DNA codes over the non chain ring Rk,s = F42k [u1 , . . . , us ]/hu21 − u1 , . . . , u2s − us i. We define
an automorphism θ over Rk,s which helps us both finding the idempotent decomposition of Rk,s
and solving the reversibility problem via skew cyclic codes. Moreover, we introduce a generalized
Gray map that preserves DNA reversibility.
Keywords: Skew Cyclic Codes, DNA Codes, Gray Map, Reversible Codes, DNA k-bases.
2010 Mathematics Subject Classification: 94B15, 94B05, 92D20.

1

Introduction

DNA sequences consist of four bases (nucleotides) which are Adenine (A), Guanine (G), Cytosine (C)
and Thymine (T). Those bases are lined up by the rule Watson-Crick complement (WCC). WCC
ensures that A pairs with T (Ac = T , T c = A) and C pairs with G (C c = G, Gc = C). The attention
into DNA structure and functional properties is attracted by solving a computationally hard (NP)
problem using DNA molecules [3]. With this study, DNA has started to use as an computational tool.
For example; in [4] and [7], authors used DNA to break the Data Encryption System. Also, because
of its natural error correcting structure, DNA has found many applications in coding theory. DNA
single basis( [2, 13, 27, 28]), double bases ([5, 14, 22, 30]), and multiple bases ([6, 16, 23, 24, 25])
over various fields and recently rings have been studied by applying different constraints especially,
Hamming distance constraint. In each case, the reversibility problem has been solved by different
methods.
The reversibility problem while working with sets more than four elements explained by the following example: Let R1,1 be the ring F42 [u1 ]/hu21 −u1 i which has 162 = 44 elements. To make a correspondence between the elements of R1,1 and DNA multiple bases, we need to map each element to a DNA
4-bases. Let (α1 , α2 , α3 ) be a codeword over R1,1 corresponding to ATTCGAACTCCG (a 12-string)
where α1 →ATTC, α2 →GAAC, α3 →TCCG and α1 , α2 , α3 ∈ R1,1 . The reverse of (α1 , α2 , α3 ) is
(α3 , α2 , α1 ), and (α3 , α2 , α1 ) corresponds to TCCGGAACATTC. However, TCCGGAACATTC is not
the reverse of ATTCGAACTCCG. Indeed, the reverse of ATTCGAACTCCG is GCCTCAAGCTTA.
So, basically reversing the entires in the codeword does not lead directly to the reverse of DNA alphabets in general except single alphabet matching.

1

In this study, we focus on extending the problem introduced in [15] and study reversible DNA codes
over Rk,s = F42k [u1 , . . . , us ]/hu21 − u1 , . . . , u2s − us i where ui uj = uj ui . To make a correspondence
between DNA alphabet and the ring Rk,s , we map each ring element to a DNA 2s+1 k-basis (2s+1 kmer). We establish a generalized Gray map that preserves DNA reversibility. Moreover, we obtain
reversible DNA codes by using skew cyclic codes over Rk,s .
The reason of considering the DNA k-bases (k-mers) is that components related to DNA, such as
transcription factor, binding site, genes, proteins etc., are consist of k-bases. DNA researchers focus
on finding the role of the specific k-bases. For example, in [20], the DNA 8-bases (8-mers) are listed
from special areas including binding sites that have important role in opening/closing the genes for
producing proteins. In [20] (Table 6), the frequencies of 8-mers are listed and the top area of the lists
are important to identify binding sites where reversible-complement DNA 8-mers have been shown
to appear intensively. Moreover, finding meaning paths in DNA by using the algebraic codes is an
interesting question for researchers.

2

Preliminaries and definitions

In this section we give basic definition of skew cyclic codes and reversible codes and we introduce
skew cyclic codes over Rk,s . Skew cyclic codes were first introduced by Boucher et al. in [8]. They
generalized cyclic codes by using skew polynomial rings with an automorphism θ over the finite field
with q elements (Fq ). The definition of skew polynomial rings is given below.
Definition 1. [18] Let R be a commutative ring with identity and θ be an automorphism over R. The
set of polynomials R[x; θ] = {a0 + a1 x + ... + an−1 xn−1 |ai ∈ R, n ∈ N} is called the skew polynomial
ring over R where addition is the usual addition of polynomials and the multiplication is defined by
xa = θ(a)x (a ∈ R) and extended to polynomial multiplication naturally.
A skew cyclic code is defined to be a linear code C of length n over Fq satisfying the property
σ(c) = (θ(cn−1 ), θ(c0 ), ..., θ(cn−2 )) ∈ C, for all c = (c0 , c1 , ..., cn−1 ) ∈ C [8]. In skew polynomial
representation of C, we can consider a codeword c = (c0 , c1 , ..., cn−1 ) of C as a polynomial c(x) =
c0 + c1 x + . . . + cn−1 xn−1 ∈ Fq [x; θ]. In this case σ(c) corresponds to the polynomial xc(x) in Fq [x; θ].
If the order of θ, say m, divides n then C corresponds to a left ideal of the quotient ring Fq [x; θ]/(xn −1)
(in [8]), else Fq [x; θ]/(xn − 1) is not a ring anymore but we can consider C as a left Fq [x; θ]−submodule
of Fq [x; θ]/(xn − 1) (in [26]). In both cases C is principally generated by a monic polynomial g(x)
which is a right divisor of xn − 1 in Fq [x; θ]. One of the attractive features of studying skew cyclic codes
is that, factorization of xn − 1 is not unique in Fq [x; θ], so we have much more generating polynomials
in contrast with cyclic codes. Thanks to their rich algebraic structure, many new good codes with
parameters exceeding the parameters of the previously best known linear codes have been obtained
in both [8] and [1]. There are many other studies done by considering skew polynomial rings over
different rings instead of finite fields, such as skew cyclic codes over Galois rings ([9]), finite chain rings
([19]), non-chain rings such as Fq + vFq ([17]) and Fq + uFq + vFq + uvFq ([29]).
In this paper, we study a family of rings Rk,s = F42k [u1 , . . . , us ]/hu21 − u1 , . . . , u2s − us i, where
k, s > 1 and ui uj = uj ui . Rk,s is a commutative non-chain ring with characteristic 2 and cardinality
s
s+1
42k2 = 42 k .

2

We use the following automorphism to define skew cyclic codes over Rk,s . Let
θ :Rk,s −→ Rk,s
k

a −→ a4 ∀a ∈ F42k ,
ui −→ ui + 1 ∀i ∈ {1, . . . , s}.
Then θ is an automorphism over Rk,s of order 2. Naturally Rk,s [x; θ] is a skew polynomial ring and a
skew cyclic code C of length n over Rk,s corresponds to a left Rk,s [x; θ]-submodule of Rk,s [x; θ]/(xn −1).
Whenever g(x) is a right divisor of xn − 1 in Rk,s , the left Rk,s [x; θ]-submodule C = (g(x)) is a skew
cyclic code over Rk,s . But not all skew cyclic codes over Rk,s are principally generated. In this study
we focus on only principally generated ones. The factorization of xn − 1 is not unique in Rk,s [x; θ],
since F42k [x; θ] is a subring of Rk,s [x; θ] and the factorization of xn − 1 is not unique in F42k [x; θ]. So,
there are many different right divisors of xn − 1. This algebraic property provides us an advantage for
finding right divisors with special properties (palindromic and θ−palindromic) in Section 4.
Definition 2. Let C be a code of length n over Fq . If cr = (cn−1 , cn−2 , . . . , c1 , c0 ) ∈ C for all
c = (c0 , c1 , . . . , cn−1 ) ∈ C, then C is called a reversible code.

3

Decomposition of Rk,s

In this section, we introduce a method to find idempotent decomposition of the ring Rk,s . By using
the decomposition of Rk,s we define a Gray map which preserves DNA reversibility.
Our aim is to establish a correspondence between the elements of Rk,s and DNA 2s+1 k-bases in such
a way that the reversibility problem is solved by using skew cyclic codes over Rk,s . First of all we need
to express the elements of Rk,s in a unique way. Let us arrange the elements of the form ur11 ur22 . . . urss
in an order. Let A be the set of such elements, i.e. A = {ur11 ur22 . . . urss |ri ∈ {0, 1}, 1 ≤ i ≤ s}. The
cardinality of A is 2s . Define a map
µ : A −→ Zs
ur11 ur22 . . . urss −→ (r1 , r2 , . . . , rs ).
There are several ways of ordering s-tuples (r1 , r2 , . . . , rs ). We will use the lexicographic order.
Definition 3 ([12]). Let α = (α1 , α2 , . . . , αs ) and β = (β1 , β2 , . . . , βs ) be in Zs>0 . If the leftmost
nonzero entry of the vector difference α − β ∈ Zs is positive then α is greater than β with respect to the
β1 β2
αs
βs
1 α2
lexicographic order, and denote it α >lex β. We write uα
1 u2 . . . us >lex u1 u2 . . . us if α >lex β.
For example; let us put u1 , u2 ∈ R1,3 in order. Since µ(u1 ) = (1, 0, 0), µ(u2 ) = (0, 1, 0) and
(1, 0, 0) − (0, 1, 0) = (1, −1, 0) then u1 >lex u2 .
Here, we rename the elements of Rk,s of the form ur11 ur22 . . . urss where ri ∈ 0, 1 and 1 ≤ i ≤ s, as
follows:
1. First consider the following specific subsets of A;
Aj = {ur11 ur22 . . . urss |exactly j of ri ’s equal 1 the others 0}
where 0 ≤ j ≤ s. So, A0 = {1}, A1 = {u1 , u2 , . . . , us }, A2 = {u1 u2 , u2 u3 . . . , us−1 us }, As =
{u1 u2 . . . us }, etc.
3

2. Arrange the elements of Aj with respect to the lexicographic order, and let Bj be the array
consisting the ordered elements of Aj . For example B0 = [1], B1 = [u1 , . . . , us ], etc.
3. Then concatenate these arrays as B = [B0 , B1 , . . . , Bs ].
4. Rename the ith element of the array B as Ui . For instance, U0 = 1, U1 = u1 , U2s −1 = u1 u2 . . . us
etc.
Define the ordered s-tuples of Rk,s as
T = [µ(U0 ), µ(U1 ), . . . , µ(U2s −1 )] = [T0 , T1 , . . . , T2s −1 ].

(1)

Note that; µ(Ui ) + µ(U2s −1−i ) = Ti + T2s −1−i = (1, 1, . . . , 1) , for 0 ≤ i ≤ 2s − 1.
Example 1. Let us consider the ring R1,3 = F16 [u1 , u2 , u3 ]/hu21 − u1 , u22 − u2 , u23 − u3 i. Then A =
{1, u1, u2 , u3 , u2 u3 , u1 u3 , u1 u2 , u1 u2 u3 } and
B0 = [1], B1 = [u1 , u2 , u3 ],
B2 = [u1 u2 , u1 u3 , u2 u3 ], B3 = [u1 u2 u3 ].
So, B = [1, u1 , u2 , u3 , u1 u2 , u1 u3 , u2 u3 , u1 u2 u3 ] = [U0 , U1 , . . . , U7 ] and the ordered 3 − tuples of R1,3 is;
T = [T0 , . . . , T7 ] = [(0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 0), (1, 0, 1), (0, 1, 1), (1, 1, 1)]. Any element
α ∈ R1,3 can be written uniquely of the form α = a0 U0 + a1 U1 + . . . a7 U7 where αi ∈ F16 . Moreover,
it can be easily seen that Ti + T7−i = (1, 1, 1), for example;
T0 + T7 = µ(U0 ) + µ(U7 ) = µ(1) + µ(u1 u2 u3 ) = (0, 0, 0) + (1, 1, 1) = (1, 1, 1),
T3 + T4 = µ(U3 ) + µ(U4 ) = µ(u3 ) + µ(u1 u2 ) = (0, 0, 1) + (1, 1, 0) = (1, 1, 1).
The following theorem is a result of the Chinese Remainder Theorem;
Theorem 1. Let I = {Ii } be a set of 2s elements of Rk,s . If
(i) Ii2 = Ii ,
(ii) Ii Ij = 0 for i 6= j and 0 ≤ i, j ≤ 2s − 1,
P2s −1
(iii)
i=0 Ii = 1,
then Rk,s = I0 F42k ⊕ I1 F42k ⊕ . . . ⊕ I2s −1 F42k .
Now we construct an idempotent set I satisfying these three conditions above. We associate
some elements of Rk,s with the s-tuple Ti ’s as follows. Let Ti = (r1 , r2 , . . . , rs ). Then define Ii =
θr1 (u1 )θr2 (u2 ) . . . θrs (us ). For example; since T0 = (0, 0, 0, . . . , 0), T1 = (1, 0, 0, . . . , 0) and T2 =
(0, 1, 0, . . . , 0) we have I0 = u1 u2 . . . us , I1 = (u1 + 1)u2 . . . us and I2 = u1 (u2 + 1)u3 . . . us .
Theorem 2. Let I = {Ii = θr1 (u1 )θr2 (u2 ) . . . θrs (us )| Ti = (r1 , r2 , . . . , rs ), 0 ≤ i ≤ 2s − 1}. Then
Rk,s = I0 F42k ⊕ I1 F42k ⊕ . . . ⊕ I2s −1 F42k .

4

Proof. (i) Ii2 = Ii .
Each Ii has the form (uj1 + 1) . . . (ujd + 1)ujd +1 . . . ujs , where {j1 , j2 , . . . , js } = {1, 2, . . . , s}. Since
(uje + 1)2 = (uje + 1) and u2jf = ujf , then Ii2 = Ii .
(ii) Ii Ij = 0 for i 6= j.
Let
Ii = θr1 (u1 )θr2 (u2 ) . . . θrs (us ) → Ti = (r1 , r2 , . . . , rs ),
Ij = θm1 (u1 )θm2 (u2 ) . . . θms (us ) → Tj = (m1 , m2 , . . . , ms ).
Since i 6= j, then Ti and Tj are distinct so, at least one coordinate re 6= me . Without loss of generality,
we may assume that re = 0 and me = 1. Then θre (ue ) = ue and θme (ue ) = ue +1. Since ue (ue +1) = 0,
we have Ii Ij = 0.
P2s −1
(iii) i=0 Ii = 1.
P j −1
The proof is by induction. For s = 0, I0 = 1. Suppose the induction hypothesis 2i=0
Ii = 1
is true for all 0 < j < l. Let us look at the case s = l. Exactly half of the elements of the set
I = {I0 , I1 , . . . , I2l −1 } have ul as a factor and the others have (ul + 1) as another factor.
If we take the subset of I which has idempotents with the factor ul , and delete ul from each
element then we have the idempotent set of Rk,l−1 , say {V0 , V1 , . . . , V2l−1 −1 } thus by induction we
P2l−1 −1
Vi = 1.
have i=0
If we take the subset of I which has idempotents with the factor (ul + 1) , and delete (ul + 1) from
each element then we have the idempotent set of Rk,l−1 , again.
So,
l
2X
−1

i=0

Ii = ul

2l−1
X−1

Vi + (ul + 1)

2l−1
X−1

Vi

i=0

i=0

= ul + (ul + 1) = 1.

Example 2. Let us determine the idempotent set I for the ring R1,3 , given in Example 1. Since
T = [T0 , . . . , T7 ] = [(0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 0), (1, 0, 1), (0, 1, 1), (1, 1, 1)], we have
I0 = u1 u2 u3 ,
I1 = (u1 + 1)u2 u3 ,
I2 = u1 (u2 + 1)u3 ,
I3 = u1 u2 (u3 + 1),
I4 = (u1 + 1)(u2 + 1)u3 ,
I5 = (u1 + 1)u2 (u3 + 1),
I6 = u1 (u2 + 1)(u3 + 1),
I7 = (u1 + 1)(u2 + 1)(u3 + 1).
By using the decomposition of Rk,s in Theorem 2, each element α ∈ Rk,s can uniquely be expressed
as α = α0 I0 + α1 I1 + . . . + α2s −1 I2s −1 , where α0 , α1 , . . . , α2s −1 ∈ F42k . By using this expression we

5

define the following Gray map:
s

ϕ : Rk,s −→ F422k
α −→ (α0 , α1 , . . . , α2s −1 ).
This Gray map is a one-to-one and onto map and can naturally be extended to n-tuples coordinatewise. The following propositon allows us to determine the Gray image of an element of the
form α = b0 U0 + b1 U1 + . . . + b2s −1 U2s −1 . The dot product “·” below denotes the componentwise
multiplication of two vectors, for example, (0, 1, 0) · (1, 0, 0) = (0, 0, 0).
Proposition 1. Let α = b0 U0 + b1 U1 + . . . + b2s −1 U2s −1 ∈ Rk,s where bi ∈ F42k for 0 ≤ i ≤ 2s − 1.
Then ϕ(α) = (α0 , α1 , . . . , α2s −1 ) and
X
bj where 0 ≤ j ≤ 2s − 1 and j satisfies Ti · Tj = (0, 0, . . . , 0).
αi =
j

Proof. Let ϕ(α) = (α0 , α1 , . . . , α2s −1 ). Then α = α0 I0 + α1 I1 + . . . + α2s −1 I2s −1 . Multiplying α by Ii
we have
Ii α = αi Ii = Ii (b0 U0 + b1 U1 + . . . + b2s −1 U2s −1 )
→ αi Ii = b0 U0 Ii + b1 U1 Ii + . . . + b2s −1 U2s −1 Ii
since Ii Ij = 0 for i 6= j. Now let us determine Uj Ii . Let the ordered s-tuple of Ii be Ti = (r1 , r2 , . . . , rs )
and the ordered s-tuple of Uj be Tj = (e1 , e2 , . . . , es ). If rk = ek = 1 for some k ∈ {1, 2, . . . , s} then,
Ii has (uk + 1) as a factor and Uj has uk then Uj Ii = 0. This means bj does not appear in the result
of Ii α. Otherwise, if either rk = ek = 0 or rk 6= ek for all k ∈ {1, 2, . . . , s} then Uj Ii 6= 0 so bj appears
in the result of Ii α. Whenever rkP
= ek = 0 or rk 6= ek for all k ∈ {1, 2, . . . , s}, Ti Tj = (0, 0, . . . , 0).
Hence we can conclude that αi = bj where 0 ≤ j ≤ 2s − 1 and j satisfies Ti · Tj = (0, 0, . . . , 0).

4

Reversible DNA codes over Rk,s

In this section we obtain reversible DNA codes from skew cyclic codes over Rk,s by making use of the
Gray map defined in the previous section.
In [23], Oztas and Siap gave a correspondence between the elements of the field F42k and DNA
k
2k−bases. In order to solve the reversibility problem they mapped each β and β 4 ∈ F42k to the DNA
2k−bases that are reverses of each other. They gave an algorithm to do this mapping. Let us call
s
this map with τ . τ can naturally be extended to a map τ2 from F422k to DNA 2s+1 k- bases as follows;
τ2 (α0 , α1 , . . . , α2s −1 ) = (τ (α0 ), τ (α1 ), . . . , τ (α2s −1 )), where αi ∈ F42k , 0 ≤ i ≤ 2s − 1.
k
In our study β 4 = θ(β) for β ∈ F42k , thus τ (β) and τ (θ(β)) are reverses of each other. Briefly, we
say that β and θ(β) are DNA-reverses of each other.
Let α ∈ Rk,s and ϕ(α) = (α0 , α1 , . . . , α2s −1 ). The corresponding DNA 2s+1 k-bases of α is
τ2 (α0 , α1 , . . . , α2s −1 ) = (τ (α0 ), τ (α1 ), . . . , τ (α2s −1 )) and its reverse is (τ (θ(α2s −1 )), τ (θ(α2s −2 )), . . . , τ (θ(α0 )))
In short, we say (α0 , α1 , . . . , α2s −1 ) and (θ(α2s −1 ), θ(α2s −2 ), . . . , θ(α0 )) are DNA reverses of each other.
Lemma 1. θ(Ij ) = I2s −1−j for all j ∈ {0, 1, . . . , 2s − 1}.
Proof. Let Tj = (r1 , r2 , . . . , rs ). Since Tj +T2s −1−j = (1, 1, . . . , 1), then T2s −1−j = (1−r1 , 1−r2 , . . . , 1−
rs ). Since ri ’s are either 0 or 1 and the order of θ is 2, then θri = θ−ri .
Ij = θr1 (u1 )θr2 (u2 ) . . . θrs (us ) ⇒ θ(Ij ) = θ1−r1 (u1 )θ1−r2 (u2 ) . . . θ1−rs (us ) = I2s −1−j .
6

Following theorem leads us to solve the reversibility problem directly by skew cyclic codes and it
shows that the Gray map ϕ preserves the DNA reversibility.
Theorem 3. Let α ∈ Rk,s . Then the DNA reverse of ϕ(α) is ϕ(θ(α)).
Proof. Let α = α0 I0 + α1 I1 + . . . + α2s −1 I2s −1 . Then ϕ(α) = (α0 , α1 , . . . , α2s −1 ), and
θ(α) = θ(α0 )θ(I0 ) + θ(α1 )θ(I1 ) + . . . + θ(α2s −1 )θ(I2s −1 )
= θ(α0 )I2s −1 + θ(α1 )I2s −2 + . . . + θ(α2s −1 )I0
= θ(α2s −1 )I0 + θ(α2s −2 )I1 + . . . + θ(α0 )I2s −1 .
Thus ϕ(θ(α)) = (θ(α2s −1 ), θ(α2s −2 ), . . . , θ(α0 )) which is exactly the DNA reverse of ϕ(α).
Example 3. In [22], Table-1 gives a correspondence between the elements of F16 and DNA 2-bases.
It has similar properties with the correspondence algorithm given in [23]. Table-1 maps each element
of F16 and its fourth power to the DNA 2-bases that are reverses of each other.
Consider the ring R1,3 , given in Example 1. Let β be a primitive element of F16 and α = β 2 I0 +
βI1 + β 5 I2 + β 3 I3 + I4 + 0I5 + β 7 I6 + I7 ∈ R1,3 . Then, ϕ(α) = (β 2 , β, β 5 , β 3 , 1, 0, β 7 , 1). Using Table-1
given in [22], the corresponding DNA 16-bases is
τ2 (β 2 , β, β 5 , β 3 , 1, 0, β 7 , 1) = (τ (β 2 ), τ (β), τ (β 5 ), τ (β 3 ), τ (1), τ (0), τ (β 7 ), τ (1))
= (GC, AT, CC, AG, T T, AA, GT, T T ).
Also,
θ(α) = I0 + β 13 I1 + 0I2 + I3 + β 12 I4 + β 5 I5 + β 4 I6 + β 8 I7
⇒ ϕ(θ(α)) = (1, β 13 , 0, 1, β 12 , β 5 , β 4 , β 8 )
⇒ τ2 (1, β 13 , 0, 1, β 12 , β 5 , β 4 , β 8 ) = (T T, T G, AA, T T, GA, CC, T A, CG).
Thus, ϕ(α) and ϕ(θ(α)) are DNA reverses of each other.
n
The Gray map ϕ can be extended to n−coordinates. For c = (c0 , . . . , cn−2 , cn−1 ) ∈ Rk,s
we
have ϕ(c) = (ϕ(c0 ), . . . , ϕ(cn−2 ), ϕ(cn−1 )). In this case the DNA reverse of ϕ(c) will be ϕ(θ(c)r ) =
(ϕ(θ(cn−1 )), ϕ(θ(cn−2 )), . . . ϕ(θ(c0 ))) where θ(c) = (θ(c0 ), . . . , θ(cn−2 ), θ(cn−1 )).
n
Definition 4. Let C ⊆ Rk,s
. If the DNA reverse of ϕ(c) exists in ϕ(C), for all c ∈ C, then C or
equivalently ϕ(C) is called a reversible DNA code.

Definition 5 ([16]). Let f (x) = a0 + a1 x + . . . + at xt be a polynomial of degree t over Rk,s . f (x)
is said to be a palindromic polynomial if ai = at−i for all i ∈ {0, 1, . . . , t}. And f (x) is said to be a
θ-palindromic polynomial if ai = θ(at−i ) for all i ∈ {0, 1, . . . , t}.
Let C be a skew cyclic code of length n over Fq with respect to an automorphism θ′ . If the order
of θ′ and n are relatively prime then C is a cyclic code over Fq [26]. Similarly, any skew cyclic code
of odd length over Rk,s with respect to θ is a cyclic code, since the order of θ is 2. For this reason we
restrict the length n to even numbers only.
Theorem 4. Let C = (g(x)) be a skew cyclic code of length n over Rk,s where g(x) is a right divisor
of xn − 1 in Rk,s [x; θ] and deg(g(x)) is odd. If g(x) is a θ-palindromic polynomial then ϕ(C) is a
reversible DNA code.
7

Proof. Let g(x) be a θ-palindromic polynomial and t = n−deg(g(x)). Recall that ϕ(c) and ϕ(θ(c)r ) are
DNA reverses of each other. Note that, we do not distinguish between the vector
representation and the
P
n
i
polynomial representation of a codeword in Rk,s
. For each c ∈ C, c(x) = t−1
i=0 βi x g(x) for some βi ∈
Pt−1
′
′
Rk,s , since C = (g(x)).
the DNA reverse of ϕ(c) is ϕ(c ) where c (x) = i=0 θ(βi )xt−1−i g(x).
P Thent−1−i
′
g(x) ∈ C, then ϕ(c′ ) ∈ ϕ(C). Hence ϕ(C) is a reversible DNA
Since c (x) =
i θ(βi )x
code.
Theorem 5. Let C = (g(x)) be a skew cyclic code of length n over Rk,s where g(x) is a right divisor of
xn − 1 in Rk,s [x; θ] and deg(g(x)) is even. If g(x) is a palindromic polynomial then ϕ(C) is a reversible
DNA code.
Proof. Let g(x) be a palindromic polynomial and t = n − deg(g(x)). For each c ∈ C, c(x) =
Pt−1
xi g(x) for some βi ∈ Rk,s , since C = (g(x)). Then the DNA reverse of ϕ(c) is ϕ(c′ ) where
i=0 βiP
t−1
t−1−i
g(x).
c′ (x) = i=0 θ(βi )x
P
t−1−i
′
g(x) ∈ C, then ϕ(c′ ) ∈ ϕ(C). Hence ϕ(C) is a reversible DNA
Since c (x) =
i θ(βi )x
code.
In Remark 1 of [15], an illustration of proofs has been given for the case k = 1 and s = 2, i.e. for
the ring R1,2 = F16 + u1 F16 + u2 F16 + u1 u2 F16 . This simple method works for all rings Rk,s .
Example 4. Let us consider the skew polynomial ring R1,3 [x; θ]. Let β be a primitive element of F42 ,
then
x6 − 1 = h(x)g(x) =[1 + (β(u2 + u3 ) + β 7 )x + (β(u2 + u3 ) + β 7 )x2 + x3 ]
[1 + (β(u2 + u3 ) + β 7 )x + (β 4 (u2 + u3 ) + β 13 )x2 + x3 ] ∈ R1,3 [x; θ].
Since g(x) = 1 + (β(u2 + u3 ) + β 7 )x + (β 4 (u2 + u3 ) + β 13 )x2 + x3 is a θ-palindromic polynomial with
odd degree then C = (g(x)) is a reversible DNA-code over R1,3 .
Example 5. Let us consider the skew polynomial ring R1,3 [x; θ]. Let β be a primitive element of F42 ,
then
x6 − 1 = h(x)g(x) =[1 + (β 14 + u1 + u2 )x + x2 ]
[1 + (β 14 + u1 + u2 )x + (β 14 + u1 + u2 )x3 + x4 ] ∈ R1,3 [x; θ].
Since g(x) = 1 + (β 14 + u1 + u2 )x + (β 14 + u1 + u2 )x3 + x4 is a palindromic polynomial with even degree
then C = (g(x)) is a reversible DNA-code over R1,3 .

5

Conclusion

In this study, we solve the reversibility problem for DNA codes over non-chain ring Rk,s . We use skew
cyclic codes which provide a direct solution for finding reversible DNA codes. This method that is
based on non-commutativity property of the ring has proven to be more compact and more feasible
than the commutative counterparts (e.g. [5, 22, 23]). Generalization of Rk,s = F42k [u1 , . . . , us ]/hu21 −
u1 , . . . , u2s −us i by changing powers of ui (i = 1, 2, ...s) and obtaining optimal codes are open problems.
There are just a few papers on k-mer based DNA codes including this one. Investigating the reversibility
problem over different rings is an interesting problem. Further, relating these theoretical findings to
real DNA data is even more interesting and challenging problem.
8

References
[1] T. Abualrub, A. Ghrayeb, N. Aydin and I. Siap, “On the construction of skew quasi-cyclic codes”,
IEEE Trans. Inform. Theory, vol. 56, no. 5, pp. 2080–2090, 2010.
[2] T. Abulraub, A. Ghrayeb and X. Nian Zeng, Construction of cyclic codes over GF (4) for DNA
computing, J. Franklin Inst. Vol. 343, No. 4-5, pp. 448–457, 2006.
[3] L. Adleman, Molecular computation of solutions to combinatorial problems, Science, New Series,
Vol. 266, pp. 1021–1024, 1994.
[4] L. Adleman, P. W. K. Rothemund, S. Roweis, E. Winfree, On applying molecular computation
to the Data Encryption Standard, J. Comput. Biol. 6(1) (1999) 53–63.
[5] A. Bayram, E.S. Oztas, I. Siap, Codes over F4 + vF4 and some DNA applications, Designs,Codes
and Cryptography, DOI 10.1007/s10623-015-0100-8, (2015).
[6] N. Bennenni, K. Guenda, S. Mesnager, ”DNA cyclic codes over rings”, Advances in Mathematics
of Communications, vol. 11, pp. 83, 2017
[7] D. Boneh, C. Dunworth, R. Lipton, Breaking DES using molecular computer, Princeton CS Tech–
Report, Number CS–TR–489–95, 1995.
[8] D. Boucher, W. Geiselmann and F. Ulmer, Skew cyclic codes, Appl. Algebra Eng. Comm., Vol.
18, No. 4, pp. 379–389, 2007.
[9] D. Boucher, P. Solé and F. Ulmer, Skew constacyclic codes over Galois rings, Adv. Math. Commun., 2 (2008), 273–292.
[10] D. Boucher and F.Ulmer, A note on the dual codes of module skew codes, Vol. 7089, pp. 230–243,
2011.
[11] D. Boucher and F. Ulmer, Coding with skew polynomial rings, J. Symb. Comput., Vol. 44, No. 12,
pp. 1644–1656, 2009.
[12] D. A. Cox , J. Little , D. O’Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3/e (Undergraduate Texts in Mathematics), Springer-Verlag New York, Inc., Secaucus, NJ, 2007.
[13] K. Guenda and T. A. Gulliver, Construction of cyclic codes over F2 + uF2 for DNA computing,
Appl. Algebra Eng. Commun. Comput, 24 (2013), 445–459.
[14] K. Guenda, T. A. Gulliver and P. Solé, On cyclic DNA codes, in Proc. IEEE Int. Symp. Inform.
Theory, Istanbul, 2013, 121-125.
[15] F. Gursoy, E. S. Oztas, I. Siap, Reversible DNA Codes over F16 + uF16 + vF16 + uvF16 , Adv.
Math. Commun. vol. 11 no. 2, (2017) 307–312.
[16] F. Gursoy, E. S. Oztas, I. Siap, Reversible DNA Codes using Skew Polynomial Rings, Appl.
Algebra Engrg. Comm. Comput., 28(4) (2017) 311–320.

9

[17] F. Gursoy, I. Siap, B. Yildiz, Construction of skew cyclic codes over Fq + vFq , Adv. Math.
Commun., Vol. 8 No. 3, pp. 313–322, 2014.
[18] N. Jacobson, Finite-Dimensional Division Algebras over Fields, Springer, Berlin, 1996.
[19] S. Jitman, S. Ling and P. Udomkavanich, “Skew constacyclic codes over finite chain rings”, Advances in Mathematics of Communications, vol. 6, no. 1, pp. 39–63, 2012.
[20] J. Lichtenberg, A. Yilmaz, J. Welch, K. Kurz, X. Liang, F. Drews, K. Ecker, S. Lee, M. Geisler,
E.Grotewold, L. Welch, The word landscape of the non-coding segments of the Arabidopsis
thaliana genome, BMC Genomics 10(1) (2009) 463–495.
[21] B. R. McDonald, Finite rings with identity, Marcel Dekker Inc., New York, 1974.
[22] E.S. Oztas, I. Siap, Lifted polynomials over F16 and their applications to DNA Codes, Filomat,
Vol. 27, No. 3, pp. 459–466, 2013.
[23] E.S. Oztas, I. Siap, On a generalization of lifted polynomials over finite fields and their applications
to DNA codes, Int. J. Comput. Math. Vol. 92, No. 9, pp. 1976–1988, 2015.
[24] E.S. Oztas, B. Yildiz, I. Siap, A novel approach for constructing reversible codes and applications
to DNA codes over the ring F2 [u]/(u2k − 1), Finite Fields Appl. 46 (2017) 217–234.
[25] E.S. Oztas, B. Yildiz, I. Siap, On DNA codes from a family of chain rings, J. Algebra Comb.
Discrete Struct. Appl., vol. 4, no. 1, 93–102, 2017.
[26] I. Siap, T. Abualrub, N. Aydin and P. Seneviratne, Skew cyclic codes of arbitrary length, Int. J.
Inform. Coding Theory, Vol. 2, No. 1, pp. 10–20, 2011.
[27] I. Siap, T. Abulraub and A. Ghrayeb, Similarity cyclic DNA codes over rings, International
Conference on Bioinformatics and Biomedical Engineering, in Shanghai, PRC, May 16-18th 2008.
[28] I. Siap, T. Abulraub and A. Ghrayeb, Cyclic DNA codes over the ring F2 [u]/(u2 − 1) based on
the deletion distance, J. Franklin Inst., Vol. 346, No. 8, pp. 731–740, 2009.
[29] Ting Yao, Minjia Shi, Patrick Solé, Skew cyclic codes over Fq + uFq + vFq + uvFq , J. Algebra
Comb. Discrete Struct. Appl. 2(3) (2015) 163–168.
[30] B. Yildiz, I. Siap, Cyclic codes over F2 [u]/(u4 − 1) and applications to DNA codes, Comput. Math.
Appl., Vol. 63, No. 7, pp. 1169–1176, 2012.

10

