Scaling Storage and Algorithms Beyond Binary Alphabets

24 concepts19 papers1 proposal

Computer science was built on the simplicity of the binary alphabet $\{0, 1\}$. It is mathematically clean, physically robust for silicon transistors, and easy to reason about. However, as we push the boundaries of data density—particularly in molecular storage media like DNA and synthetic polymers—and seek optimal performance in core string-processing data structures, this binary constraint becomes a fundamental bottleneck.

If we expand our alphabet size from $M = 2$ to a larger value, the information density per position scales logarithmically as $\log_2 M$. Moving from two states to eight, eleven, or twelve states offers a massive leap in raw storage capacity and writing throughput. Yet, doing so breaks many of our foundational theoretical tools. A major research direction has emerged to bridge this gap, focusing on the physical realization of expanded molecular alphabets and the generalization of the algorithms, data structures, and error-correcting codes needed to support them.

The Physical Mechanics of Expanded Alphabets

In molecular data storage, the standard genetic code provides a natural quaternary alphabet $\{A, C, G, T\}$, yielding 2 bits of information per position. To break past this density limit, researchers are engineering non-canonical systems that expand the available chemical vocabulary.

One approach introduces entirely new chemical building blocks. S. Kasra Tabatabaei et al. demonstrated an 11-letter molecular alphabet by incorporating chemically modified nucleotides alongside natural bases. By pairing this expanded alphabet with a deep learning-based nanopore readout, the authors nearly doubled data density and boosted writing throughput, since each sequential chemical addition step writes significantly more information. Similarly, Yan Wang et al. reviewed the transition to non-canonical nucleic acids (ncNAs), showing that a 12-letter alphabet raises the theoretical storage capacity from 2 bits to 3.58 bits per nucleotide position while providing enhanced environmental stability.

Binary Alphabet:      [0] [1]                               -> 1.00 bit/site
Quaternary (DNA):     [A] [C] [G] [T]                       -> 2.00 bits/site
Expanded Molecular:   [A] [C] [G] [T] [m1] [m2] ... [m7]    -> 3.46 bits/site

Alternatively, instead of synthesizing unique chemical bases, researchers can manipulate the physical geometry of the polymer backbone. Chao Pan et al. introduced "DNA Tails," a storage architecture that mimics the multi-level cell (MLC) logic of solid-state flash memory. Instead of relying on binary state changes (such as enzymatic nicking), the authors used enzymatic synthesis to grow single-stranded DNA extensions of varying lengths at specific sites. By treating the discrete physical length of the extension as a distinct information state, they achieved up to eight distinct symbols per site, packing multiple bits into a single molecular location.

The Theoretical Bottleneck: Combinatorial Explosion

If expanding the alphabet is physically viable, why haven't our digital systems and algorithms kept pace? The challenge lies in the mathematical and notational complexity that emerges when transitioning from binary ($M=2$) to arbitrary or higher-order alphabet sizes ($M > 2$).

Consider digital trees like tries and suffix trees, which underpin high-speed routing and string searching. Classic proofs for their structural properties—such as the distribution of "protected nodes" or external path lengths—rely heavily on the simplicity of binary branching. As Jeffrey Gaither et al. and Kevin Leckey et al. point out, generalizing these frameworks to larger alphabets introduces severe analytical hurdles, often leaving explicit constants uncalculated because the dependencies between overlapping string suffixes scale poorly. Even optimization techniques like level compression see their asymptotic guarantees shift when applied to non-binary data types, a phenomenon analyzed by Svante Janson.

This combinatorial explosion also impacts state synchronization in automata. Vladimir V. Gusev et al. noted that scaling random-input synchronization models beyond two symbols introduces intricate transition behaviors that resist traditional binary proofs, requiring entirely new mathematical models to handle the increased degree of freedom.

Error Correction and Reconstruction in Higher Dimensions

The most critical challenge of an expanded alphabet is maintaining data integrity. In a binary system, an error is simple: a 0 becomes a 1. In an $M$-ary molecular system, a symbol can mutate into any of the other $M-1$ symbols, or it can be completely deleted or inserted during synthesis and sequencing.

Even the step from binary to standard quaternary DNA requires entirely new coding formulations to handle the messy reality of biological storage, as explored by Andreas Lenz et al. and Anisha Banerjee et al.. When the alphabet scales further to accommodate diverse synthetic monomers, traditional error-correction frameworks break down. Anisha Banerjee et al. and Ryan Gabrys et al. emphasize that generalizing codes to support higher-order alphabets is essential for managing insertion and deletion errors in multi-monomer mixtures, where molecules are read together in a single "soup."

Binary Error Space:      [0] <------ Bit Flip ------> [1]

M-ary Error Space:       [A] <--- Substitution ----> [B]
                          |                           |
                      Deletion                    Insertion
                          |                           |
                          v                           v
                         [ ]                         [C]

Furthermore, reading molecular data often requires reconstructing strings from fragmented or noisy copies (traces). Classic mathematical models for trace reconstruction (Nina Holden et al.), circular string recovery (Akiko Manada et al.), and reconstruction from prefix/suffix compositions (Srilakshmi Pattabiraman et al.) have historically been restricted to binary strings. Moving these to larger alphabets requires rethinking the underlying combinatorial structures.

For example, Tuvi Etzion et al. observed that generalizing specialized combinatorial structures like de Bruijn covering sequences to higher-order alphabets often degrades efficiency, necessitating entirely new algebraic approaches.

Conversely, this expanded complexity can sometimes be turned into an advantage. In cryptography, Heping Wen et al. demonstrated that an extended RNA dynamic coding scheme with a massive rule set can dramatically increase data randomness and complexity, turning alphabet expansion into a powerful mechanism for image encryption.

Ultimately, scaling past binary alphabets requires a tight co-design between chemical engineering and discrete mathematics. By rewriting algorithms to tolerate the combinatorial complexity of $M$-ary states, researchers are unlocking the massive density advantages promised by molecular physics.

Key Foundational Work

Partial fillup and search time in LC tries (2005) — contributed 1 concept elements to this direction.
Towards More Realistic Probabilistic Models for Data Structures: The External Path Length in Tries under the Markov Model (2012) — contributed 1 concept elements to this direction.
On the Number of 2-Protected Nodes in Tries and Suffix Trees (2012) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_alphabet_size_scalability_7b9e098f,
  title = {alphabet size scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/alphabet-size-scalability/rdr_7b9e098fd7e8459cb38d86c880af5502},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_alphabet_size_scalability_7b9e098f_v1,
  title = {alphabet size scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/alphabet-size-scalability/rdr_7b9e098fd7e8459cb38d86c880af5502/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake