🔢 mathematics

Sequence Reconstruction for Sticky Insertion/Deletion Channels

This paper investigates the sequence reconstruction problem for $(t, s)$ -sticky-insertion/deletion channels by deriving a recursive formula for the minimum number of distinct outputs required to uniquely recover a transmitted vector and proposing an efficient algorithm to perform this reconstruction.

Original authors: Van Long Phuoc Pham, Yeow Meng Chee, Kui Cai, Van Khu Vu

Published 2026-04-24

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Van Long Phuoc Pham, Yeow Meng Chee, Kui Cai, Van Khu Vu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Fixing a Messy Message

Imagine you are trying to send a secret message to a friend using a very glitchy walkie-talkie. But this isn't just a normal glitchy channel; it's a "Sticky" channel.

Sticky Insertions: Sometimes, when you say a word, the walkie-talkie gets stuck and repeats it. If you say "Hello," it might come out as "Hello-Hello."
Sticky Deletions: Sometimes, if you say a word twice (like "Hello-Hello"), the walkie-talkie might accidentally swallow one of them, turning it back into "Hello."

The problem is that the receiver doesn't know which version is the original. Did you say "Hello" once, and it got repeated? Or did you say it twice, and one got deleted?

The Goal: The researchers want to know: How many times do you need to send the same message to guarantee your friend can figure out exactly what you said? And once they have all those copies, how can they quickly figure out the original without getting a headache?

The Analogy: The "Run" of Identical Marbles

To solve this, the authors realized they don't need to worry about what the letters are (A, B, C), but rather how they are grouped.

Imagine your message is a string of marbles.

Original: Red, Red, Blue, Blue, Blue, Green.
The "Run": This is a group of identical marbles stuck together. In the example above, you have a "Red Run" (2 marbles), a "Blue Run" (3 marbles), and a "Green Run" (1 marble).

The Magic Rule: Even if the sticky channel adds extra marbles or eats some, it never changes the order of the colors, and it never merges two different colors together.

If you have a Red Run, it stays a Red Run. It might get bigger (Red-Red-Red) or smaller (Red), but it will never turn into a Blue Run.

So, the problem simplifies to: "How many marbles are in each color run?"

Part 1: The Magic Number (How many copies do we need?)

The first big question the paper answers is: What is the minimum number of copies ( $N$ ) the receiver needs to be 100% sure of the original message?

If you only send 1 copy, you might get a "Red-Red-Red" and not know if you started with "Red-Red" or "Red-Red-Red-Red" (and one got deleted).

The authors did some heavy math (using something called "generating functions," which is like a fancy calculator for counting patterns) to find the exact formula.

The Result: They found a specific number based on:

$r$ : How many different color groups (runs) you have.
$t$ : The maximum number of times a marble could get stuck (inserted).
$s$ : The maximum number of times a marble could get eaten (deleted).

They proved that if you send $N$ copies, where $N$ is calculated by their formula, the receiver can mathematically guarantee they will find the one and only original sequence. It's like having enough puzzle pieces to solve the puzzle with no ambiguity.

Part 2: The Detective Work (How to reconstruct the message)

Knowing how many copies you need is great, but what do you do with them? You can't just guess. The paper provides a step-by-step detective algorithm.

Imagine you have 5 copies of the message received from the sticky channel. They all look slightly different because of the errors.

The Detective's Strategy:

Check the Skeleton: First, make sure all 5 copies have the same "skeleton" (e.g., they all go Red -> Blue -> Green). If one says "Red -> Green -> Blue," the channel is too broken, and you give up.
The Min/Max Game: Look at the first "Red Run" across all 5 copies.
- Copy 1 has 2 Reds.
- Copy 2 has 3 Reds.
- Copy 3 has 4 Reds.
- Copy 4 has 2 Reds.
- Copy 5 has 5 Reds.
- The "Minimum" is 2. The "Maximum" is 5.
- The original number of Reds must be somewhere between these two numbers (adjusted for the max errors allowed).
The Frequency Check: This is the clever part. The algorithm looks at how often each number appears.
- If the original was 3 Reds, and you have a limit of 1 error, you would expect to see mostly 2s, 3s, and 4s.
- If you see a weird pattern (like too many 5s), the math tells you the original couldn't have been 3.
The Two-Pointer Solution: The authors found a super-fast way to do this check. Instead of checking every single number one by one (which is slow), they use a "Two-Pointer" method. Imagine two fingers sliding along a ruler; they move in opposite directions to quickly find the "sweet spot" where the original number must be.

Why is this cool?
Without this algorithm, a computer might have to try billions of combinations to find the answer. With their algorithm, it's like having a GPS that takes you straight to the destination in seconds.

Why Does This Matter?

You might ask, "Who cares about sticky marbles?"

This is actually crucial for future technology:

DNA Data Storage: Scientists are trying to store data in DNA. DNA is like a long string of beads. When reading DNA, the machine sometimes gets "sticky" and reads a letter twice or skips one. This research helps us figure out how to store data reliably in DNA.
Racetrack Memory: A new type of computer memory that uses magnetic domains. These can also suffer from "sticky" errors where a bit gets duplicated or lost.

Summary

The Problem: Messages get messed up by "sticky" errors (duplicates or missing items).
The Insight: The order of groups stays the same; only the size of the groups changes.
The Solution:
- Math: They calculated the exact number of copies needed to guarantee a correct reconstruction.
- Algorithm: They built a fast, efficient "detective" tool to find the original message from those copies, avoiding slow, brute-force guessing.

It's a perfect blend of pure math (counting possibilities) and practical engineering (building a fast recovery tool) to keep our future data safe.

1. Problem Statement

The paper addresses the Sequence Reconstruction Problem for a specific type of noisy channel known as the $(t, s)$ -sticky-insdel channel.

Context: This problem is motivated by emerging data storage systems like racetrack memories and DNA-based storage, where errors often manifest as "sticky" insertions (repeating a symbol) and "sticky" deletions (removing a symbol from a run of identical symbols).
Channel Model:
- Sticky Insertion: A symbol is duplicated (e.g., $0 \to 00$ ).
- Sticky Deletion: A symbol is removed from a run of length $\ge 2$ (e.g., $00 \to 0$ ).
- Constraints: A transmitted vector $x$ undergoes at most $t$ sticky-insertion errors and at most $s$ sticky-deletion errors.
Key Property: These errors preserve the number of runs (maximal contiguous substrings of identical symbols) but alter the lengths of those runs.
Objective: Determine the minimum number of distinct channel outputs ( $M$ ) required to uniquely reconstruct the original transmitted vector $x$ . Additionally, the authors aim to provide efficient algorithms to perform this reconstruction.

2. Methodology

The authors employ a combination of enumerative combinatorics, generating functions, and algorithmic design.

A. Mathematical Abstraction

Run-Length Encoding: The authors map a sequence $x$ with $r$ runs to a pair $(c, u)$ , where $c$ represents the sequence of distinct symbols (the "run heads") and $u = (u_1, \dots, u_r)$ represents the lengths of the runs.
Error Ball Definition: Since the run structure $c$ $c$ remains unchanged, the problem reduces to reconstructing the run-length vector $u$ $u$ from erroneous vectors $v$ $v$ within an asymmetric error ball $A_{t,s}(u)$ $A_{t, s} (u)$ .
- $v \in A_{t,s}(u)$ if $\sum \max(0, u_i - v_i) \le s$ (deletions) and $\sum \max(0, v_i - u_i) \le t$ (insertions).
Intersection Analysis: The core of the reconstruction problem relies on finding the maximum size of the intersection of two such error balls, denoted as $N_{t,s}(r) = \max_{u_1, u_2} |A_{t,s}(u_1) \cap A_{t,s}(u_2)|$ . The minimum number of outputs required is $N_{t,s}(r) + 1$ .

B. Derivation of Bounds

