Coding Theory and Algorithms for Emerging Technologies in Synthetic Biology

One of the main issues associated with DNA-based data storage system implementations is the high cost and large latency of DNA synthesis. Current estimates are that recording one bit of information via synthesis takes off the order of seconds, which is prohibitive for practical applications.

To mitigate this issue, in our prior work, we proposed the first known molecular storage system that uses both native and chemically modified bases to expand the molecular alphabet used during recording. While expanded alphabets may be beneficial for recording, they may be a challenge to read (sequence) using existing technologies. To this end, we examine how chemically modified bases can be classified using nano pore and PacBio sequencers, and propose tailor-made machine learning methods that can clean the current and kinetics signals provided by the readers and lead to high readout accuracy.

The genetic code serves as a molecular mapping function, translating triplets of nucleotides into the 20 amino acids that comprise proteins. The Central Dogma of Biology outlines the processes of transcription of DNA into RNA and the subsequent translation of RNA into proteins. Decoding of information within genes occurred through codons – triplets of nucleotides in RNA that are interpreted by tRNA molecules with complementary anticodons.

While accurate execution of this code is essential for producing unique protein sequences from each gene, the inherent molecular processes within cells inevitably lead to errors.

We present new experimental and computational methods for mapping errors that occur during transcription and translation. These errors include the incorporation of incorrect amino acids, shifts in the reading frame that alter the resulting amino acid sequence due to a single nucleotide shift, and the violation of translation stop codon signals leading to unintended protein extensions. We further discuss post-synthesis chemical editing of RNA molecules, which modulates the genetic information encoded in DNA and allows a single gene to produce multiple protein products.

One of the primary challenges we face is distinguishing between neutral, deleterious, and beneficial errors and edits. While some events may have no selective advantage, and even disadvantage, evolution appears to favor instances where diversity confers adaptability. We provide compelling examples illustrating how translation errors enable organisms to create and propagate protein diversity faster than DNA mutations can generate genetic variation.

Our findings suggest that errors and edits within the Central Dogma represent a newly recognized mechanism through which evolution fosters functional diversity, upon which natural selection can act.

In this session, we’ll explore the Composite Motif-Based DNA Data Storage system developed by Helixworks as part of the MoSS project. This system takes DNA data storage a step further by significantly increasing the amount of data encoded per synthesis operation, from 2 bits to 48 bits. At the same time, it improves data retrieval accuracy, enabling effective recovery even with low oligo read coverage.

The talk will provide a technical overview of our fully automated, end-to-end system. It integrates encoding, oligo synthesis, sequencing, and data retrieval into one streamlined workflow.

Key outcomes include the successful synthesis of oligonucleotides up to 625 nucleotides long, scaled to $1,000$ oligos per run. The system achieved a $98\%$ motif recovery rate when oligos were sequenced at 32 attomoles each and a $60\%$ recovery rate at just $1$ attomole each. This indicates that smaller DNA amounts can be used effectively in combination with error-correction codes for data recovery. Additionally, it features real-time base-to-bit decoding powered by Nanopore sequencing.

Advances in molecular profiling technologies are propelling medicine toward a future that is more predictive, preventative, personalized, and participatory. A core challenge is to leverage the vast, complex datasets generated by these technologies to build computational models that can meaningfully link molecular data to high-level disease phenotypes. Such models could provide valuable insights, improve diagnostics, and guide personalized treatment strategies.

This task demands machine learning models that are flexible enough to capture the biological complexity of these relationships, data-efficient enough to operate on typically small clinical datasets, and interpretable to allow insights to be contextualized within established biological knowledge.

Synthesising DNA strands using combinations of short sequences (motifs) from a fixed motif library is an interesting alternative to nucleotide-by-nucleotide synthesis because it could potentially reduce the cost of synthesis – a major obstacle to adopting DNA storage for long-term archival data. We discuss channel errors observed in an empirical dataset provided to us by HelixWorks, propose channel models that mimic these types of errors, and discuss the trade-offs associated with different coding schemes and code parameters for the proposed channel models.

This talk is intended to provide an introduction to the relevance of non-canonical and chemically-engineered nucleic acids in synthetic as well as molecular biology. First, some of the non-canonical modifications are introduced. These include non-canonical nucleotides relevant to epigenetics, as well as chemically-designed modifications engineered to augment specific properties of DNA or RNA, such as adding nuclease resistance or increasing thermodynamic stability, while simultaneously maintaining essential recognition by nucleic acid processing enzymes. These modifications are known to be essential for nucleic acid therapeutics and therefore are an important research topic. Large-scale synthesis of DNA or RNA libraries with natural or engineered chemical modifications can be accomplished using nucleic acid photolithography.

I discuss how to find the capacity of noisy permutation channels. The noisy permutation channel models DNA storage systems where strands of DNA are abstracted as symbols. The individual symbols go through a process where they are subjected to memoryless noise and a uniform permutation is then applied to the collection of symbols. The capacity the noisy permutation channel represents the amount of information which can be stored in a DNA storage system with such properties. We find the exact capacity for strictly positive noise matrices using Kullback-Leibler (KL) divergence covering and a result bounding the KL divergence between sampling from a distribution with and without replacement.

