Mutually Uncorrelated Primers for DNA-Based Data Storage

We introduce the notion of weakly mutually uncorrelated (WMU) sequences, motivated by applications in DNA-based data storage systems and synchronization between communication devices. WMU sequences are characterized by the property that no sufficiently long suffix of one sequence is the prefix of the same or another sequence. WMU sequences used for primer design in DNA-based data storage systems are also required to be at large mutual Hamming distance from each other, have balanced compositions of symbols, and avoid primer-dimer byproducts. We derive bounds on the size of WMU and various constrained WMU codes and present a number of constructions for balanced, error-correcting, primer-dimer free WMU codes using Dyck paths, prefix-synchronized, and cyclic codes.

• Publication year

  2017

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2017-09-13

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TIT.2018.2792488arXiv 1709.05214
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Mutually Uncorrelated Codes for DNA Storage

  2018cited by this paper
• Codes in the damerau distance for DNA storage

  2016cited by this paper
• Portable and Error-Free DNA-Based Data Storage

  2016cited by this paper
• Codes for DNA sequence profiles

  2015cited by this paper
• A Rewritable, Random-Access DNA-Based Storage System

  2015cited by this paper
• DNA-Based Storage: Trends and Methods

  2015cited by this paper
• Asymmetric Lee distance codes for DNA-based storage

  2015cited by this paper
• Towards practical, high-capacity, low-maintenance information storage in synthesized DNA

  2013cited by this paper
• Non-Overlapping Codes

  2013influential reference
• Next-Generation Digital Information Storage in DNA

  2012cited by this paper
• Cross-Bifix-Free Codes Within a Constant Factor of Optimality

  2012cited by this paper
• A New Approach to Cross-Bifix-Free Sets

  2011cited by this paper
• Base-stacking and base-pairing contributions into thermal stability of the DNA double helix

  2006cited by this paper
• DNA codes that avoid secondary structures

  2005cited by this paper
• On the Design of Codes for DNA Computing

  2005cited by this paper
• Distributed sequences and search process

  2004cited by this paper
• AutoDimer: a screening tool for primer-dimer and hairpin structures.

  2004cited by this paper
• Codes for mass data storage systems

  2004cited by this paper
• Frame synchronization using distributed sequences

  2000cited by this paper
• Constructions of binary constant-weight cyclic codes and cyclically permutable codes

  1992cited by this paper
• Maximal Prefix-Synchronized Codes

  1978cited by this paper
• On the expected duration of a search for a fixed pattern in random data

  1973cited by this paper
• Optimum Frame Synchronization

  1972cited by this paper
• THE AVERAGE HEIGHT OF PLANTED PLANE TREES

  1972cited by this paper
• Synchronization of binary messages

  1960cited by this paper
• A comparison of signalling alphabets

  1952cited by this paper

• Constrained Coding Bounds via Goulden–Jackson Cluster Theorem

  2025cites this paper
• On Algebraic Designing of DNA Codes With Biological and Combinatorial Constraints

  2025cites this paper
• Straightforward and Efficient Constrained Codes

  2025influential citation
• Q-ary (1,k)-overlap-free Codes with given Restrictions

  2025cites this paper
• Achieving handle-level random access in an encrypted DNA archival storage system via frequency dictionary mapping coding

  2025cites this paper
• ReLume: Enhancing DNA storage data reconstruction with flow network and graph partitioning.

  2025cites this paper
• A Dynamic Sliding Window Encoding for Secured DNA Data Storage Compliant With Biological and Indexing Constraints

  2025cites this paper
• A generalized construction of variable-length non-overlapping codes

  2025cites this paper
• Family of Mutually Uncorrelated Codes for DNA Storage Address Design

  2025cites this paper
• New construction of non-expandable (1, k)-overlap-free codes

  2025cites this paper
• Constructions and Bounds for q-Ary (1, k)-Overlap-Free Codes

  2024cites this paper
• Tail-Erasure-Correcting Codes

  2024cites this paper
• Two-dimensional q-ary non-overlapping codes

  2024cites this paper
