Our goal is to describe an encoder-decoder for storing data in DNA where:
(1) The GC-AT content is at most 5% imbalanced.
(2) Homopolymer-runs are at most of length 3.
(3) The targets are encoded quaternary strands of length 100-500 nucleotides.
(4) The encoder-decoder should work at linear time (at most).
(5) Demands reasonable memory requirements.
Additionally, we assume that there will be a singular output length for every input length. In algorithms where the output length varies, we chose the worst-case output length.
Reliability is an inherent challenge for the emerging nonvolatile technology of racetrack memories, and there exists a fundamental relationship between codes designed for racetrack memories and codes with constrained periodicity. Previous works have sought to construct codes that avoid periodicity in windows yet have either only provided existence proofs or required high redundancy. This paper provides the first constructions for avoiding periodicity that are both efficient (average-linear time) and with low redundancy (near the lower bound). The proposed algorithms are based on iteratively repairing windows which contain periodicity until all the windows are valid. Intuitively, such algorithms should not converge as there is no monotonic progression; yet, we prove convergence with average-linear time complexity by exploiting subtle properties of the encoder. Overall, we both provide constructions that avoid periodicity in all windows, and we also study the cardinality of such constraints.
Relevant Projects 
