Sequence Reconstruction from Unordered Fragment Compositions

This direction is split into other directions: permutation channel. Its last version stays readable and citable here.

Version 1 of 142 papers59 conceptsfrozen 2026-10-04

In traditional communication, we view data as a stream—a sequence of bits arriving in a specific, predictable order. However, emerging technologies like DNA data storage and polymer-based memory break this fundamental assumption. In these systems, reading data is more like reaching into a soup of molecules and pulling out random fragments. We lose the "where" and are left only with the "what."

The research direction explored here focuses on sequence reconstruction from unordered compositions: the mathematical and algorithmic challenge of recovering a unique original string when its structural order has been shattered into a multiset of fragments, counts, or masses.

The Ambiguity of the Bag-of-Parts

The core problem is ambiguity. If you are given the "bigrams" (overlapping pairs of letters) of a string, can you tell what the original string was? For example, the bigrams {AB, BA, AB} could come from ABAB or... nothing else? Actually, as Aryeh Kontorovich and Ari Trachtenberg demonstrate in Unique decodability of bigram counts by finite automata, determining if a set of "shingles" (overlapping substrings) maps to a unique string is non-trivial.

This is often framed as finding a unique Eulerian trail in a graph. Each fragment is an edge; if the graph structure allows for multiple paths that visit every edge exactly once, the reconstruction is ambiguous. Huimin Xie developed efficient ways to detect this non-uniqueness using finite automata, providing a way to tell on-the-fly if a DNA sequence reconstruction is certain or merely a guess Finite automata for testing composition-based reconstructibility of sequences.

From Sequences to Compositions

In molecular storage, the problem is even harder. We often don't even see the fragments themselves; we see their compositions (the count of each type of unit) or their masses.

Imagine a polymer chain. When we "read" it using tandem mass spectrometry, the chain breaks into fragments. We don't see the sequence of bits in a fragment; we only see its total weight. As Srilakshmi Pattabiraman and Ryan Gabrys explain in Coding for Polymer-Based Data Storage, this transforms a string problem into an algebraic one. If a fragment has a mass of 500, it might be composed of three "0" units and two "1" units, but we don't know their order.

Jayadev Acharya and colleagues showed that if you have the compositions of all possible substrings, you can often reconstruct the string using bivariate polynomials String Reconstruction from Substring Compositions. The intuition is that the set of all substring compositions acts like a unique "fingerprint" for the string, provided the string is long enough or the alphabet is large enough.

The Permutation Channel

At the extreme end of this loss of structure is the permutation channel. Here, the receiver gets all the symbols transmitted, but their order is completely randomized. It is as if you sent a sentence and the receiver got a bag of letters.

To communicate through such a channel, Mladen Kovačević and Vincent Y. F. Tan suggest that we must move away from traditional error-correction that relies on position Coding for the Permutation Channel with Insertions, Deletions, Substitutions, and Erasures. Instead, we encode information in the counts of symbols. In multi-user scenarios, Anuran Makur and William Lu have shown that "tagging" packets—essentially embedding a small piece of the "where" inside the "what"—allows us to recover the original timing information even after a total shuffle Permutation Capacity Region of Adder Multiple-Access Channels.

Designing for Reconstructibility

If the natural process of reading data (like sequencing DNA or mass spectrometry) destroys order, the solution is to design the data so that its order is inherent in its parts.

Researchers have developed several strategies to ensure unique reconstruction:

  1. Indexing and Spatially-Coupled Codes: Lorenz Welter and Antonia Wachter-Zeh use specialized index codes to label fragments, allowing them to be stitched back together even if many are missing or corrupted Index-Based Concatenated Codes for the Multi-Draw DNA Storage Channel.
  2. Algebraic Constraints: By using $B_h$ codes (where all sums of $h$ elements are distinct), Ryan Gabrys and Srilakshmi Pattabiraman ensure that even when fragments from different molecules are mixed together, their mass signatures don't overlap in ways that create ambiguity Reconstructing Mixtures of Coded Strings from Prefix and Suffix Compositions.
  3. Structural Properties: Using "Dyck strings" or specific combinatorial paths (like Catalan-Bertrand paths) ensures that the "bag of masses" can only be parsed in one mathematically consistent way Reconstruction of Sets of Strings from Prefix/Suffix Compositions.

Ultimately, this research direction shifts the burden of data integrity from the channel (the physical medium) to the code. By understanding the fundamental limits of how much information can be stored in unordered collections—as explored by Albert Guillén i Fàbregas in the "short molecule" regime DNA Storage in the Short Molecule Regime—we can build storage systems that are robust to the chaotic, unordered nature of the molecular world.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sequence_reconstruction_from_unordered_f_0744c627,
  title = {Sequence Reconstruction from Unordered Fragment Compositions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequence-reconstruction-from-unordered-fragment-compositions/rdr_0744c627acf6445996de9c5df248ae58},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_sequence_reconstruction_from_unordered_f_0744c627_v1,
  title = {Sequence Reconstruction from Unordered Fragment Compositions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequence-reconstruction-from-unordered-fragment-compositions/rdr_0744c627acf6445996de9c5df248ae58/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}