• Codes with restricted overlaps: expandability, constructions, and bounds

  2024cites this paper
• On maximal almost balanced non-overlapping codes and non-overlapping codes with restricted run-lengths

  2024cites this paper
• Efficient and low-complexity variable-to-variable length coding for DNA storage

  2024cites this paper
• Survey for a Decade of Coding for DNA Storage

  2024cites this paper
• Representing Information on DNA Using Patterns Induced by Enzymatic Labeling

  2024cites this paper
• Efficient data reconstruction: The bottleneck of large-scale application of DNA storage.

  2024cites this paper
• Naslavljanje DNA-pomnilnikov

  2024cites this paper
• On the maximum size of variable-length non-overlapping codes

  2024cites this paper
• Improved Gilbert-Varshamov Bounds for Hopping Cyclic Codes and Optical Orthogonal Codes

  2023cites this paper
• Balanced Set Codes With Small Intersections

  2023cites this paper
• GCNSA: DNA storage encoding with a graph convolutional network and self-attention

  2023cites this paper
• On the Design of Codes for DNA Computing: Secondary Structure Avoidance Codes

  2023cites this paper
• Improved constructions of secondary structure avoidance codes for DNA sequences

  2023cites this paper
• In search of maximum non-overlapping codes

  2023cites this paper
• Bee Identification Problem for DNA Strands

  2023cites this paper
• Weakly mutually uncorrelated codes with maximum run length constraint for DNA storage

  2023cites this paper
• DNA-Based Data Storage Systems: A Review of Implementations and Code Constructions

  2023cites this paper
• DNA-Based Storage of RDF Graph Data: A Futuristic Approach to Data Analytics

  2023cites this paper
• Design of DNA Storage Coding with Enhanced Constraints

  2022influential citation
• Constructions and Bounds for Codes With Restricted Overlaps

  2022cites this paper
• Convergence of the Number of Period sets in Strings

  2022cites this paper
• Balanced reconstruction codes for single edits

  2022cites this paper
• Adaptive coding for DNA storage with high storage density and low coverage

  2022influential citation
• Bee Identification Problem for DNA Strands

  2022cites this paper
• Rewritable two-dimensional DNA-based data storage with machine learning reconstruction

  2021cites this paper
• Design of Constraint Coding Sets for Archive DNA Storage

  2021cites this paper
• Minimum Free Energy Coding for DNA Storage

  2021cites this paper
• Quasi-cyclic codes: algebraic properties and applications

  2020cites this paper
• Improved Coding Over Sets for DNA-Based Data Storage

  2020cites this paper
• Coded Trace Reconstruction

  2020influential citation
• Construction of Duplication Correcting Codes

  2020cites this paper
• Efficient and Explicit Balanced Primer Codes

  2020influential citation
• An Intelligent Optimization Algorithm for Constructing a DNA Storage Code: NOL-HHO

  2020cites this paper
• K-Means Multi-Verse Optimizer (KMVO) Algorithm to Construct DNA Storage Codes

  2020cites this paper
• Construction of tandem duplication correcting codes

  2019cites this paper
• Coded Trace Reconstruction

  2019influential citation
• Anchor-Based Correction of Substitutions in Indexed Sets

  2019cites this paper
• Set-Codes with Small Intersections and Small Discrepancies

  2019cites this paper
• Binary Robust Positioning Patterns with Low Redundancy and Efficient Locating Algorithms

  2019cites this paper
• Efficient and Explicit Balanced Primer Codes

  2019influential citation
• Robust Positioning Patterns with Low Redundancy

  2019cites this paper
• I T ] 9 S ep 2 01 9 Coded Trace Reconstruction

  2019influential citation
• Analysis of synchronized storage method for multimedia key areas based on machine learning

  2019cites this paper
• Improved DNA based storage capacity and fidelity using composite DNA letters

  2018cites this paper
• Unique Reconstruction of Coded Strings From Multiset Substring Spectra

  2018cites this paper
• The Capacity of Associated Subsequence Retrieval

  2018cites this paper