Repeat-Free Codes With Local Constraints

Abstract

<italic>Repeat-free</italic> sequences were recently introduced to reduce errors in the reconstruction process of DNA strings. Such sequences have the property that every <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-tuple appears at most once (for predefined <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>). In this paper, we consider the problem of encoding data into a <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula><italic>-repeat free</italic> sequence that also adheres to local constraints. First, we provide encoding and decoding schemes for primitive systems. Under an additional irreducibility assumption on a specific sub-system, we improve upon the best-known capacity result, and show that the capacity of such systems is determined only by the local constraints as long as <inline-formula> <tex-math notation="LaTeX">$k\geqslant (1+\epsilon)\log (n)$ </tex-math></inline-formula>. With no additional assumptions, we provide encoding and decoding schemes for <inline-formula> <tex-math notation="LaTeX">$k\geqslant (2+\epsilon)\log (n)$ </tex-math></inline-formula>. We then generalize the encoding and decoding scheme to irreducible systems.