In DNA data storage and computation, DNA strands are required to meet certain combinatorial constraints. This paper shows how some of these constraints can be achieved simultaneously. First, we use the algebraic structure of irreducible cyclic codes over finite fields to generate cyclic DNA codes that satisfy reverse and complement properties. We show how such DNA codes can meet constant guanine-cytosine content constraint by MacWilliams-Seery algorithm. Second, we consider fulfilling the run-length constraint in parallel with the above constraints, which allows a maximum predetermined number of consecutive duplicates of the same symbol in each DNA strand. Since irreducible cyclic codes can be represented in terms of the trace function over finite field extensions, the linearity of the trace function is used to fulfill a predefined run-length constraint. Thus, we provide an algorithm for constructing cyclic DNA codes with the above properties including run-length constraint. We show numerical examples to demonstrate our algorithms generating such a set of DNA strands with all the prescribed constraints.
Ramy TAKI ELDIN
Ain Shams University
Hajime MATSUI
Toyota Technological Institute
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Ramy TAKI ELDIN, Hajime MATSUI, "Run-Length Constraint of Cyclic Reverse-Complement and Constant GC-Content DNA Codes" in IEICE TRANSACTIONS on Fundamentals,
vol. E103-A, no. 1, pp. 325-333, January 2020, doi: 10.1587/transfun.2019EAP1053.
Abstract: In DNA data storage and computation, DNA strands are required to meet certain combinatorial constraints. This paper shows how some of these constraints can be achieved simultaneously. First, we use the algebraic structure of irreducible cyclic codes over finite fields to generate cyclic DNA codes that satisfy reverse and complement properties. We show how such DNA codes can meet constant guanine-cytosine content constraint by MacWilliams-Seery algorithm. Second, we consider fulfilling the run-length constraint in parallel with the above constraints, which allows a maximum predetermined number of consecutive duplicates of the same symbol in each DNA strand. Since irreducible cyclic codes can be represented in terms of the trace function over finite field extensions, the linearity of the trace function is used to fulfill a predefined run-length constraint. Thus, we provide an algorithm for constructing cyclic DNA codes with the above properties including run-length constraint. We show numerical examples to demonstrate our algorithms generating such a set of DNA strands with all the prescribed constraints.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2019EAP1053/_p
Copy
@ARTICLE{e103-a_1_325,
author={Ramy TAKI ELDIN, Hajime MATSUI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Run-Length Constraint of Cyclic Reverse-Complement and Constant GC-Content DNA Codes},
year={2020},
volume={E103-A},
number={1},
pages={325-333},
abstract={In DNA data storage and computation, DNA strands are required to meet certain combinatorial constraints. This paper shows how some of these constraints can be achieved simultaneously. First, we use the algebraic structure of irreducible cyclic codes over finite fields to generate cyclic DNA codes that satisfy reverse and complement properties. We show how such DNA codes can meet constant guanine-cytosine content constraint by MacWilliams-Seery algorithm. Second, we consider fulfilling the run-length constraint in parallel with the above constraints, which allows a maximum predetermined number of consecutive duplicates of the same symbol in each DNA strand. Since irreducible cyclic codes can be represented in terms of the trace function over finite field extensions, the linearity of the trace function is used to fulfill a predefined run-length constraint. Thus, we provide an algorithm for constructing cyclic DNA codes with the above properties including run-length constraint. We show numerical examples to demonstrate our algorithms generating such a set of DNA strands with all the prescribed constraints.},
keywords={},
doi={10.1587/transfun.2019EAP1053},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - Run-Length Constraint of Cyclic Reverse-Complement and Constant GC-Content DNA Codes
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 325
EP - 333
AU - Ramy TAKI ELDIN
AU - Hajime MATSUI
PY - 2020
DO - 10.1587/transfun.2019EAP1053
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E103-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2020
AB - In DNA data storage and computation, DNA strands are required to meet certain combinatorial constraints. This paper shows how some of these constraints can be achieved simultaneously. First, we use the algebraic structure of irreducible cyclic codes over finite fields to generate cyclic DNA codes that satisfy reverse and complement properties. We show how such DNA codes can meet constant guanine-cytosine content constraint by MacWilliams-Seery algorithm. Second, we consider fulfilling the run-length constraint in parallel with the above constraints, which allows a maximum predetermined number of consecutive duplicates of the same symbol in each DNA strand. Since irreducible cyclic codes can be represented in terms of the trace function over finite field extensions, the linearity of the trace function is used to fulfill a predefined run-length constraint. Thus, we provide an algorithm for constructing cyclic DNA codes with the above properties including run-length constraint. We show numerical examples to demonstrate our algorithms generating such a set of DNA strands with all the prescribed constraints.
ER -