During the translocation of a single-strand DNA molecule through a nanopore channel, its real-time conductance level is determined by the sequence of $\delta$ nucleotides, also known as a $\delta$-mer, at its narrowest constriction. The nanopore sequencer produces noisy piecewise constant signals. Under the $\delta$-mer model, the pore goes through $k$ distinct states when the input DNA sequence has $k$ distinct $\delta$-mer substrings. In this talk, we denoise multiple nanopore signals drawn from the same Gaussian-output, DNA sequence-specific, hidden Markov model (HMM), and recover its state-dependent means. We assume that each HMM state $i$ can only transition to itself or to state $i+1$, and has Gaussian-distributed emissions with mean $x_i$. Starting from a Gaussian prior on $x_i$, we use importance sampling to approximate the conditional expectation of $x_i$ given the observations. We test the algorithm’s performance using both simulated and experimental nanopore signals generated by Oxford Nanopore Technologies’ R10.4.1 nanopore.

Counterfeit products result in an estimated loss of 45 billion EUR annually, affecting industries such as pharmaceuticals, food, and luxury goods. Ensuring the traceability of products is crucial, particularly for textiles, gemstones, critical components like airplane parts, and biological products. This talk proposes a framework for in-product authentication by embedding unique identifiers directly into products.

The proposed in-product authentication method must meet several criteria: it must be evaluable, reproducible, embeddable, unclonable, unpredictable, unique, one-way, tamper-evident, and property-preserving. The authentication process involves a challenge $𝐮\in {𝒜}_1^k$ resulting in a response $𝐫\in {𝒜}_2^m$, which is then processed to extract features $𝐜\in {𝒜}_3^n$.

Inspired by the EUF-CMA model, we propose a security protocol involving:

1. 1.

   Authentic substance and evaluation function: $\theta :𝐮\mapsto 𝐜$

2. 2.

   Function evaluation by an attacker: $({𝐮}_1,\mathrm{\dots },{𝐮}_q)\mapsto ({𝐜}_1,\mathrm{\dots },{𝐜}_q)$

3. 3.

   The attacker must: a) Predict the next outcome b) Create a new substance

We identify three attack scenarios: dilution, readout and reproduce, and amplification. To quantify security, we aim to draw parallels to classical cryptography, where security is measured in bits where $L$ bit represents that the most efficient attack has complexity $2^L$. For in-product authentication, we consider lab operations, material costs, time costs, and product entropy. We propose various entropy measures: entropy of resulting features, intra-device entropy for different challenges, inter-device distance entropy for the same challenge, and conditional entropy given $\mathrm{\ell }$ previous results.

The outlook includes further elaborating the framework for comparing in-product authentication schemes, creating more schemes and security mechanisms, and establishing a universal security level.

Emerging DNA storage technologies use composite DNA letters, where information is represented by probability vectors, leading to higher information density and lower synthesis cost. However, the issue of information leakage needs to be addressed due to untrusted storage providers. This paper introduces an asymptotic ramp secret sharing scheme (ARSSS) for distributed secret information storage using composite DNA letters. This innovative scheme, inspired by secret sharing methods over finite fields and enhanced with a modified matrix-vector multiplication operation for probability vectors, achieves asymptotic information-theoretic data security for a large alphabet size. Moreover, this scheme reduces the number of reading operations for DNA samples compared to traditional schemes and therefore lowers the complexity and the cost of DNA-based secret sharing.

DNA-based storage has attracted significant attention due to recent demonstrations and given the trends in cost decreases of DNA synthesis and sequencing, it is estimated that within the next 5 years DNA storage may become a highly competitive archiving technology. This technology introduces new challenges in finding coding solutions to address various problems associated with the implementation of DNA-based storage systems. In this talk, I will present several algorithmic and coding problems that are motivated by the DNA-based storage channel. Many of them are motivated by the special behavior of the errors in DNA which are mainly insertions, deletions, and substitutions. Then, I will discuss how to reduce not only the cost but also the latency of DNA storage by initiating the study of the DNA coverage depth problem, which aims to reduce the required number of reads to retrieve information from the storage system. Under this framework, our main goal is to understand the effect of error-correcting codes and retrieval algorithms on the required sequencing coverage depth.

The talk covered several topics related to coding, algorithms and design, in the context of synthetic biology. We first addressed information aspects of CRISPR activity. CRISPR-Cas systems are supposed to induce (cleavage or other) activity in a very specific manner. However – in practice we often observe detectable off-target activity, This can be obstructive in many applications and dangerous in therapeutic applications. I described work from my group that investigated off-target activity in CRISPR. I have particularly described CRISPECTOR, a machine learning based software tool that supports the measurement of off target activity in experiments done in cells. We then moved to combinatorial schemes for encoding information in DNA. Specifically – we addressed the effect on the number of required synthesis cycles. Using a coupon collector distribution analysis investigated the trade off with higher required synthesis depth. The talk corresponded with several other talks in the seminar, which addressed either CRISPR (eg Somoza, Rak) or combinatorial encoding and its applications (eg Yaakobi, Wang, Sokolovski).