Maximum Ball Size: The authors first derive a recursive formula for the maximum size of a single sticky-insdel ball, $A_{t,s}(r)$ , using induction. They prove that the maximum size occurs when the run lengths are sufficiently large ( $u_i \ge s+1$ ).
Generating Functions: To obtain an explicit formula for $A_{t,s}(r)$ , they construct a generating function $f_r(x, y)$ and extract coefficients, resulting in a closed-form summation involving binomial coefficients.
Intersection Formula: Using the derived properties, they establish a formula for the maximum intersection size $N_{t,s}(r)$ , which determines the reconstruction threshold.

C. Algorithm Design

The paper proposes a reconstruction algorithm based on the theoretical bounds:

Input: $M = N_{t,s}(r) + 1$ distinct erroneous sequences.
Process:
1. Validation: Verify that all inputs share the same run formation (symbol sequence).
2. Run-Length Analysis: For each run index $j$ , compute the minimum ( $a_j$ ) and maximum ( $b_j$ ) observed run lengths across all inputs.
3. Constraint Solving: The true run length $u_j$ must lie in $[b_j - t, a_j + s]$ . The algorithm uses frequency counts of observed lengths to identify the unique $u_j$ that satisfies specific combinatorial inequalities derived from the error ball definitions.
Optimization: While a naive approach checks all candidates, the authors propose an optimized two-pointer algorithm (Algorithm 4) that exploits monotonic properties of the constraints to find the unique solution efficiently.

3. Key Contributions

Explicit Formula for Reconstruction Threshold: The paper provides the first explicit formula for the minimum number of distinct outputs ( $N_{t,s}(r) + 1$ $N_{t, s} (r) + 1$ ) required to uniquely reconstruct a sequence in a channel with both sticky insertions and deletions.
- The formula is given as:
  $N_{t,s}(r) = 1 + \sum_{i=1}^t A_{t-i,s}(r-1) + \sum_{i=1}^s A_{t,s-i}(r-1)$
- Where $A_{t,s}(r)$ is defined via a complex summation of binomial coefficients derived from the generating function.
Characterization of Maximum Error Balls: The authors prove that the maximum size of a sticky-insdel ball is achieved when run lengths are large, providing a foundational lemma for the intersection analysis.
Efficient Reconstruction Algorithm: They present a deterministic algorithm that reconstructs the original vector from the minimum number of outputs. The algorithm includes an optimized two-pointer approach that reduces the complexity of finding the correct run lengths compared to a brute-force search.

4. Results

Theoretical Result: The paper establishes that for a vector with $r$ runs, the number of distinct outputs required is exactly $M = N_{t,s}(r) + 1$ .
Algorithmic Result: The proposed algorithm successfully recovers the original vector $x$ $x$ from $M$ $M$ outputs.
- Time Complexity: The preprocessing (validity check and run extraction) takes $O(Mn)$ time. The core reconstruction step for each run uses the optimized two-pointer method, which is significantly faster than the naive $O((s+t)^2)$ approach, though the exact complexity of the optimized step depends on the specific constraints of the binomial coefficient checks.
Special Cases: The results generalize previous work on pure sticky-insertion channels (where $s=0$ ), recovering known results for tandem-duplication channels as a special case.

5. Significance

Practical Application: This work is critical for the reliability of DNA data storage and racetrack memories, where sticky errors are the dominant failure mode. Knowing the exact number of reads (outputs) needed to guarantee data recovery allows system designers to optimize storage overhead and read redundancy.
Theoretical Advancement: Prior to this work, the reconstruction problem for channels with both insertion and deletion errors was not fully solved with explicit formulas. This paper bridges the gap between pure deletion channels and pure insertion channels, providing a unified framework for sticky-insdel errors.
Algorithmic Efficiency: The development of an efficient reconstruction algorithm ensures that the theoretical bounds are not just mathematical curiosities but practically implementable solutions for real-world decoding systems.

In summary, this paper solves the sequence reconstruction problem for sticky-insdel channels by deriving exact combinatorial bounds on the required number of observations and providing a constructive, efficient algorithm to recover the original data.